快速排序(C语言简单实现)
快速排序(Quick Sort)是冒泡排序的升级版。基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。对快速排序过程的理解:https://www.runoob.com/w3cnote/quick-sort.html
/* 对顺序表L作快速排序 */
void QuickSort(SqList *L){
QSort(L, 1, L->length);
}
/* 对顺序表L中的子序列L->r[low.high]作快速排序 */
void QSort(SqList *L, int low, int high){
int pivot;
if(low<high){
pivot = Partition(L, low, high); //将L->r[low..high]一分为二,算出枢轴值pivot
QSort(L, low, pivot-1); //对低子表递归排序
QSort(L, pivot+1, high); //对高子表递归排序
}
}
/* 交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大(小)于它 */
int Partition(SqList *L, int low, int high){
int pivotkey;
pivotkey = L->r[low]; //用表的第一个记录作枢轴记录
while(low < high){
//从表的两端交替向中间扫描
while(low < high && L->r[high] >= pivotkey)
high--;
swap(L, low, high); //将比枢轴记录小的记录交换到低端
while(low < high && L->r[low] <= pivotkey)
low++;
swap(L, low, high); //
将此枢轴记录大的记录交换到高端
}
return low; //返回枢轴所在位置
}
复杂度分析
快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。
在最优情况下,Partition每次都划分得很均匀,如果排序n
个关键字,其递归树的深度就为log2(n)+1
向下取整,即仅需递归log2(n)
次,需要时间为T(n)
的话,那么第一次Partition应该是需要对整个数组扫描一边,作n
次比较,然后,获得的枢轴将数组一分为二,各自还需要T(n/2)
的时间(最好情况下才平分)。综合起来,最优情况下,快速排序算法的时间复杂度为O(nlogn)
。
最坏情况下,待排序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,会是一棵斜树
。此时需要执行n-1次递归调用,且第i
次需要经过n-1
次关键字的比较才能找到第i
个记录,也就是枢轴的位置,因此最终比较次数为O(n^2)
。
平均情况下,时间复杂度为O(nlogn)
。
空间复杂度,主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2(n)
,其空间复杂度也就为O(logn)
,最坏情况,需要进行n-1
递归调用,其空间复杂度为O(n)
,平均情况,空间复杂度也为O(logn)
。
因为是跳跃着比较和交换的,所以,快速排序时一种不稳定的排序方法。
快速排序优化
优化选取枢轴
三数取中法:即取三个关键字先进行排序,将中间数作为枢轴,一般取左端,右端和中间三个数,也可以随机取,这样子至少这个中间数一定不会是最小或者最大。从概率上来说,取到三个数均为最小或最大的可能性微乎其微,因此中间数位概率大大提高。由于整个序列是无序状态,随机选取三个数和从左中右取三个数其实是一样的,而且随机数生成器本身还会带来时间上的开销,因此随机生成不予考虑。
修改代码,在Partition函数代码的第3和4行之间增加一段代码:
int pivotkey;
int m = low&#