无为而无不为,无欲其所不欲

冒泡排序、插入排序、选择排序、计数排序、堆排序、快速排序、归并排序

基本概念

排序算法的稳定性：如果待排序的序列中存在相同键值的元素，排序前后的相对顺序保持不变。【相同的元素不交换位置】

最坏时间复杂度、最好时间复杂度和平均时间复杂度.

最坏时间复杂度
最坏情况下的时间复杂度称最坏时间复杂度，一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

平均时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，设每种情况的出现的概率为pi,平均时间复杂度则为sum(pi*f(n)) 。

最好时间复杂度
最理想情况下的时间复杂度称最好时间复杂度。

冒泡排序

【分组插入排序】

思路分析：

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

②对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

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

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

过程动态图：

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

总结：冒泡排序算法最坏的情况和平均复杂度是O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)，排序算法稳定。

直接插入排序

思路分析：

①在长度为N的数组，将数组中第i [1~（N-1) ] 个元素，插入到数组 [0~i] 适当的位置上。

②在排序的过程中当前元素之前的数组元素已经是有序的了。

③在插入的过程中，有序的数组元素，需要向右移动为更小的元素腾出空间，直到为当前元素找到合适的位置。

过程动态图展示：

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

总结：时间复杂度平均为O(n^2)，最坏为O(n^2)，最好为O(n)，空间复杂度为O(1)，排序算法稳定。

希尔排序

基本思想

希尔排序的核心思想是先将数组分割成若干个子序列，然后对每个子序列进行插入排序。随着算法的进行，子序列之间的间隔（gap）逐渐减小，直到最后变为1，此时整个数组变为一个子序列行最后一次插入排序。

希尔排序的过程

  1. 选择一个初始的间隔序列（通常为数组长度的一半）。
  2. 对于每个间隔 gap，将数组分割成若干个子序列。
  3. 对每个子序列进行插入排序。
  4. 减少间隔，重复步骤2和3，直到间隔为1。

举例说明

假设我们有一个长度为 8 的数组 [8, 4, 1, 3, 2, 7, 6, 5]，按照希尔排序的步骤进行排序：

  1. 初始间隔 gap = 4：
    • 子序列1：[8, 2]
    • 子序列2：[4, 7]
    • 子序列3：[1, 6]
    • 子序列4：[3, 5]
    • 对每个子序列进行插入排序。
  2. 间隔 gap = 2：
    • 子序列1：[2, 1, 6, 5]
    • 子序列2：[8, 4, 3, 7]
    • 对每个子序列进行插入排序。
  3. 间隔 gap = 1：
    • 整个数组进行一次插入排序。

通过这个例子，可以看到希尔排序如何逐步减少间隔并进行排序。

