动易政府网站源代码qq群推广链接

基本思想

快速排序（Quick Sort），本质上是对冒泡排序的改进，以从小到大排序为例，每趟排序将待排的数据记录分割成两个子数据记录，其中前一半的数据记录关键字比后一半的数据记录关键字小，这样递归分别对两个子数据记录继续分割排序，最终形成完整的有序数据记录。

理解：冒泡排序相当于每次排序后，前面的数据记录关键子都比最后位置的数据记录关键字小，快速排序只要求每次排序后，以某个数据记录关键字为界，前面的一半比后面的一半小即可，这里的某个数据记录称为 枢轴或支点记录。

快速排序时间复杂度是O(nlogn)，在基于比较的内部排序算法中，其平均时间性能最好，它是一种不稳定的内部排序算法。快速排序实现需要栈空间，空间复杂度是(logn)，最坏情况下是O(n)。

当初始序列为从小到大有序时，每次如果选择第一个数据记录作为枢轴，将退化成冒泡排序，最坏的时间复杂度是O(n^2)。因此可以比较数据记录第一个记录、中间记录、最后一个记录关键字大小，选择中间值作为枢轴，可以改善最坏情况下时间性能。

举例来说：

例如：给定10个整数：(4,3,1,2,6,5,0,9,8,7) 从小到大排序。

第一趟子排序：针对整个数据记录(4,3,1,2,6,5,0,9,8,7)。

选择4作为枢轴记录，将比4小的都交换到前面，大的交换到后面。

最终结果是(0,3,1,2,4,5,6,9,8,7)。

很明显，分成两个部分(0,3,1,2)和(5,6,9,8,7)，其中4位置已经有序，不用再排。

第二趟子排序：分别针对(0,3,1,2)和(5,6,9,8,7)两个子数据记录序列。

对于(0,3,1,2)，选择0作为枢轴，得到(0,3,1,2)，分成两个部分，前面部分为空，后面部分为(3,1,2)，0已有序。最终的序列是(0,3,1,2,4,5,6,9,8,7)。

对于(5,6,9,8,7)，选择5作为枢轴，得到(5,6,9,8,7)，分成两个部分，前面部分为空，后面部分为(6,9,8,7)，其中5已经有序。最终的序列是(0,3,1,2,4,5,6,9,8,7)。

第三趟子排序：分别针对(3,1,2)和(6,9,8,7)两个子数据记录序列。

对于(3,1,2)，选择3作为枢轴，得到(2,1,3)，分成两个部分，后面部分为空，前面部分为(2,1)，3已有序。最终的序列是(0,2,1,3,4,5,6,9,8,7)。

对于(6,9,8,7)，选择6作为枢轴，得到(6,9,8,7)，分成两个部分，前面部分为空，后面部分为(9,8,7)，其中6已经有序。最终的序列是(0,3,1,2,4,5,6,9,8,7)。

....

很明显，一趟子排序后，枢轴记录将在整个数据记录序列中有序，不断划分子序列，直到序列为空或1个数据记录时，将结束划分，整个数据记录序列有序。

代码实现（递归实现）

实现要点：利用函数递归实现，快速排序算法需要两个子函数实现，一个子函数实现按照枢轴记录划分整个序列，另一个子函数对划分的两部分序列进行递归排序。

/*
#include <stdio.h>
// 对给定的待排记录序列划分，返回枢轴记录位置 
int partition(int a[], int low, int high)
{// 选择第一个关键字作为枢轴 int t = a[low];while(low < high){while(low < high && a[high] >= t) high--;a[low] = a[high];while(low < high && a[low] <= t)low++;  a[high] = a[low];  }a[low] = t;return low;
}void qsort(int a[], int low, int high)
{if(low < high){int t = partition(a, low, high);qsort(a, low, t-1);qsort(a, t+1, high);}
}void quick_sort(int a[], int length)
{qsort(a, 0, length-1);
} int main(void)
{int a[10] = {4,3,1,2,6,5,0,9,8,7};quick_sort(a,10);int i;for(i=0; i<10; i++)printf("%d ", a[i]);return 0;
}

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。