C语言实现快速排序算法-平芜编程栈

1. 什么是快速排序算法

快速排序的核心思想是通过分治法（Divide and Conquer）来实现排序。
算法的基本步骤是:
1. 选择一个基准值（通常是数组中的某个元素），将数组分成两部分，使得左边的部分所有元素都小于基准值，右边的部分所有元素都大于基准值。
2. 对这两部分分别进行递归排序，直到整个数组有序。

那么，该算法为什么叫做快速排序算法呢？

快速排序算法之所以被称为“快速”，是因为它在大多数情况下都能够快速地完成排序。在平均情况下，其时间复杂度为O(nlogn)，其中n为数组的大小。

此外，快速排序还具有原地排序的特点，即不需要额外的辅助空间，只需对原始数组进行原地操作。这些优点使得快速排序成为了排序问题中的一种首选算法。

2. 单趟排序

单趟排序指的就是将数组分为两部分的算法。

对于实现这一步，我们有三种思路。

2.1 霍尔法

霍尔并无什么特殊含义，只是因为最早发现快速排序算法的人叫霍尔，这是他的实现方法。

思路：

1. 先选定一个基准值key（一般选择首元素）。
2. 定义两个指针left和right，分别指向数组的左右两端。
3. left从左往右遍历，寻找大于基准值的元素，right从右往左遍历，寻找小于基准值的元素。
4. 如果left与right未相遇，那么就交换两指针指向的元素。
5. 如果left与right相遇，那么就让key指向的元素与right指向的元素交换。

代码

//霍尔法 int PartSort_1(int* arr, int left, int right) { int key = left; while (left < right) { while (left < right && arr[right] >= arr[key]) { right--; } while (left < right && arr[left] <= arr[key]) { left++; } if (left < right) swap(&arr[left], &arr[right]); } swap(&arr[key], &arr[left]); return left; }

注意事项（如何保证right和left共同指向的元素与key指向的元素交换是合理的）

1. 如果选取的基准值为首元素，那么在外层循环的一次循环中，一定要让right先进行移动，这样可以确保共同指向的元素是小于或等于基准值的。
2. 如果选取的基准值为最后一个元素，则与上面相反。

2.2 挖坑法

核心思想与霍尔法相同，但是表现形式有所差异。

思路

顾名思义，我们将基准值单独用变量进行存放，而将基准值原本所在的位置空出来成为一个坑（我们将其称作hole）。

1. right先进行遍历，如果发现有小于基准值的元素，则将该元素填入hole中，然后right指向的位置成为新的hole。(假设F小于key)

2. 然后left再进行遍历，如果发现有大于基准值的元素，则将该元素填入hole中，然后left指向的位置成为新的hole。（假设B大于key）

3. 以此类推，当left与right相遇时，将key填入hole中即可。

代码

//挖坑法 int PartSort_2(int* arr, int left, int right) { int key = arr[left]; int hole = left; while (left < right) { while (left < right && arr[right] >= key) { right--; } arr[hole] = arr[right]; hole = right; while (left < right && arr[left] <= key) { left++; } arr[hole] = arr[left]; hole = left; } arr[hole] = key; return hole; }

注意事项

对于这个方法来说，洞在谁那边，谁就后开始遍历。

2.3 前后指针法

思路

1. 定义两个指针，prev和cur，prev所指向的以及之前的元素就是小于基准值的元素，cur用于遍历数组。
2. 如果cur找到小于基准值的元素，让prev++，然后交换prev指向的元素和cur指向的元素。
3. 让基准值与prev指向的元素进行交换。

代码

//前后指针 int PartSort_3(int* arr, int left, int right) { int key = left; int prev = left; int cur = left + 1; while (cur <= right) { //arr[cur]小于基准值就交换 if (arr[cur] <= arr[key] && ++prev != cur) { swap(&arr[prev], &arr[cur]); } cur++; } swap(&arr[key], &arr[prev]); return prev; }