假设我们有一个长度为 8 的数组 [8, 4, 1, 3, 2, 7, 6, 5]，按照希尔排序的步骤进行排序：

  1. 初始间隔 gap = 4：
    • 子序列1：[8, 2]
    • 子序列2：[4, 7]
    • 子序列3：[1, 6]
    • 子序列4：[3, 5]
    • 对每个子序列进行插入排序。
  2. 间隔 gap = 2：
    • 子序列1：[2, 1, 6, 5]
    • 子序列2：[8, 4, 3, 7]
    • 对每个子序列进行插入排序。
  3. 间隔 gap = 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 ShellSort(int *a,size_t n)
{
	assert(a);
	int gap = n;
	while(gap > 1)
	{
		gap = gap/3+1; //控制分组
		for(size_t i = 0;i < n-gap;i++)//注意边界条件，避免越界
		{
			int end = i;
			int tmp = a[end+gap];
			while(end >= 0)
			{
				if(a[end] > tmp)
				{
					a[end+gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end+gap] = tmp;
		}
	}
}

【✳】时间复杂度分析

希尔排序的时间复杂度分析涉及到以下几个方面：

1. 间隔序列的选择

希尔排序的效率很大程度上取决于所选择的间隔序列。常见的间隔序列有：

  • 希尔序列：间隔序列为 { n/2, n/4, …, 1 }。
  • Hibbard 序列：间隔序列为 { 1, 3, 7, …, 2^k - 1 }。
  • Knuth 序列：间隔序列为 { 1, 4, 13, 40, …, (3^k - 1) / 2 }。

不同的间隔序列会影响排序的时间复杂度。这里我们以希尔序列为例进行分析。

2. 插入排序的时间复杂度

对于一个长度为 h 的子序列，插入排序的时间复杂度为 O(h^2)。

3. 总时间复杂度

计算方式

假设数组长度为 n，间隔序列为 { n/2, n/4, …, 1 }。在每个间隔 gap 下进行插入排序的时间复杂度可以近似看作 O(n)。

具体分析如下：

  • 当 gap = n/2 时，进行 n/2 次插入排序，每次插入排序的时间复杂度为 O((n/2)^2) = O(n^2/4)。
  • 当 gap = n/4 时，进行 n/4 次插入排序，每次插入排序的时间复杂度为 O((n/4)^2) = O(n^2/16)。
  • 依次类推，直到 gap = 1。

由于每次 gap 变为原来的一半，总的时间复杂度可以表示为：
T(n) = O(n^2/4) + O(n^2/16) + … + O(1)

这实际上是一个几何级数，求和结果为：
T(n) = O(n^2 * (1/4 + 1/16 + … + 1/n^2))

因为这个和趋近于 O(n log^2 n)，所以希尔排序的平均时间复杂度为 O(n log^2 n)。

总结

时间复杂度可以在 O(n^(1.3)) 到 O(n^2) 之间。

常见的间隔序列及其时间复杂度

  1. 希尔序列（Shell Sequence）：间隔序列为 {n/2, n/4, …, 1}。
    • 时间复杂度：O(n^2)
  2. Hibbard 序列：间隔序列为 {1, 3, 7, …, 2^k - 1}。
    • 时间复杂度：O(n^(3/2))
  3. Knuth 序列：间隔序列为 {1, 4, 13, 40, …, (3^k - 1) / 2}。
    • 时间复杂度：O(n^(3/2))
  4. Sedgewick 序列：间隔序列为 {1, 5, 19, 41, 109, …}。
    • 时间复杂度：O(n^(4/3))
  5. Pratt 序列：间隔序列为 {1, 2, 3, 4, 6, 8, 9, …}，即2的幂和3的幂的所有组合。
    • 时间复杂度：O(n log^2 n)

时间复杂度计算示例：Hibbard 序列

假设我们使用 Hibbard 序列，间隔序列为 {1, 3, 7, …, 2^k - 1}。

分析步骤

  1. 间隔序列长度：对于一个长度为 n 的数组，最大间隔 k 满足 2^k - 1 ≈ n，即 k ≈ log_2 n。
  2. 每个间隔下的复杂度：在每个间隔 h 下，插入排序的复杂度为 O(n / h * h) = O(n)。
  3. 总复杂度：对于每个间隔 h，我们需要进行 k 次插入排序。由于 k ≈ log_2 n，总复杂度为 O(n log_2 n)。

然而，由于 Hibbard 序列的实际排序效果，实验结果表明其平均时间复杂度更接近于 O(n^(3/2))。

总结

希尔排序的时间复杂度范围很广，具体取决于所使用的间隔序列。一般来说，时间复杂度可以在 O(n^(1.3)) 到 O(n^2) 之间变化。对于大多数实际应用，使用优化的间隔序列（如 Sedgewick 序列或 Pratt 序列）可以得到较好的时间复杂度，接近 O(n log^2 n)。

参考公式

  • 希尔序列：O(n^2)
  • Hibbard 序列：O(n^(3/2))
  • Knuth 序列：O(n^(3/2))
  • Sedgewick 序列：O(n^(4/3))
  • Pratt 序列：O(n log^2 n)

为什么说希尔排序不稳定！

举个例子来说明这个问题：

假设有以下数组：[3, 3, 1, 2, 2]。

  1. 初始数组： [3, 3, 1, 2, 2]
  2. 选择一个跨度（gap），例如2： 对于跨度为2的子序列，我们有两个子序列：[3, 1, 2]和[3, 2]。
  3. 对每个子序列进行插入排序：
    • 对子序列[3, 1, 2]，排序后为[1, 2, 3]。
    • 对子序列[3, 2]，排序后为[2, 3]。
  4. 合并结果： [1, 2, 2, 3, 3]

在这个例子中，原数组中两个相同的“2”的相对顺序在排序后改变了。原本位于数组后半部分的“2”被移到了前半部分，而前半部分的“2”则保持在后半部分，这说明了希尔排序的不稳定性。

选择排序

**思路分析：**第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前/后位置，下一趟从n-1个元素中选出最小/大的元素并放在最前/后位置。以此类推，经过n-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
//选择排序
void SelectSort(int *a,size_t n)
{
	assert(a);
	size_t left = 0,right = n-1;
	while(left < right)
	{
		size_t min = left,max = left;
		for(size_t i = left;i <= right;i++)
		{
			if(a[i] > a[max])
			{
				max = i;
			}
			if(a[i] < a[min])
			{
				min = i;
			}
		}
		swap(a[min],a[left]);
		if(max == left) //最大值在最左边
			max = min;
		swap(a[max],a[right]);
		--right;
		++left;
	}
}

**总结：**直接选择排序的最好时间复杂度号最坏时间复杂度都是O(n^2)，因为即使数组一开始就是正序的，也需要将两重循环进行完，平均时间复杂度也是O(n^2)，最好的时间复杂度为O(n^2)，空间复杂度为O(1)，因为不占用多余的空间。直接选择排序是一种原地排序并且不稳定的排序算法，优点是实现简单，占用空间小，缺点是效率低，时间复杂度高，对于大规模的数据耗时较长。

为什么说选择排序不稳定！

举个例子来说明选择排序的不稳定性：

假设有以下数组：[4, 2, 3, 2, 1]。

  1. 初始数组： [4, 2, 3, 2, 1]
  2. 第一轮选择最小元素：
    • 当前数组：[4, 2, 3, 2, 1]
    • 最小元素是1，将其与第一个元素4交换：
    • 交换后数组：[1, 2, 3, 2, 4]
  3. 第二轮选择最小元素：
    • 当前数组：[1, 2, 3, 2, 4]
    • 最小元素是2，将其与第二个元素2交换（没有实际变化）：
    • 交换后数组：[1, 2, 3, 2, 4]
  4. 第三轮选择最小元素：
    • 当前数组：[1, 2, 3, 2, 4]
    • 最小元素是2，将其与第三个元素3交换：
    • 交换后数组：[1, 2, 2, 3, 4]

在这个例子中，原数组中两个相同的“2”的相对顺序在排序后改变了。原本位于数组第二个位置的“2”在排序后移动到了数组第三个位置，而原本在第四个位置的“2”则保持在第四个位置，这说明了选择排序的不稳定性。

堆排序

基本概念：

  • 大根堆：根节点最大，常用于获取最大值。
  • 小根堆：根节点最小，常用于获取最小值。

思路分析：

①将长度为n的待排序的数组进行堆有序化构造成一个大顶堆

②将根节点与尾节点交换并输出此时的尾节点

③将剩余的n -1个节点重新进行堆有序化

④重复步骤2，步骤3直至构造成一个有序序列

（升序构建小堆，降序构建大堆）

过程动态图

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 AdjustDown(int *a,size_t root,size_t n)//向下调整算法
{
	size_t parent = root;
	size_t child = parent*2+1;//下标为0的为第一个孩子，所以parent*2+1为下标为左孩子
	while(child < n)
	{
		if(child+1 < n && a[child+1] > a[child])
		{
			++child;//让child指向较大的那个孩子
		}
		if(a[child] > a[parent])
		{
			swap(a[child],a[parent]);
			parent = child;
			child = child*2+1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int *a,size_t n)//升序，建大堆
{
	assert(a);
	int i;
	//从第一个非叶子节点开始，做向下调整，调整完第一个元素为最大元素
	for(i = (n-2)/2;i >= 0;--i)
	{
		AdjustDown(a,i,n);
	}//大堆建成
	int end;
	//交换第一个元素和最后一个元素，然后把交换后的第一个元素往下调整，再成大堆
	//--end，即是缩小范围，每次把最大的换到end的位置
	for(end = n-1;end >= 0;--end)
	{
		swap(a[end],a[0]);
		AdjustDown(a,0,end);
	}
}

总结：堆排序的最好和最差情况时间复杂度都为O(nlog2n)，平均时间复杂度为O(nlog2n)，空间复杂度为O(1)，排序算法不稳定，无需使用多余的空间帮助排序。优点是占用空间较小，时间复杂度较低，缺点是实现较为复杂，并且当待排序序列发生改动时，哪怕是特别小的改动，都需要调整整个堆来维护堆的性质，维护开销较大。

时间复杂度

构建堆的时间复杂度

  • 自底向上的堆化过程：在堆排序中，首先要将无序数组构建成一个最大堆。这一过程的时间复杂度为 O(n)。

排序过程的时间复杂度

  • 删除最大元素并重建堆：将最大堆的根节点（最大值）与最后一个节点交换，然后对剩余的 n−1个元素重新进行堆化。每次堆化的时间复杂度为 O(log⁡n)，因为堆化操作的高度最多为 log⁡2n

这个过程需要进行 n−1 次，因此排序部分的总时间复杂度为：O(nlog2n)

补充下建堆的过程

建堆步骤

堆的性质要求每个节点的值都不小于（最大堆）或不大于（最小堆）其子节点的值。建堆的过程自底向上进行，因为这样可以确保在调整某个节点时，它的子节点已经是堆。

详细步骤

  1. 选择从最后一个非叶子节点开始：因为叶子节点本身已经是一个堆，所以我们只需要调整非叶子节点。最后一个非叶子节点的索引是 ⌊n/2⌋−1，其中 n 是数组的长度。
  2. 自底向上调整堆：从最后一个非叶子节点开始，依次向前遍历每个节点，执行 heapify 操作以确保每个节点都满足堆的性质。

heapify 操作

heapify 是调整堆的核心操作，确保以某个节点为根的子树满足堆的性质。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void heapify(int arr[], int n, int i) {
    int largest = i;       // 初始化 largest 为根节点
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点存在且大于 largest
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果 largest 不是根节点
    if (largest != i) {
        swap(arr[i], arr[largest]); // 交换根节点和最大值节点
        heapify(arr, n, largest);   // 递归地调整受影响的子树
    }
}

建堆的完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void buildMaxHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始自底向上调整堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void heapSort(int arr[], int n) {
    // 建立最大堆
    buildMaxHeap(arr, n);

    // 一个一个地从堆中取出元素，并调整剩余的堆
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆的根节点（最大值）与堆的最后一个元素交换
        swap(arr[0], arr[i]);

        // 调整剩余的堆，使其重新满足最大堆的性质
        heapify(arr, i, 0);
    }
}

示例

假设我们有一个数组[4,10,3,5,1]，建堆过程如下：

  1. 初始数组：[4,10,3,5,1]
  2. 从最后一个非叶子节点 i=1 开始堆化：
    • 当前节点是 10，左子节点是 5，右子节点是 1，没有变化。
  3. 处理根节点 i=0
    • 当前节点是 4，左子节点是 10，右子节点是 3。由于 10 最大，将 4 和 10 交换，得到 [][10, 4, 3, 5, 1][10,4,3,5,1]。
    • 调整后的子树根节点是 4，它没有子节点需要调整。

结果是 [][10, 4, 3, 5, 1][10,4,3,5,1]，这个数组已经是最大堆。

大根堆（Max Heap）实现代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <vector>
#include <stdexcept>

class MaxHeap {
public:
    MaxHeap() {}

    // 插入元素
    void insert(int value) {
        data.push_back(value);
        heapifyUp(data.size() - 1);
    }

    // 删除最大值
    int extractMax() {
        if (data.empty()) {
            throw std::runtime_error("Heap is empty");
        }
        int maxValue = data[0];
        data[0] = data.back();
        data.pop_back();
        heapifyDown(0);
        return maxValue;
    }

    // 获取最大值
    int getMax() const {
        if (data.empty()) {
            throw std::runtime_error("Heap is empty");
        }
        return data[0];
    }

    // 打印堆
    void printHeap() const {
        for (int value : data) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }

private:
    std::vector<int> data;

    // 向上调整
    void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (data[index] > data[parentIndex]) {
                std::swap(data[index], data[parentIndex]);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 向下调整
    void heapifyDown(int index) {
        int size = data.size();
        while (index < size) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largest = index;

            if (leftChild < size && data[leftChild] > data[largest]) {
                largest = leftChild;
            }
            if (rightChild < size && data[rightChild] > data[largest]) {
                largest = rightChild;
            }
            if (largest != index) {
                std::swap(data[index], data[largest]);
                index = largest;
            } else {
                break;
            }
        }
    }
};

// 示例用法
int main() {
    MaxHeap heap;
    heap.insert(10);
    heap.insert(20);
    heap.insert(15);
    heap.insert(30);
    heap.insert(25);

    std::cout << "Heap elements: ";
    heap.printHeap();

    std::cout << "Max value: " << heap.extractMax() << std::endl;
    std::cout << "Heap after extracting max: ";
    heap.printHeap();

    return 0;
}

快速排序

本质上快速排序把数据划分成几份，所以快速排序通过选取一个关键数据，再根据它的大小，把原数组分成两个子数组：第一个数组里的数都比这个主元数据小或等于，而另一个数组里的数都比这个主元数据要大或等于。

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
#include <iostream>
#include <vector>

// 辅助函数，用于交换两个元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 分区函数
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最右边的元素作为基准
    int i = low - 1;  // i指向小于pivot的最后一个元素

    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;  // 返回pivot的正确位置
}

// 快速排序递归函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取分区点
        quickSort(arr, low, pi - 1);  // 排序左边部分
        quickSort(arr, pi + 1, high);  // 排序右边部分
    }
}

