排序算法时间复杂度，空间复杂度和稳定性分析
| 排序算法 |
时间复杂度(平均) |
时间复杂度(最好) |
时间复杂度(最坏) |
空间复杂度 |
稳定性 |
| 快速排序 |
O($nlog_2n$) |
O($nlog_2n$) |
O($n^2$) |
O($log_2n$) |
不稳定 |
| 归并排序 |
O($nlog_2n$) |
O($nlog_2n$) |
O($nlog_2n$) |
O(n) |
稳定 |
| 选择排序 |
O($n^2$) |
O($n^2$) |
O($n^2$) |
O(1) |
不稳定 |
| 插入排序 |
O($n^2$) |
O($n$) |
O($n^2$) |
O(1) |
稳定 |
| 希尔排序 |
O($n^{1.3}$) |
O($n$) |
O(n^2) |
O(1) |
不稳定 |
| 冒泡排序 |
O($n^2$) |
O($n$) |
O($n^2$) |
O(1) |
稳定 |
| 堆排序 |
O($nlog_2n$) |
O($nlog_2n$) |
O($nlog_2n$) |
O(1) |
不稳定 |
| 计数排序 |
O($n+k$) |
O($n+k$) |
O($n+k$) |
O($n+k$) |
稳定 |
1. 快速排序(Quick Sort)
算法思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
C++ 版本实现
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
| class Solution {
public:
/**
* 快速排序
*/
void QuickSort(vector<int>& nums, int left, int right) {
// 注意这个条件
if (left < right) {
int index = partition(nums, left, right);
QuickSort(nums, left, index - 1);
QuickSort(nums, index + 1, right);
}
}
private:
/**
* 快排的核心函数
* 完成设置一个标志位，使得比它小的都在它前面，比它大的都在它后面
*/
int partition(vector<int>& nums, int left, int right) {
int flag = left; // 标志位
int index = left + 1;
for (int i = index; i <= right; i++) {
if (nums[i] < nums[flag]) {
swap(nums, i, index);
index++;
}
}
// 把标志位放回到其应该所处的位置
swap(nums, flag, index - 1);
return index - 1;
}
void swap(vector<int>& nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
};
|
2 .归并排序
算法思想
利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)
C++ 版本实现
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
| class Solution {
public:
/**
* 归并排序
* 思想来源于分治法
*/
void MergeSort(vector<int>& nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
MergeSort(nums, left, mid);
MergeSort(nums, mid + 1, right);
Merge(nums, left, mid, right);
}
}
private:
/**
* 核心函数
*/
void Merge(vector<int>& nums, int left, int mid, int right) {
vector<int> temp(nums.size());
int tempIndex = left;
int rightIndex = mid + 1;
int curIndex = left;
while (left <= mid && rightIndex <= right) {
if (nums[left] < nums[rightIndex]) {
temp[curIndex++] = nums[left++];
} else {
temp[curIndex++] = nums[rightIndex++];
}
}
while (left <= mid) {
temp[curIndex++] = nums[left++];
}
while (rightIndex <= right) {
temp[curIndex++] = nums[rightIndex++];
}
while (tempIndex <= right) {
nums[tempIndex] = temp[tempIndex];
tempIndex++;
}
}
};
|
3. 选择排序
算法思想
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零。
C++ 版本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
/**
* 选择排序
*/
void SelectSort(vector<int>& nums, int left, int right) {
int minIndex;
for (int i = left; i <= right; i++) {
minIndex = i;
for (int j = i + 1; j <= right; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
int temp = nums[minIndex];
nums[minIndex] = nums[i];
nums[i] = temp;
}
}
};
|
4. 插入排序
算法思想
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
C++版本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
/**
* 插入排序
*/
void InsertSort(vector<int>& nums, int left, int right) {
for (int i = left; i <= right; i++) {
int j = i - 1;
int curnum = nums[i];
while (j >= left && curnum < nums[j]) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = curnum;
}
}
};
|
5. 希尔排序
算法思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
C++版本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
/**
* 希尔排序(缩小增量排序) 插入排序的升级版
*/
void ShellSort(vector<int>& nums, int left, int right) {
int n = right - left + 1;
// 缩小增量
for (int gap = left + n / 2; gap > 0; gap /= 2) {
// 采用插入排序算法进行排序
for (int i = left + gap; i <= right; i++) {
int j = i;
int curSum = nums[i];
while (j - gap >= left && curSum < nums[j - gap]) {
nums[j] = nums[j - gap];
j -= gap;
}
nums[j] = curSum;
}
}
}
};
|
6. 冒泡排序
算法思想
从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。
C++ 版本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
/**
* 冒泡排序
*/
void BubbleSort(vector<int>& nums, int left, int right) {
for (int i = left; i < right; i++) {
bool flag = true; //用于判断是否交换
for (int j = left; j < right - left; j++) {
if (nums[j + 1] < nums[j]) {
int temp = nums[j + 1];
nums[j + 1] = nums[j];
nums[j] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
}
};
|
7. 堆排序
算法思想
将序列构建最大堆，然后将堆顶元素和堆底最后一关元素交换，调整最大堆，再交换，再调整最大堆。
C++版本实现
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
| class Solution {
public:
/**
* 堆排序
* 升序：最大堆 降序：最小堆
*
*/
void HeapSort(vector<int>& nums) {
int length = nums.size();
// 构建最大堆，从第一个非叶子结点开始，非叶子结点为 length/2-1
for (int i = length / 2 - 1; i >= 0; i--) {
heapify(nums, i, length);
}
// 依次将最后一个元素和堆顶元素交换，并重新调整最大堆
for (int i = length - 1; i >= 0; i--) {
swap(nums, 0, i);
heapify(nums, 0, i);
}
}
private:
/**
* 下沉
*/
void heapify(vector<int>& nums, int i, int length) {
int temp = nums[i];
// 注意这儿循环，如果下沉到最低端，无法下沉
while (i < length) {
// 假设最左孩子最大
int largest = 2 * i + 1;
// 如果有右孩子，和当前值比较
if (2 * i + 2 < length && nums[2 * i + 2] > nums[largest]) {
largest = 2 * i + 2;
}
// 如果左孩子不存在或者无法下沉，跳出循环
if (largest >= length || temp > nums[largest]) {
break;
}
// 和最大的孩子交换
swap(nums, i, largest);
// 更新i继续下沉
i = largest;
}
}
// 交换
void swap(vector<int>& nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
};
|
8. 计数排序
算法思想
对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。 一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
C++版本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
/**
* 计数排序
*/
void CountingSort(vector<int>& nums, int maxValue) {
vector<int> temp(maxValue + 1, 0);
int index = 0;
for (int i = 0; i < nums.size(); i++) {
temp[nums[i]]++;
}
for (int i = 0; i <= maxValue; i++) {
while (temp[i] > 0) {
nums[index++] = i;
temp[i]--;
}
}
}
};
|
