对于快速排序的理解

 

这两天一直在看排序的算法，当看到快速排序的时候卡了，真是那个郁闷啊。之前几个排序（选择、冒泡......）很快就可以过了。

可是看到快速排序的时候就怎么的也不能理解。

然后就到网上去搜了下，搜到的也就这么几种解释，多数都是大同小异。

网上搜到的，解析得也有点官方，看了会觉得还是看不懂。

怎么的......只能自己慢慢理解吧！

最后......也算是有点小成就吧，自己能理解，不知道对还是不对。

 

费话就不多说了，以下附上代码，和我自己对快速排序的理解！请指教！

 

public void quickSort(int[] array, int left, int right) { //array，要排序的数组；

                                                                       //left，从数组left位置开始排序；

                                                                       //right，排序到数组的right位置。 排序整个数组：left=0；right=array.length。

if (left < right) { //如果是一个正确的开始和结束的排序位置（开始位置肯定小于结束位置）

int mid = partition(array, left, right);  //通过partition方法得到排序的分隔点（关于partition方法原理可以往下看注解）

quickSort(array, left, mid - 1);  //递归分隔点以前部分的排序（以left为开始点，分隔点前一个元素为结束点）

quickSort(array, mid + 1, right); //递归分隔点以后部分的排序（以分隔点的后一个元素为开始点，以right为结束点）

}

}

 

//在不管partition方法的实现的情况下，以上方法相信大家都应该可以容易的理解吧！

//既：通过partition方法将数组array分成以分隔点为中心，左边是比其小的元素集，右边是比其大的元素集。

//       然后返回数组的分隔点，通过递归对分隔点左右两边再进行排序。

//下面来看partition方法的实现——->

 

public int partition(int[] array, int left, int right) { //排序数组array的left到right位置，并返回分隔点（分隔点左边是小元素，右边是大元素）

                                                                           //array:要分隔的数组

                                                                           //left:要分隔部分的开始位置

                                                                           //right:要分隔部分的结束位置

int pivot = array[left]; //设定第一个元素为基准元素（一般都以第一个元素为基准，本例也一样，不做特殊化）

int head = left; //这两个值（head/tail）的设定我觉得是挺重要的。

                                      //head:指向要分隔部分的左(头)位置

                //从小到大排列 //head++，向右(tail)移动；tail——，向左(head)移动。

int tail = right + 1;//tail:指向要分隔部分的右(尾)位置 ，为什么要后移一位，请看后注。

 

//以下连起来为一句话：①②③④

while (head < tail) { //①在head和tail碰到(==) 之前，

if (array[head] <= pivot) {   //②如果在head位置找到了比基准元素大的元素，

head++;  //否则找下一个元素

} else if (array[tail - 1] > pivot) { //③并且在(tail-1)位置找到了比基准元素小或等于的元素。

tail——; //否则找上一个元素

} else {

swap(array, head, tail - 1);//④那么交换head和(tail-1)位置的元素。

                                                                    //来实现把大的元素放到基准元素后面，把小的元素放基准元素前面。

head++; //并让head指向下一个元素

tail——;//让tail指向上一个元素                    注：“++“、”——”来分别指向下一个元素是因为这两个位置的元素已经比较过了，

                                                                                            //不需要再过它们比较，来提高效率

}

}

  //到这里已经结束上面的交换，既：head>=tail。

//下面将把基准元素放到"中间位置",并非真正的中间，只是它的左边是比基准元素小的元素，它的右边是比基准元素大的元素）

//记：是本次比较的中间位置（left到right）

array[left] = array[head - 1];  //把第一个元素(left)赋值为head指针的上一个元素.

                                                         //为什么是上一个元素，而不是head指向位置的元素？

                                                         //因为head指向位置的元素，你不知道它的大小，

                                                         //把head指向的元素放到小元素集(基准元素的左边),将无法保证小元素集(可能head指向的元素比基准元素大)

                                                         //这样就破坏了排序（排列的目的：将基准的左边放比基准小的元素，将基准的右边放比基准大的元素）

                                                        //所以，把head的上一个元素和基准交换就能保证排列的目的。因为head的上一个元素一定是小元素

array[head - 1] = pivot;//把head指针的上一个元素赋值为基准元素 （完成交换）

return head - 1; //返回基准元素位置（通过上面的交换，这里基准元素的位置已经变成了head-1），作为排序的分隔点。

}

 

private void swap(int[] array, int a, int b) { //交换数组array中的a和b位置的元素

                                                                    //该方法用异或"^"来完成交换，当然也可以简单的第三个临时元素来完成

array[a] = array[a] ^ array[b];

array[b] = array[a] ^ array[b];

array[a] = array[a] ^ array[b];

}

 

//后注：为什么tail = right+1 ; head ≠left-1 ?

//left指向排列首 ，right指向排列尾。

//排列开始的指针head当然应该指向排列首(left)啊，结束tail当然指向排列尾(right)啦。可tail为什么要后移一位，这样不就会造成越界吗？

//我的理解是这样的：

//head++,向tail移动。为了能让head指针在最后能够指向最尾right ,如果在这里不加一，那么在下面while判断首尾相遇(head== tail)的时候，就要写成while(head<＝tail)。

//这样感觉应该也可以......为什么不用while(head<=tail)？

//因为，如果用“<=”的话，当head == tail的时候还要比较一次,这样不是多余，会降低效率！

//所以在这里用后移一位来处理（tail = right+1）.让在“while(head < tail)”的条件下，head可以指向最尾（right）.

//相应的，在以下的计算中要用“tail-1”来计算，为的是不让数组下标越界。

//为什么head不用上移一位呢？

//因为在while循环中，head判断在前，基准是第一个位置元素array[left]，而且找的是比基准元素大的元素，所以tail指针不可能也不需要指向第一个位置元素.顾不用做上移一位处理！

以上是本人对快速排序的一点点理解！

如果大家有什么更好的见解，可以分享一下哦！

当然以上如果哪里本人理解错了，也请及时提出，以便纠正！谢谢！

 

评论

3 楼 Hxuejie 2011-11-22  

归并排序和快速排序是不是大同小异呢？

2 楼 Hxuejie 2011-11-22  

Technoboy 写道

看一下《Java数据结构和算法》

呵呵，嗯！
谢谢指点！
那问一下我对快速排序的理解对吗？其原理是这样的吗？

1 楼 Technoboy 2011-11-11  

看一下《Java数据结构和算法》