// 打印数组
void printArray(const std::vector<int>& arr) {
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    std::cout << "Sorted array: \n";
    printArray(arr);
    return 0;
}

vector版本的/手撕快排版本

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
#include<bits/stdc++.h>

using namespace std;
void quickSort(vector<int> &nums,int left,int right){
	if(left>=right) return ;
	int i=left-1;
	int j=right+1;
	int tmp=nums[left+rand()%(right-left+1)];
	while(i<j){
		while(nums[++i]<tmp) ;
		while(nums[--j]>tmp) ;
		if(i<j){
			swap(nums[i],nums[j]);
		}
	}
	quickSort(nums,left,j);
	quickSort(nums,j+1,right);
}
void sortFun(vector<int> &nums){
	quickSort(nums,0,nums.size()-1);
	return ;
}
signed main(){
	vector<int> num={1,4,2,3,5,6,3,2,5,6,10};
	sortFun(num);
	for(auto resi:num) cout<<resi<<" ";
	return 0;
}

数组中第 K 大的数：可以用快排实现，也可以用优先队列实现。

举例：

假设我们有数组 arr = {10, 7, 8, 9, 1, 5}，我们调用 partition(arr, 0, 5)。

  • 初始状态：pivot = 5，i = -1。
  • 遍历数组：
    • j = 0，arr[j] = 10，大于 pivot，不交换，i 仍为 -1。
    • j = 1，arr[j] = 7，大于 pivot，不交换，i 仍为 -1。
    • j = 2，arr[j] = 8，大于 pivot，不交换，i 仍为 -1。
    • j = 3，arr[j] = 9，大于 pivot，不交换，i 仍为 -1。
    • j = 4，arr[j] = 1，小于 pivot，交换 arr[0] 和 arr[4]，i = 0。
  • 交换基准元素：
    • 将 arr[1] 和 arr[5] 交换，得到 arr = {1, 5, 8, 9, 10, 7}。
  • 返回值：
    • 返回 i + 1 = 1。

