排序算法

Posted on Edited on

快速排序

tips：为什么快速排序算法把基准元素名称定义为pivot

在快速排序算法中，“pivot”（基准元素）是一个用来将数据集分割成两部分的元素。所有比基准元素小的元素都被放到它的左边，而所有比它大的元素都被放到它的右边。这就是为什么它被称为 “pivot”（枢轴），因为它在排序过程中起到了中心轴的作用，就像一个旋转门或者天平的支点那样。

在一次快速排序的分割操作中，我们从数组的一端开始，将所有比pivot小的元素放到左边，比pivot大的元素放到右边。这个过程称为分区操作（partitioning）。经过分区操作后，pivot元素会位于数组的某个位置，它左边的所有元素都不大于它，它右边的所有元素都不小于它，所以它就到了排序后应该在的位置。

然后我们可以递归地对pivot左边的元素和右边的元素分别进行快速排序，这样整个数组就会变得有序。

所以，pivot元素在快速排序中起到了关键的作用，它是算法的核心部分。

代码实现

以下是一个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
#include <iostream>
#include <vector>

// 交换函数
void swap(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}

// 快速排序的一次划分操作
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];   // 选择最右边的元素作为基准元素
    int i = low - 1;

    for(int j = low; j <= high-1; j++) {
        if(arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return (i + 1);
}

// 快速排序函数
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);  // 对右侧子数组递归执行快速排序
    }
}

// 主函数
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";
    for(int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

在这个程序中，partition函数是快速排序的核心，它实现了一次划分操作。我们首先选择一个基准元素（这里选择的是数组最右侧的元素），然后将所有比基准元素小的元素移动到数组的左侧，比基准元素大的元素移动到数组的右侧。

quickSort函数是一个递归函数，它首先调用partition函数进行一次划分操作，然后对基准元素左侧和右侧的子数组分别递归调用quickSort函数进行排序。这个过程会一直递归下去，直到子数组的大小为1或0，此时子数组已经是有序的，递归结束。

在实现代码时犯了一个小错误

在partition函数实现时，最后一步的交换过程中，应该是swap(arr[i+1], arr[high])，而我第一次实现时写成了swap(arr[i+1], pivot)。为什么这样不行呢？貌似看起来是合理的，因为我们在一开始就有语句：int pivot = arr[high];但是恰巧问题就是出现在了这里，因为我们要交换的是vector容器里的元素，我们在实现int pivot = arr[high];这个语句时pivot只是拿到了arr[high]的值，因此我们并没有实际交换arr[i+1]和arr[high]，所以排序后的结果肯定是错的。（因此，定义成这样int& pivot = arr[high]，就可以这样写：swap(arr[i+1], pivot)）

堆排序

堆排序是一种基于堆的排序算法。它使用了一种叫做堆的数据结构。堆有两种类型：最大堆和最小堆。最大堆的特性是父节点的值大于或等于其所有子节点的值，最小堆的特性是父节点的值小于或等于其所有子节点的值。

堆排序的基本步骤如下：

  1. 建立最大堆：将待排序序列构造成一个最大堆，这样就能保证整个序列的最大值就是堆顶的根节点。
  2. 交换数据：将根节点与最后一个元素交换位置，然后断开（排除）最后一个元素。
  3. 重建最大堆：通过调整使剩余元素重新构成最大堆。
  4. 重复步骤2~3，直到整个序列有序。

这里挂一个讲堆排序很好的博客，一定要耐心阅读！引用链接

堆排序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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void heapify(vector<int>& arr, int n, int i) {
	int largest = i;   //从largest往下开始建立大根堆，暂不考虑largset往上的数据
	int left = 2 * i + 1;
	int right = 2 * i + 2;

	if (left < n && arr[left] > arr[largest]) {
		largest = left;
	}

	if (right < n && arr[right] > arr[largest]) {
		largest = right;
	}

	if (largest != i) {
		swap(arr[i], arr[largest]);
		heapify(arr, n, largest);    
	}
}

void heapSort(vector<int>& arr) {
	int n = arr.size();

	for (int i = n / 2 - 1; i >= 0; --i) {
		heapify(arr, n, i);
	}

	for (int i = n - 1; i >= 0; --i) {
		swap(arr[0], arr[i]);
		heapify(arr, i, 0);
	}
}

int main() {
	vector<int> arr = { 10, 7, 8, 9, 1, 5, 5, 5, 5 };
	heapSort(arr);
	for (auto a : arr) {
		cout << a << " ";
	}
	cout << endl;
	return 0;
}
自己初步实现时没有彻底弄明白堆排序，所以有如下这个问题

为什么第一次需要

1
2
3
for (int i = n / 2 - 1; i >= 0; --i) {
		heapify(arr, n, i);
	}

而从i=n-1开始，就直接 heapify(arr, i, 0);就没有i=n/2-1的这个过程

这是因为我们在开始的时候是在创建最大堆。在创建最大堆的过程中，我们需要从最后一个非叶子节点（即 n / 2 - 1）开始，然后向前遍历到根节点（即 0），对每个节点进行下沉操作，确保其满足最大堆的性质。这是创建最大堆的过程。

然后，我们进入排序的步骤，每次将当前最大的元素（即堆顶元素）与当前堆的最后一个元素交换，然后断开最后一个元素（即排除最后一个元素，使堆的大小减小1），然后再将新的堆顶元素进行下沉操作，确保剩余元素还是一个最大堆。这个过程一直持续到整个堆的元素都被排除，即整个数组都被排序。

因此，在排序的过程中，我们不需要再从 n / 2 - 1 开始了，因为除了堆顶元素以外，其他元素都满足最大堆的性质，所以我们只需要将新的堆顶元素进行下沉操作即可，也就是 heapify(arr, i, 0);。