快排的优化策略

1、快速排序的基本思想： 
快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2、快速排序的三个步骤： 
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot） 
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大 
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

3、选择基准的方式： 
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。

最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列

我们介绍三种选择基准的方法：(3种)

方法(1)：固定位置

思想：取序列的第一个或最后一个元素作为基准

基本的快速排序

int SelectPivot(int arr[],int low,int high)  
{  
    return arr[low];//选择选取序列的第一个元素作为基准  
}  

注意：基本的快速排序选取第一个或最后一个元素作为基准。但是，这是一直很不好的处理方法。

测试数据：

测试数据分析：如果输入序列是随机的，处理时间可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为起泡排序，时间复杂度为Θ(n^2)。而且，输入的数据是有序或部分有序的情况是相当常见的。因此，使用第一个元素作为枢纽元是非常糟糕的，为了避免这个情况，就引入了下面两个获取基准的方法。

方法(2)：随机选取基准

引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴

思想：取待排序列中任意一个元素作为基准

随机化算法

/*随机选择枢轴的位置，区间在low和high之间*/  
int SelectPivotRandom(int arr[],int low,int high)  
{  
    //产生枢轴的位置  
    srand((unsigned)time(NULL));  
    int pivotPos = rand()%(high - low) + low;  

    //把枢轴位置的元素和low位置元素互换，此时可以和普通的快排一样调用划分函数  
    swap(arr[pivotPos],arr[low]);  
    return arr[low];  
}  

测试数据： 

测试数据分析：:这是一种相对安全的策略。由于枢轴的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”

方法(3)：三数取中（median-of-three）

引入的原因：虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴

分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数

举例：待排序序列为：8 1 4 9 6 3 5 2 7 0 
左边为：8，右边为0，中间为6. 
我们这里取三个数排序后，中间那个数作为枢轴，则枢轴为6

注意：在选取中轴值时，可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取，一般的，会有（2t＋1）平均分区法（median-of-(2t+1)，三平均分区法英文为median-of-three）。

具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴。

即：采用三数取中，并用0下标元素存储枢轴。

/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/  
int SelectPivotMedianOfThree(int arr[],int low,int high)  
{  
    int mid = low + ((high - low) >> 1);//计算数组中间的元素的下标  

    //使用三数取中法选择枢轴  
    if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]  
    {  
        swap(arr[mid],arr[high]);  
    }  
    if (arr[low] > arr[high])//目标: arr[low] <= arr[high]  
    {  
        swap(arr[low],arr[high]);  
    }  
    if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]  
    {  
        swap(arr[mid],arr[low]);  
    }  
    //此时，arr[mid] <= arr[low] <= arr[high]  
    return arr[low];  
    //low的位置上保存这三个位置中间的值  
    //分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了  
} 

测试数据：

测试数据分析：使用三数取中选择枢轴优势还是很明显的，但是还是处理不了重复数组

4、四种优化方式：

优化1：当待排序序列的长度分割到一定大小后，使用插入排序

原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排

截止范围：待排序序列长度N = 10，虽然在5~20之间任一截止范围都有可能产生类似的结果，这种做法也避免了一些有害的退化情形。摘自《数据结构与算法分析》Mark Allen Weiness 著

if (high - low + 1 < 10)  
{  
    InsertSort(arr,low,high);  
    return;  
}//else时，正常执行快排 

测试数据：

测试数据分析：针对随机数组，使用三数取中选择枢轴+插排，效率还是可以提高一点，真是针对已排序的数组，是没有任何用处的。因为待排序序列是已经有序的，那么每次划分只能使待排序序列减一。此时，插排是发挥不了作用的。所以这里看不到时间的减少。另外，三数取中选择枢轴+插排还是不能处理重复数组

最后

以上就是无限乌冬面为你收集整理的快排的优化策略的全部内容，希望文章能够帮你解决快排的优化策略所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。