通过上述步骤，我们将数组划分为两部分：{1} 和 {8, 9, 10, 7}，其中基准元素 5 位于正确的位置。

总结：平均时间复杂度为O(nlog2n)，最坏时间复杂度为O(n^2)，空间复杂度为O(nlog2n），排序算法不稳定。

补充：

  • 选择的枢轴（pivot）不理想：如果每次选择的枢轴总是数组中的最大或最小元素，快速排序将退化为最坏情况。例如，对于一个已经有序的数组，如果每次选择第一个元素或最后一个元素作为枢轴，快速排序会产生极度不平衡的划分，导致最坏时间复杂度 O(n^2)。

    举个例子，假设我们总是选择第一个元素作为枢轴：

    • 对于一个已经有序的数组 [1, 2, 3, 4, 5]，第一次选择 1 作为枢轴，将数组划分为 [] 和 [2, 3, 4, 5]。
    • 接下来，选择 2 作为枢轴，将数组划分为 [] 和 [3, 4, 5]。
    • 继续下去，每次的划分都会导致一个子数组为空，另一个子数组包含剩余的所有元素。

    这样，每次递归调用都会减少一个元素，导致总体时间复杂度变为 O(n^2)。

  • 重复元素很多：当数组中有很多重复元素时，特别是所有元素都相同时，如果选择的枢轴总是那些重复的元素，快速排序也会退化。例如，对于一个全是相同元素的数组 [5, 5, 5, 5, 5]，如果选择枢轴为 5，每次划分后的两个子数组大小不变，这会导致快速排序退化为最坏时间复杂度。

为了避免快速排序退化为 O(n^2)，常用的改进方法包括：

  • 随机选择枢轴：在每次划分时随机选择一个元素作为枢轴，这样可以大大减少出现最坏情况的概率。
  • 三数取中法（Median of Three）：选择第一个元素、中间元素和最后一个元素的中位数作为枢轴。
  • 混合排序算法：当数组大小较小时，切换到插入排序等其他高效的排序算法，因为在小数组上，插入排序的性能通常优于快速排序。

✳✳✳快速排序怎么变成稳定的？

方法 1：修改分区策略，使用辅助数组

一种直接且简单的方法是使用辅助数组来实现稳定性。我们可以在划分过程中，将与基准值相等的元素分配到一个独立的临时数组中，确保它们的相对顺序保持不变。具体步骤如下：

  1. 使用辅助数组来暂存元素，以保证相同值的元素在分区时不会改变相对顺序。
  2. 分区时，将小于基准元素的部分放在左侧，等于基准元素的部分放在中间，大于基准元素的部分放在右侧。
  3. 最后，将辅助数组合并回来。由于等于基准值的元素在暂存时保持了顺序，稳定性得以保证。
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
#include <iostream>
#include <vector>

void stableQuickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[right];  // 选择最右边的元素作为基准
    std::vector<int> less, equal, greater;

    // 分区
    for (int i = left; i <= right; ++i) {
        if (arr[i] < pivot) {
            less.push_back(arr[i]);
        } else if (arr[i] == pivot) {
            equal.push_back(arr[i]);
        } else {
            greater.push_back(arr[i]);
        }
    }

    // 将分区后的元素重新合并回原数组
    int index = left;
    for (int val : less) arr[index++] = val;
    for (int val : equal) arr[index++] = val;
    for (int val : greater) arr[index++] = val;

    // 递归排序左半部分和右半部分
    stableQuickSort(arr, left, left + less.size() - 1);
    stableQuickSort(arr, right - greater.size() + 1, right);
}

