常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ In-place 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ In-place 不稳定
插入排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ In-place 稳定
希尔排序 $O(\log(n))$ $O(n\log^2(n))$ $O(n\log^2(n))$ $O(1)$ In-place 不稳定
归并排序 $O(\log(n))$ $O(\log(n))$ $O(\log(n))$ $O(n)$ Out-place 稳定
快速排序 $O(\log(n))$ $O(\log(n))$ $O(n^2)$ $O(\log(n))$ In-place 不稳定
堆排序 $O(\log(n))$ $O(\log(n))$ $O(\log(n))$ $O(1)$ In-place 不稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(k)$ Out-place 稳定
桶排序 $O(n+k)$ $O(n+k)$ $O(n……2)$ $O(n+k)$ Out-place 稳定
基数排序 $O(n*k)$ $O(n*k)$ $O(n*k)$ $O(n+k)$ Out-place 稳定

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

1
2
3
4
n：数据规模
k：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存

冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  3. 针对所有的元素重复以上的步骤，除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> bubbleSort(vector<int> nums) {
	for (int i = 1; i < nums.size(); i ++) {
		for(int j = 0; j < nums.size() - i; j ++) {
			if(nums[j] > nums[j+1]) {
				int temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
			}
		}
	}
	return nums;
}

选择排序

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  3. 重复第二步，直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> selectionSort(vector<int> nums) {
	for (int i = 0; i < nums.size()-1; i ++) {
		int minIndex = i;
		for(int j = i+1; j < nums.size(); j ++) {
			if(nums[j] < nums[minIndex]) {
				minIndex = j;
			}
		}
		if(minIndex != i) {
			int temp = nums[minIndex];
			nums[minIndex] = nums[i];
			nums[i] = temp;
		}
	}
	return nums;
}

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）。
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> insertionSort(vector<int> nums) {
	for (int i = 0; i < nums.size(); ++i) {
		int preIndex = i - 1;
		int current = nums[i];
		while(preIndex >= 0 && nums[preIndex] > current) {
			nums[preIndex+1] = nums[preIndex];
			preIndex --;
		}
		nums[preIndex+1] = current;
	}
	return nums;
}

希尔排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> shellSort(vector<int> nums) {
	int gap = 1;
	while(gap < nums.size() / 3) {
		gap = gap * 3 + 1;
	}
	while(gap > 0) {
		for(int i = gap; i < nums.size(); i ++) {
			int temp = nums[i];
			int j = i - gap;
			while(j >= 0 && nums[j] > temp) {
				nums[j+gap] = nums[j];
				j-=gap;
			}
			nums[j+gap] = temp;
		}
		gap = gap / 3;
	}
	return nums;
}

归并排序

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。
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
vector<int> merge(vector<int> left, vector<int> right) {
	vector<int> result;
	while(left.size() > 0 && right.size() > 0) {
		if(left[0] > right[0]) {
			result.push_back(right[0]);
			right.erase(right.begin());
		} else {
			result.push_back(left[0]);
			left.erase(left.begin());
		}
	}
	while(left.size() > 0) {
		result.push_back(left[0]);
		left.erase(left.begin());
	}
	while(right.size() > 0) {
		result.push_back(right[0]);
		right.erase(right.begin());
	}
	return result;
}

vector<int> mergeSort(vector<int>& nums) {
	if(nums.size() < 2) {
		return nums;
	}
	int mid = nums.size() / 2;
	vector<int> left(nums.begin(), nums.begin()+mid);
	vector<int> right(nums.begin()+mid, nums.end());
	return merge(mergeSort(left), mergeSort(right));
}

快速排序

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
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) {
	int basic = nums[left];
	int partitionIndex = left+1;
	int i = partitionIndex;
	while(i <= right) {
		if(nums[i] < basic) {
			int temp = nums[i];
			nums[i] = nums[partitionIndex];
			nums[partitionIndex] = temp;
			partitionIndex ++;
		}
		i ++;
	}
	nums[left] = nums[partitionIndex - 1];
	nums[partitionIndex-1] = basic;
	return partitionIndex - 1;
}

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

堆排序

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； $arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]$
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列； $arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]$
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
void adjustHeap(vector<int>& nums, int i, int length) {
	// 取出元素i
	int temp = nums[i];

	// 从j节点开始
	for (int j = i*2+1; j < length;  j = j*2+1) {
		// 如果左子节点小于右子节点，j指向右子节点
		if(j+1<length && nums[j] < nums[j+1]) {
			j ++;
		}
		// 如果子节点大于父节点，将子节点赋值为父节点
		if(nums[j] > temp) {
			nums[i] = nums[j];
			i = j;
		} else {
			break;
		}
	}
	nums[i] = temp;
}

