|
四种优化方式 快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序，这是优化快速排序就很有必要了。 优化在Patition函数中进行： ![]()
一、优化选取基准点：三数取中法即，将排序区间的两个端点与中点三个数中居中的数调整为基准点。 在Patition()函数中while循环前加入： [cpp] view plain copy
print?![]() ![]()
- int mid=low+(high-low)/2;
- if(arr[low]>arr[high])
- swap(&arr[low],&arr[high]);
- if(arr[mid]>arr[high])
- swap(&arr[mid],&arr[high]);
- if(arr[mid]>arr[low])
- swap(&arr[mid],&arr[low]);
二、省去不必要的交换
Patition函数中频繁地交换其实有些是不必要的，可以省去，只用赋值就可以了 [cpp] view plain copy
print?![]() ![]()
- pointKey=arr[low];
- while(low<high)
- {
- while(low<high&&pointKey<=arr[high]) high--;
- arr[low]=arr[high];
- while(low<high&&pointKey>=arr[low]) low++;
- arr[high]=arr[low];
- }
- arr[low]=pointKey;
- return low;
三、优化小数组时的排序方案快速排序在序列较长的数组排序时效率较高。我们可以对长度大于k的子序列递归调用快速排序，让原序列基本有序，而小于k时采用插入排序。实验证明，k取值为7时,改进算法的性能最佳。 (等待补充) 四、优化递归操作使递归变为尾递归，节省栈空间。 ![]()
| 
楼主
标题置顶
标题高亮
