插入排序

直接插入

1
2
3
4
5
6
7
8
9
void insertSort(vector<int>& nums) {
	for (int i = 1; i < nums.size(); ++i) {
		int j = i;
		while (j >= 1 && nums[j] < nums[j - 1]) {
			swap(nums[j], nums[j - 1]);
			--j;
		}
	}
}

折半插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void binaryInsertSort(vector<int>& nums) {
	for (int i = 1; i < nums.size(); ++i) {
		int key = nums[i];
		int low = 0, high = i - 1;
		while (low <= high) {
			int mid = low + (high - low) / 2;
			if (nums[mid] >= key) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		for (int k = i - 1; k >= low; --k)  {
			nums[k + 1] = nums[k];
		}
		nums[low] = key;
	}
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
void shellSort(vector<int>& nums) {
	int n = nums.size();
	for (int dk = n / 2; dk >= 1; dk /= 2) {
		for (int i = dk; i < n; ++i) {
			int j = i;
			while (j >= dk && nums[j] < nums[j - dk]) {
				swap(nums[j], nums[j - dk]);
				j -= dk;
			}
		}
	}
}

冒泡排序

1
2
3
4
5
6
7
8
9
void bubbleSort(vector<int>& nums) {
	for (int i = nums.size() - 1; i > 0; --i) {
		for (int j = 0; j < i; ++j) {
			if (nums[j] > nums[j + 1]) {
				swap(nums[j], nums[j + 1]);
			}
		}
	}
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int partition(vector<int>& nums, int left, int right) {
    // 设定随机pivot
	int randIdx = rand() % (right - left + 1) + left;
	swap(nums[left], nums[randIdx]);
	int pivot = nums[left];
	while (left < right) {
		while (left < right && nums[right] >= pivot) --right;
		nums[left] = nums[right];
		while (left < right && nums[left] <= pivot) ++left;
		nums[right] = nums[left];
	}
	nums[left] = pivot;
	return left;
}

void recurSort(vector<int>& nums, int left, int right) {
	if (left > right) return;
	int p = partition(nums, left, right);
	recurSort(nums, left, p - 1);
	recurSort(nums, p + 1, right);
}

void quickSort(vector<int>& nums) {
	srand((unsigned)time(nullptr));
	recurSort(nums, 0, nums.size() - 1);
}

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
void selectSort(vector<int>& nums) {
	for (int i = 0; i < nums.size(); ++i) {
		int minIdx = i;
		for (int j = i + 1; j < nums.size(); ++j) {
			if (nums[minIdx] > nums[j]) {
				minIdx = j;
			}
		}
		swap(nums[i], nums[minIdx]);
	}
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void headAjust(vector<int>& nums, int i, int len) {
	while (i * 2 + 1 <= len) {
		int left = i * 2 + 1, right = i * 2 + 2;
		int largest = i;
		if (left <= len && nums[left] > nums[i]) {
			largest = left;
		}
		if (right <= len && nums[right] > nums[largest]) {
			largest = right;
		}
		if (largest == i) break;
		swap(nums[i], nums[largest]);
		i = largest;
	}
}

void heapSort(vector<int>& nums) {
    // 构建最大堆
	int len = nums.size() - 1;
	for (int i = len / 2; i >= 0; --i) {
		headAjust(nums, i, len);
	}
	for (int i = len; i > 0; --i) {
		swap(nums[i], nums[0]);
		headAjust(nums, 0, --len);
	}
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void merge(vector<int>& nums, int low, int mid, int high) {
	vector<int> numsCpy(high - low + 1);
	int p1 = low, p2 = mid + 1, p3 = 0;
	while (p1 <= mid && p2 <= high) {
		if (nums[p1] <= nums[p2]) {
			numsCpy[p3++] = nums[p1++];
		}
		else {
			numsCpy[p3++] = nums[p2++];
		}
	}
	while (p1 <= mid) numsCpy[p3++] = nums[p1++];
	while (p2 <= high) numsCpy[p3++] = nums[p2++];
	for (int i = 0; i < numsCpy.size(); ++i) {
		nums[low++] = numsCpy[i];
	}
}

void recurSort(vector<int>& nums, int low, int high) {
	if (low >= high) return;
	int mid = low + (high - low) / 2;
	recurSort(nums, low, mid);
	recurSort(nums, mid + 1, high);
	merge(nums, low, mid, high);
}

void mergeSort(vector<int>& nums) {
	recurSort(nums, 0, nums.size() - 1);
}

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 本排序算法仅适用于整数排序
void countingSort(vector<int>& nums, int exp) {
	int n = nums.size();
	vector<int> output(n);
	vector<int> count(10, 0);
	for (int i = 0; i < n; ++i) {
		int digit = (nums[i] / exp) % 10;
		++count[digit];
	}
	for (int i = 1; i < 10; ++i) {
		count[i] += count[i - 1];
	}
	for (int i = n - 1; i >= 0; --i) {
		int digit = (nums[i] / exp) % 10;
		output[count[digit] - 1] = nums[i];
		--count[digit];
	}
	for (int i = 0; i < n; ++i) {
		nums[i] = output[i];
	}
}

void radixSort(vector<int>& nums) {
	int n = nums.size();
	vector<int> positiveNums;
	vector<int> negativeNums;
	for (int i = 0; i < n; ++i) {
		if (nums[i] >= 0) {
			positiveNums.emplace_back(nums[i]);
		}
		else {
			negativeNums.emplace_back(-1 * nums[i]);
		}
	}
	if (!positiveNums.empty()) {
		int maxVal = *max_element(positiveNums.begin(), positiveNums.end());
		for (int exp = 1; maxVal / exp > 0; exp *= 10) {
			countingSort(positiveNums, exp);
		}
	}
	if (!negativeNums.empty()) {
		int maxVal = *max_element(negativeNums.begin(), negativeNums.end());
		for (int exp = 1; maxVal / exp > 0; exp *= 10) {
			countingSort(negativeNums, exp);
		}
	}
	for (int i = 0; i < n; ++i) {
		if (i < negativeNums.size()) {
			nums[i] = -1 * negativeNums[negativeNums.size() - i - 1];
		}
		else {
			nums[i] = positiveNums[i - negativeNums.size()];
		}
	}
}