void swap(vector<int>& nums, int a, int b) {
	int temp = nums[a];
	nums[a] = nums[b];
	nums[b] = temp;
}

vector<int> heapSort(vector<int>& nums) {
	// 构建大顶堆
	for (int i = nums.size()/2-1; i >= 0; i --) {
		// 从第一个非叶子节点从下至上，从左至右调整结构
		adjustHeap(nums, i, nums.size());
	}

	// 调整结构，交换堆顶元素与末尾元素
	for(int j = nums.size()-1; j > 0; j --) {
		swap(nums, 0, j);
		adjustHeap(nums, 0, j);
	}
	return nums;
}

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> countingSort(vector<int> nums) {
	// 得到最大值
	int max = nums[0];
	for (int i = 1; i < nums.size(); ++i) {
		if(nums[i] > max) {
			max = nums[i];
		}
	}
	// 确定统计数组长度
	vector<int> countArray(max+1);
	// 遍历数列，填充
	for (int i = 0; i < nums.size(); ++i) {
		countArray[nums[i]] ++;
	}

	vector<int> res;
	for (int i = 0; i < countArray.size(); ++i) {
		for(int j = 0; j < countArray[i]; j ++) {
			res.push_back(i);
		}
	}
	return res;
}

优化：

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
vector<int> countingSort2(vector<int> nums) {
	// 得到最大值与最小值
	int max = nums[0];
	int min = nums[0];
	for (int i = 1; i < nums.size(); ++i) {
		if(nums[i] > max) {
			max = nums[i];
		}
		if(nums[i] < min) {
			min = nums[i];
		}
	}
	// 确定统计数组长度
	int d = max - min;
	vector<int> countArray(d+1);
	// 遍历数列，填充
	for (int i = 0; i < nums.size(); ++i) {
		countArray[nums[i] - min] ++;
	}
	// 统计数组变形，后面的元素等于前面的元素之和
	int sum = 0;
	for(int i = 0; i < countArray.size(); i ++) {
		sum += countArray[i];
		countArray[i] = sum;
	}

	// 倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
	vector<int> res(nums.size());
	for (int i = nums.size()-1; i >= 0; i --) {
		res[countArray[nums[i]-min]-1] = nums[i];
		countArray[nums[i]-min] --;
	}
	return res;
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

当输入的数据可以均匀的分配到每一个桶中，速度最快。

当输入的数据被分配到了同一个桶中，速度最慢。

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
vector<int> bucketSort(vector<int>& nums) {
	int minNum = nums[0];
	int maxNum = nums[0];
	for (int i = 1; i < nums.size(); ++i) {
		if(nums[i] > maxNum) {
			maxNum = nums[i];
		}
		if(nums[i] < minNum) {
			minNum = nums[i];
		}
	}

	// 桶的大小
	double bucketRange = (maxNum - minNum)*1.0 / nums.size();

	// 桶数组
	vector<vector<int>> bucketArray(nums.size()+1);

	for(int num : nums) {
		bucketArray[(int)(num-minNum)/bucketRange].push_back(num);
	}

	// 桶内排序
	for(int i = 0; i < bucketArray.size(); i ++) {
		sort(bucketArray[i].begin(), bucketArray[i].end());
	}

	vector<int> res;
	for(vector<int> num : bucketArray) {
		res.insert(res.end(), num.begin(), num.end());
	}
	return res;
}

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；
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
vector<int> radixSort(vector<int>& nums) {
	// 初始为个位数
	int index = 0;
	// 最小的位数置为1（包含0）
	int n = 1;
	int maxNum = nums[0];
	for (int i = 1; i < nums.size(); ++i) {
		if(nums[i] > maxNum) {
			maxNum = nums[i];
		}
	}
	// 得到最大数是几位数
	while(maxNum/10 > 0) {
		n ++;
		maxNum /= 10;
	}

	while(index < n) {
		// 字典桶
		vector<vector<int>> bucket(10);
		for(int num : nums) {
			int radix = (int) (num / pow(10, index))%10;
			bucket[radix].push_back(num);
		}
		int j = 0;
		for(int k = 0; k < 10; k ++) {
			// 桶不为空
			if(bucket[k].size() != 0) {
				for(int num : bucket[k]) {
					nums[j] = num;
					j++;
				}
			}
		}
		index ++;
	}
	return nums;
}