排序算法总结

一些知识

  • 稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
  • 非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
  • 原地排序：指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换。
  • 非原地排序：需要利用额外的数组来辅助排序。
  • 使用计数、基数排序算法对负数排序时，可以先预处理让其变为正数，排序完毕后再复原，比如统一加减；

常见稳定排序有：冒泡排序、插入排序、归并排序

常见非稳定排序有：选择排序、希尔排序、堆排序、快速排序

十大排序

1.冒泡排序

冒泡排序就是比较相邻的两个元素，把小的元素往前调(把大的元素往后调)，每次循环将最大的元素移动到后面；

步骤：对每一对相邻元素，如果第一个比第二个大，就交换他们两个；

时间O(n^2)、空间O(1)、稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubbleSort(vector<int>& nums) {
    int len = nums.size();
    // 只需len - 1次循环
    for (int i = 0; i < len - 1; ++i) {
        // 标记，避免无效循环
        bool flag = false;
        // 界限是len - 1 - i
        for (int j = 0; j < len - 1 - i; ++j) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

2.选择排序

选择排序是给每个位置选择剩余未排序元素中最小的元素，然后交换；

步骤：

  • 在未排序序列中找到最小(大)元素，存放到排序序列的起始位置；
  • 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
  • 以此类推，直到所有元素均排序完毕；

时间O(n^2)、空间O(1)、不稳定

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

3.插入排序

插入排序是在一个已经有序的小序列的基础上，每次寻找合适的插入位置来插入一个元素。刚开始这个有序的小序列就是第一个元素，每次从有序序列的末尾倒序开始寻找插入位置。

步骤：

  1. 从第一个元素开始，该元素可以认为已经被排序

  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

  3. 如果该元素（已排序）大于新元素，将该元素移到前一位置

  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

  5. 将新元素插入到该位置后

  6. 重复步骤2~5

时间O(n^2)、空间O(1)、稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void insertionSort(vector<int>& a) { 
    int n = a.size();
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) {
            int j = i - 1;
            // 待排序的新元素
            int x = a[i];

            while (j >= 0 && x < a[j]) {
                // 把大于新元素的元素后移
                a[j + 1] = a[j];
                --j;
            }
			// 此处x >= a[j]
            a[j + 1] = x;
        }
    }
}

4.快速排序

每次处理完后基准位置是有序的，然后递归处理左右区间；

步骤：

  1. 选取第一个数为基准

  2. 将比基准小的数交换到前面，比基准大的数交换到后面

  3. 对左右区间递归重复第二步，直到各区间只有一个数

时间O(nlogn)、空间O(logn)、不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 左闭右闭
void quickSort(vector<int>& a, int left, int right) {
    // 递归结束标志
    if (left >= right) return;

    int first = left;      // 低位下标
    int last  = right;     // 高位下标
    int key   = a[first];  // 设第一个为基准

    while (first < last) {
        // 从后往前走，将比第一个小的移到前面
        while (first < last && a[last] > key) --last;
        if (first < last) a[first++] = a[last];

        //从前往后走， 将比第一个大的移到后面
        while (first < last && a[first] <= key) ++first;
        if (first < last) a[last--] = a[first];
    }
    a[first] = key;
    
    // 自顶向下
    quickSort(a, left, first - 1);  // 前半递归
    quickSort(a, first + 1, right); // 后半递归
}

5.希尔排序

希尔排序是插入排序的一种变种。无论是插入排序还是冒泡排序，如果原数组的一个元素距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。间隔也称作增量。

时间O(nlogn)、空间O(1)、不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void shellSortCore(vector<int>& nums, int gap, int i) {
    int inserted = nums[i];
    //  插入的时候按间隔gap进行插入
    int j = i - gap;
    while (j >= 0 && inserted < nums[j]) {
        nums[j + gap] = nums[j];
        j -= gap;
    }
    nums[j + gap] = inserted;
}

void shellSort(vector<int>& nums) {
    int len = nums.size();
    //进行分组，最开始的时候，gap为数组长度一半
    for (int gap = len / 2; gap > 0; gap /= 2) {
        //对各个分组进行插入分组
        for (int i = gap; i < len; ++i) {
            //将nums[i]插入到所在分组正确的位置上
            shellSortCore(nums, gap, i);
        }
    }
}

6.归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。适用于处理较大规模的数据，但比较耗内存。

归并排序有自顶向下的递归方法，和自底向上的迭代方法；

即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

  • 对于分治，只需不断地分，直到只有一个元素的时候（一个元素认为它有序）；

  • 对于合并，只要不断地取出两个有序数组中比较小的那一个放在一个辅助数组中（通过比较），直到把两个有序数组中的元素取完；

步骤：

  • 把长度为n的输入序列分成两个长度为n/2的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列；

时间O(nlogn)、空间O(n)、稳定

