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大于key3. 以此类推当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和curprev所指向的以及之前的元素就是小于基准值的元素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); }6. 总结单趟排序算法用哪个快速排序递归还是非递归层次较深时换用什么排序算法一般来说插入排序是最好的这些都是可以自由组合的。时间复杂度空间复杂度空间复杂度主要是函数调用对栈的占用。