基本思想
快速排序（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，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。
网友评论