基本快速排序
快速排序和冒泡排序同属交换排序,但是由于关键字的比较和交换是跳跃进行的,所以是不稳定的排序。
快速排序的基本思想:通过一趟排序讲待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对着两部分记录进行排序,以达到整个序列有序的目的。
C++代码
/**********************************/ /***********快速排序***************/ /**********************************/ int Partition(ElemType a[],int low,int high) { //将选取的pivotkey不断交换,将比它小的换到它的左边,比它大的换到它的右边, //它也在交换中不断更改自己的位置 int pivotkey; pivotkey = a[low]; while(low < high) { while(low < high && a[high] >= pivotkey) high--; swap(a,low,high); while(low < high && a[low] <= pivotkey) low++; swap(a,low,high); } return low; } void QSort(ElemType a[],int low,int high) { int pivot; if(low < high) { pivot = Partition(a,low,high); QSort(a,low,pivot-1); QSort(a,pivot+1,high); } } void QuickSort(ElemType a[],int n) { QSort(a,1,n); }
Python代码
#---------------# #--Quick sort1--# #---------------# def partition(arr,low,high): pivotkey = arr[low] while low < high: while low < high and arr[high] >= pivotkey: high -= 1 swap(arr,low,high) while low < high and arr[low] <= pivotkey: low +=1 swap(arr,low,high) return low def qsort(arr,low,high): if low < high: pivot = partition(arr,low,high) qsort(arr,low,pivot-1) qsort(arr,pivot+1,high) def quick_sort(arr): arrlen = len(arr) qsort(arr,0,arrlen-1)
快速排序复杂度分析
快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。
最优情况下,时间复杂度为O(nlogn),空间复杂度O(logn)。
最坏情况下,待排序的序列为正序或逆序,时间复杂度为O(n^2),空间复杂度O(n)。
快速排序优化
1.优化选取pivot
三数取中法,即去三个关键字先进行排序,讲中间数作为pivot,一般取左端、右端和中间,也可以随机选取。
int pivotkey; int m = low+(high-low)/2; if(a[low]>a[high]) swap(a,low,high); if(a[m]>a[high]) swap(a,m,high); if(a[low]<a[m]) swap(a,low,m); pivotkey = a[low];//此时已为左中右三个关键字的中间值
2.优化不必要的交换
int Partition(ElemType a[],int low,int high) { //将选取的pivotkey不断交换,将比它小的换到它的左边, //比它大的换到它的右边,它也在交换中不断更改自己的位置 int pivotkey; pivotkey = a[low]; while(low < high) { while(low < high && a[high] >= pivotkey) high--; a[low] = a[high];//采用替换而不是交换的方式 while(low < high && a[low] <= pivotkey) low++; a[high] = a[low]; } a[low] = pivotkey;//最后赋值回去 return low; }
3.优化小数组时的排序方案
改进QSort,使得其在high-low不大于某个常数时(7或者50,实际调节),就使用直接插入排序,保证最大化的利用两种排序。
4.优化递归操作
如果排序的序列划分极端不平衡,递归深度讲趋近于n,而不是平衡时的logn,这不仅是速度快慢的问题,栈的大小也是有限的。
对QSort实现尾递归。
void QSort(ElemType a[],int low,int high) { int pivot; //if --> while while(low < high) { pivot = Partition(a,low,high); QSort(a,low,pivot-1); low = pivot+1;//实现尾递归 } }
采用迭代而不是递归的方法缩减堆栈深度,提高了整体性能。