①递归，辅助数组传引用

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
// 左闭右闭
void mergeSortCore(vector<int>& nums, vector<int>& temp, int left, int right) {
    if (left >= right) return;

    int mid    = left + (right - left) / 2;
    int start1 = left, end1 = mid;
    int start2 = mid + 1, end2 = right;
    // 分治
    mergeSortCore(nums, temp, start1, end1);
    mergeSortCore(nums, temp, start2, end2);

    // 合并到辅助数组中
    int index = left;
    while (start1 <= end1 && start2 <= end2) {
        temp[index++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];
    }
    while (start1 <= end1) temp[index++] = nums[start1++];
    while (start2 <= end2) temp[index++] = nums[start2++];

    // 从辅助数组取回排序好的元素
    for (int i = left; i <= right; ++i) nums[i] = temp[i];
}

void mergeSort(vector<int>& nums) {
    // 辅助数组, 存储排序好的数据
    vector<int> temp(nums.size(), 0);
    mergeSortCore(nums, temp, 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
void mergeTwoVec(vector<int>& nums, int left, int mid, int right) {
    int start1 = left, end1 = mid;
    int start2 = mid + 1, end2 = right;

    // 辅助数组, 存储排序好的数据
    vector<int> temp(right - left + 1, 0);

    // 合并到辅助数组中
    int index = 0;
    while (start1 <= end1 && start2 <= end2) {
        temp[index++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];
    }
    while (start1 <= end1) temp[index++] = nums[start1++];
    while (start2 <= end2) temp[index++] = nums[start2++];

    // 从辅助数组取回排序好的元素
    index = 0;
    for (int i = left; i <= right; ++i) nums[i] = temp[index++];
}

// 左闭右闭
void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    // 分治
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    // 合并
    mergeTwoVec(nums, left, mid, right);
}

7.堆排序

基于堆(大根堆、小根堆)的一种排序算法，每次从堆顶取出一个元素；

  • 堆是采用vertor<TimeNode>数组实现的，数组下标从0开始，对应堆顶节点；
  • 对于数组中下标为k的某节点，其左子节点为2*k + 1，右子节点为2*k + 2，父节点为(k - 1) / 2；
  • 插入节点时，插入到数组中的最后一个节点的后面，然后与该节点的父节点比较大小，如果插入的元素小于父节点元素，那么与父节点交换位置。重复上述步骤直到大于父节点元素或者到达堆顶。该过程叫做上浮，即插入时上浮；
  • 移除节点时，将该节点与末尾节点交换，然后当前节点(之前的尾部节点)与子节点中的较小者比较，如果当前节点大于较小子节点，那么与较小子节点交换位置，重复上述步骤直到小于较小子节点或者到达倒数第二个节点为止。最后再删除末尾节点。该过程叫做下沉，即移除元素时下沉;
  • 排序时无需插入节点上浮构建堆，而是将待排数组看着完全二叉树，不断下沉节点，从而变成大顶堆；

步骤：

  • 从后往前遍历数据，让当前节点的父节点下沉来构建堆（大根堆）；

  • 交换堆顶与堆最后一个元素；

  • 堆大小(heapSize)减一；

  • 调整堆，即新堆顶节点下沉；

时间O(nlogn)、空间O(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
// 维护大根堆，让值小的节点下沉
void heapSink(vector<int>& nums, int heapSize, int i) {
    int maxIdx = i;
    int left   = i * 2 + 1;
    int right  = i * 2 + 2;

    if (left < heapSize && nums[left] > nums[maxIdx]) maxIdx = left;
    if (right < heapSize && nums[right] > nums[maxIdx]) maxIdx = right;

    if (maxIdx != i) {
        swap(nums[maxIdx], nums[i]);
        heapSink(nums, heapSize, maxIdx);
    }
}

// 建立大根堆，从树的倒数第二层的倒数第一个结点开始，让值小的节点下沉
void heapBuild(vector<int>& nums) {
    // 最后一个节点的父节点的下标
    int lastRoot = ((nums.size() - 1) - 1) / 2;

    for (int i = lastRoot; i >= 0; --i) {
        heapSink(nums, nums.size(), i);
    }
}

// 堆排序
void heapSort(vector<int>& nums) {
    heapBuild(nums);

    int heapSize = nums.size();
    while (heapSize > 1) {
        // 交换最后一个结点和根节点（最大值）
        swap(nums[0], nums[heapSize - 1]);
        // 堆大小减一
        --heapSize;
        // 对交换后的根节点继续进行调整
        heapSink(nums, heapSize, 0);
    }
}

8.计数排序

统计小于等于某元素值的元素的个数count，然后将该元素就放在目标数组的索引i位(i = count, i ≥ 0)；

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在[min, max]的大小区间中；max - min 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。速度快于任何比较排序算法。

步骤：

  • 找出待排序的数组中最大和最小的元素；
  • 统计数组中每个值为 i 的元素出现的次数，存入数组 Cnt 的第 i 项；
  • 对所有的计数累加（从 Cnt 中的第一个元素开始，每一项和前一项相加）；
  • 填充目标数组：将每个元素 i 放在新数组的第 Cnt[i] 项，每放一个元素就将 Cnt[i] 减去 1；

时间O(n+k)、空间O(k)、稳定 （k = maxNum - minNum + 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
// 计数排序
void countSort(vector<int>& nums) {
    // 确保待排序容器非空
    int n = nums.size();
    if (n <= 1) return;

    // 找到数组中的最小和最大元素
    int minNum = INT_MAX, maxNum = INT_MIN;
    for (int num : nums) {
        if (num < minNum) minNum = num;
        if (num > maxNum) maxNum = num;
    }

    int len = maxNum - minNum + 1;
    // 计数容器 countVec
    vector<int> vecCount(len, 0);

    // 统计每个键值出现的次数
    for (int num : nums) ++vecCount[num - minNum];

    int index = 0;
    for (int i = 0; i < len; ++i) {
        while (vecCount[i] != 0) {
            nums[index++] = i + minNum;
            --vecCount[i];
        }
    }
}

②普通计数排序

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
// 计数排序
void countSort(vector<int>& nums) {
    // 确保待排序容器非空
    int n = nums.size();
    if (n == 0) return;

    // 辅助数组存储排序好的元素
    vector<int> temp(n, 0);

    // 使用 nums 的最大值 + 1 作为计数容器 countVec 的大小
    auto it  = max_element(nums.begin(), nums.end());
    int  len = *it + 1;

    vector<int> vecCount(len, 0);

    // 统计每个键值出现的次数
    for (int num : nums) ++vecCount[num];

    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for (int i = 1; i < len; ++i) vecCount[i] += vecCount[i - 1];

    // 将键值放到目标位置,此处逆序是为了保持相同键值的稳定性
    for (int i = n - 1; i >= 0; --i) {
        int num = nums[i];
        // 表示小于等于num的元素有vecCount[num]个
        int cnt = vecCount[num];
        // 也就是包括num自己，所有需要减一
        int idx   = cnt - 1;
        temp[idx] = num;
        --vecCount[num];
    }
    swap(nums, temp);
}

9.桶排序

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。大编号桶里的所有元素均大于小编号桶里的任意元素；

步骤：

  • 设置一个定量的数组当作桶；
  • 寻访序列，并且把项目一个一个放到对应的桶中；
  • 对每个不是空的桶子进行排序（使用其它排序算法）；
  • 从非空桶里把取回排序好的元素；

时间O(n+k)、空间O(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
void bucketSort(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return;

    // 获取数组的最小值和最大值
    int minNum = INT_MAX, maxNum = INT_MIN;
    for (int num : nums) {
        if (num < minNum) minNum = num;
        if (num > maxNum) maxNum = num;
    }

    int bucketNum  = 5;                                  // 桶数量
    int bucketSize = (maxNum - minNum) / bucketNum + 1;  // 桶大小

    vector<vector<int>> buckets(bucketNum, vector<int>(0));  // 桶数组

    // 从小至大分桶
    for (int num : nums) {
        int bucketIndex = (num - minNum) / bucketSize;
        buckets[bucketIndex].emplace_back(num);
    }
    // 桶内排序
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
    }
    // 从桶中依次取数
    int index = 0;
    for (auto& bucket : buckets) {
        for (int num : bucket) {
            nums[index++] = num;
        }
    }
}

10.基数排序

一种多关键字的排序算法，对数组中所有数依次按由低到高的位数进行多次排序；

步骤：

  • 取得数组中的最大数，并取得位数；
  • arr为原始数组，从最低位开始取每个位组成radix数组；
  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

时间O(n x k)、空间O(n x 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 取出最大位数
int getBitNum(vector<int>& nums) {
    int maxValue = INT_MIN;
    for (int num : nums) {
        if (num > maxValue) maxValue = num;
    }

    int bitCount = 1;
    while (maxValue >= 10) {
        maxValue /= 10;
        ++bitCount;
    }
    return bitCount;
}

// 计数排序的思想，不过记录的是数位上数字的出现次数
void radixSortCore(vector<int>& nums, int divisor) {
    vector<int> countBit(10, 0);  // 0~9 共10个
    // 统计个、十、百、千...位上 0~9 数字的出现次数；
    for (int num : nums) {
        // 多余的位数算出来就是0
        int x = (num / divisor) % 10;
        ++countBit[x];
    }

    // 这里不同于利用差值的计数排序，需要算前缀和
    for (int i = 1; i <= 9; ++i) countBit[i] += countBit[i - 1];

    // 辅助数组存储排序好的元素
    vector<int> temp(nums.size(), 0);

    // 需要倒叙保证稳定
    for (int i = nums.size() - 1; i >= 0; --i) {
        int x = (nums[i] / divisor) % 10;
        // 该元素前面有 cnt 个当前数位比它小的元素，包括其自己；
        int cnt = countBit[x];
        temp[cnt - 1] = nums[i];
        --countBit[x];
    }
    swap(nums, temp);
}

void radixSort(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return;

    int maxBitLen = getBitNum(nums);

    // 基数排序，低位优先
    int divisor = 1;
    for (int i = 0; i < maxBitLen; ++i) {
        radixSortCore(nums, divisor);
        // 不断提高位数
        divisor *= 10;
    }
}

【参考资料】力扣题解、阿秀笔记