- 论坛徽章:
- 0
|
|
对于快速排序的理解
这两天一直在看排序的算法，当看到快速排序的时候卡了，真是那个郁闷啊。之前几个排序（选择、冒泡......）很快就可以过了。
可是看到快速排序的时候就怎么的也不能理解。
然后就到网上去搜了下，搜到的也就这么几种解释，多数都是大同小异。
网上搜到的，解析得也有点官方，看了会觉得还是看不懂。
怎么的......只能自己慢慢理解吧！
最后......也算是有点小成就吧，自己能理解，不知道对还是不对。
费话就不多说了，以下附上代码，和我自己对快速排序的理解！请指教！- 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方法将数组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指向上一个元素 注：“++“、”——”来分别指向下一个元素是因为这两个位置的元素已经比较过了，
- //不需要再过它们比较，来提高效率
- }
- }
//下面将把基准元素放到"中间位置",并非真正的中间，只是它的左边是比基准元素小的元素，它的右边是比基准元素大的元素）
//记：是本次比较的中间位置（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];
- }
//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指针不可能也不需要指向第一个位置元素.顾不用做上移一位处理！
以上是本人对快速排序的一点点理解！
如果大家有什么更好的见解，可以分享一下哦！ |
|
免费注册
发表于 2011-11-10 20:22
