快速排序 三平均分区法 java_java快速排序的三种快排及四种优化方式

本文转载自CSDN博主「silentsharer」

可以配套食用我的博文 java快速排序的两种思想与代码实现

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];

}

测试数据：