注意事项

如果选取的基准值为首元素，则在最后让prev指向的元素与基准值交换；如果选区的基准值为最后一个元素，则在最后让prev指向的下一个元素与基准值交换。

3. 快速排序算法的递归实现

按照第一部分的介绍，我们很容易的到下面的代码。

void QuickSort(int* arr, int begin, int end) { if (begin >= end) return; int key = PartSort_3(arr, begin, end); QuickSort(arr, key + 1, end);//排右边 QuickSort(arr, begin, key - 1);//排左边 }

4. 快速排序算法的优化

4.1 层次优化

当数据量十分巨大时，使用递归实现的快速排序算法会由于调用函数次数过多而导致程序效率下降。

由于递归的逻辑结构像是一个树状图，所以在递归的层次较深时，每次进到下一层都会调用上一层两倍数量的函数。

众所周知，是一个极其可怕的东西，那么我们能不能在层次较深，所需排序的数组长度较短时，转而使用其他经典的排序算法呢？

于是我们做出了如下的优化：

void QuickSort(int* arr, int begin, int end) { if (begin >= end) return; if (end - begin <= 8) { InsertSort(arr + begin, end - begin + 1); return; } int key = PartSort_3(arr, begin, end); QuickSort(arr, key + 1, end);//排右边 QuickSort(arr, begin, key - 1);//排左边 }

当数组长度小于等于9时，我们采用插入排序来进行排序（不止插入排序，其他排序也可）。

//插入排序 void InsertSort(int* arr, int len) { for (int i = 1; i < len; i++) { int j = i; while (j > 0 && arr[j] < arr[j - 1]) { swap(&arr[j], &arr[j - 1]); j--; } } }

4.2 基准值的选择

在上面的代码中，我们默认左端的值为基准值，这种选法在大多数情况下没有什么问题，但是在元素本就有序的情况下，每趟排序调整完之后，基准值的左边无元素，剩余元素全在基准值的右边。

这就使得快速排序算法的过程变得与冒泡排序十分相似。

于是，在取基准值这件事上，我们最好做出优化。

我们采取得方式是：取区间左端，中间，右端三个数中居中的值。

int GetMidInThree(int* arr, int left, int right) { int mid = (left + right) / 2; if (arr[left] < arr[right]) { if (arr[mid] < arr[left]) return left; else if (arr[right] < arr[mid]) return right; else return mid; } else { if (arr[mid] < arr[right]) return right; else if (arr[left] < arr[mid]) return left; else return mid; } } //快速排序 void QuickSort(int* arr, int begin, int end) { if (begin >= end) return; if (end - begin <= 8) { InsertSort(arr + begin, end - begin + 1); return; } int mid = GetMidInThree(arr, begin, end); swap(&arr[begin], &arr[mid]); int key = PartSort_3(arr, begin, end); QuickSort(arr, key + 1, end);//排右边 QuickSort(arr, begin, key - 1);//排左边 }

5. 快速排序算法的非递归实现

区别每一次函数调用的关键信息就是其左端点与右端点，除此之外的信息都是可以共用的。

所以，为了方便理解，我们用一个结构体来表示每次函数调用：

typedef struct PartSort { int left; int right; }PartSort;

进行一次函数调用------出栈
进行一次函数调用------入栈

// 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right) { Stack st; PartSort range = { left, right }; STInit(&st); STPush(&st, range); while (!STEmpty(&st)) { range = STTop(&st); STPop(&st); if (range.left >= range.right) continue; if (range.right - range.left <= 8) { InsertSort(a + range.left, range.right - range.left + 1); continue; } int mid = GetMidInThree(a, range.left, range.right); swap(&a[range.left], &a[mid]); int key = PartSort_1(a, range.left, range.right); STPush(&st, (PartSort) { range.left, key - 1 }); STPush(&st, (PartSort) { key + 1, range.right }); } STDestroy(&st); }