int main() {
    std::vector<int> arr = {3, 3, 1, 4, 2, 5, 3, 1};
    stableQuickSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

方法 2：使用链表（或索引数组）

另一种方法是基于链表或索引数组。我们可以保持元素的相对顺序，通过存储元素的原始位置来确保相同元素在快速排序的过程中不会被打乱。

基于链表的示例实现：

  1. 使用一个链表来存储排序的元素。
  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
#include <iostream>
#include <list>
#include <vector>

void stableQuickSort(std::list<int>& arr) {
    if (arr.size() <= 1) return;

    int pivot = arr.back();  // 使用最后一个元素作为基准
    std::list<int> less, equal, greater;

    // 分区
    for (int val : arr) {
        if (val < pivot) {
            less.push_back(val);
        } else if (val == pivot) {
            equal.push_back(val);
        } else {
            greater.push_back(val);
        }
    }

    // 递归排序左右部分
    stableQuickSort(less);
    stableQuickSort(greater);

    // 合并结果
    arr.clear();
    arr.splice(arr.end(), less);
    arr.splice(arr.end(), equal);
    arr.splice(arr.end(), greater);
}

int main() {
    std::list<int> arr = {3, 3, 1, 4, 2, 5, 3, 1};
    stableQuickSort(arr);

    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

归并排序

思路分析：

当一个数组左边有序，右边也有序，那合并这两个有序数组就完成了排序。如何让左右两边有序了？用递归！这样递归下去，合并上来就是归并排序。

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
//归并排序
void _MergeSort(int *a, int left, int right)
{
	assert(a);
	if(left >= right)
		return;
 
	int mid = left + ((right-left) >> 1);
 
	_MergeSort(a, left, mid);
	_MergeSort(a, mid+1, right);
 
	int *tmp = new int[right-left+1];//开辟同原数组大小的辅助空间
	
	int begin1 = left;//左区间的开头
	int begin2 = mid+1;//右区间的开头
 
	int cur = 0;//辅助空间的开头
 
	while(begin1 <= mid && begin2 <= right)
	{
		if(a[begin1] < a[begin2])
		{
			tmp[cur++] = a[begin1++];
		}
		else
		{
			tmp[cur++] = a[begin2++];
		}
	}
	//将余下的直接放入辅助空间
	while(begin1 <= mid)
	{
		tmp[cur++] = a[begin1++];
	}
	while(begin2 <= right)
	{
		tmp[cur++] = a[begin2++];
	}
	
	//将tmp数组的值全部拷贝到a数组里面
	for(int i = 0; i < cur; i++)
	{
		a[left+i] = tmp[i];
	}
	delete[] tmp;//释放自己申请的空间
}
 
void MergeSort(int *a, size_t n)
{
	assert(a);
	_MergeSort(a, 0, n-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
#include<bits/stdc++.h>

using namespace std;

void mergefun(vector<int> &nums,int l,int mid,int r){
	vector<int> tmp;
	int i=l;
	int j=mid+1;
	while(i<=mid&&j<=r){
		if(nums[i]<nums[j]){
			tmp.push_back(nums[i++]);
		}else{
			tmp.push_back(nums[j++]);
		}
	}
	while(i<=mid) tmp.push_back(nums[i++]);
	while(j<=r) tmp.push_back(nums[j++]);
	for(int i=0;i<tmp.size();i++) nums[i+l]=tmp[i];
	return ;
}
void mergeSort(vector<int> &nums,int l,int r){
	if(l==r){
		return ;
	}else{
		int mid=(l+r)/2;
		mergeSort(nums,l,mid);
		mergeSort(nums,mid+1,r);
		mergefun(nums,l,mid,r);
	}
}
void SortFun(vector<int> &nums){
	if(nums.size()<2) return ;
	int l=0;
	int r=nums.size()-1;
	mergeSort(nums,l,r);
}

signed main(){
	vector<int> nums{1,3,5,6,2,2,5,7,3,1};	
	SortFun(nums);
	for(auto num:nums) cout<<num<<" ";
	return 0;
}

总结：平均和最坏、最好时间复杂度为O(nlog2n)，空间复杂度O(n)，排序算法稳定。

一个经典问题：数组中的逆序对（hard）

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
class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int res = mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid + 1, right);

        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            tmp[k] = nums[k];
        }
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = tmp[j++];
            } else if (j == right + 1 || tmp[i] <= tmp[j]) {
                nums[k] = tmp[i++];
            } else {
                nums[k] = tmp[j++];
                res += mid - i + 1;
            }
        }

        return res;
    }

    int reversePairs(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmp(len);
        return mergeSort(nums, tmp, 0, len - 1);
    }
};

总结

image-20240701233431874

参考资料：

排序算法（七大经典排序算法）

https://segmentfault.com/a/1190000021638663#item-7-27