排序(五)快速排序

一、定义

百科中的快速排序的介绍是:

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

二、实现思路

从数据中选择一个基准数,将整个数据中比基准数小的放到基准数的左边,比基准数大的数放到右边。这样整个数据就分成了两个部分,再将两个部分的数据通过递归在执行前面的操作,重复即可完成排序。

整个算法中基准数的选择绝定了算法的效率一般有三种方式。

1》将数据中的第一个数作为基准数,在随机的数据中效率还行,但在反序的数据中效率低下。

2》随机选择一个数为基准数,因为每次都要随机产生基准数效率有所降低。

3》三数中值分割法,一组N个数的中值是第[N/2]个最大的数。”基准“的最好选择是数组的中值。但是这很难算出,且减慢快速排序的速度。这样的中值的估计量可以通过随机选取三个元素并用它们的中值作为”基准”而得到。实际上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为“基准”。

下面以 4 6 2 8 5 9 1 为例子讲解.

  1. 选择基准(此处选择每个部分的第一个为基准。)这里选择4作为基准。

  2. 从右边开始找比基准数4小的数1,找到后记录数据下标j=6,再从左边向右找比基准数4大的数6,记录下标i=1.将1和6交换。交换后的数据为:4 1 2 8 5 9 6.继续从右向左找,找到2比4小,记录其下标j=2,再从左往右找比基准数大的数,再找到之前碰到了j,停止寻找。将相遇的下标记下为i=j=2;将下标为2的数据与基准数交换,得到新数据为:2 1 4 8 5 9 6.这样就结束了一次查找。将数据分为两部分,基准数左边的都是比基准数小的。2 1;基准数的右边都是比基准数大的数:8 5 9 6。

  3. 使用递归将两个数据,重复执行上述步骤,直到所有分出的数据长度小于等于1,快速排序就写好了。

三、代码

当基准从左边第一个取的时候 ,先从右边开始移动 。当基准从右边第一个去的时候,先从左边移动

中间的时候,先从右边开始移动,在每次还没遇到交换的时候 i++ 左边+1 不知道为什么、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void quickSort(int[] a , int start ,int end ){
if (start >= end){
return;
}
//选择基准 ,为开始位置
int m = start ;
//选择基准为中间位置
// int m = start + (end - start)/2 ;
//设置开始和结束哨兵
int i = start , j = end;
//设置基准值
int key = a[m];
while (i !=j){
//右边哨兵找到比基准小的数停下 , 且两个哨兵遇到的时候停下
while (a[j] >= key && i!=j ) j--;
//左边哨兵找到比基准大的数停下 , 且两个哨兵遇到的时候停下
while (a[i] <= key && i!=j) i++;
if (i!=j){
//两个哨兵没有遇到 且都找到了对应的值那么 交换两个哨兵处的值
swap(a,j,i);
}
}
swap(a,m,i);
quickSort(a,start,i-1);
quickSort(a,i+1,end);
}