?
这两天一直在看排序的算法，当看到快速排序的时候卡了，真是那个郁闷啊。之前几个排序（选择、冒泡......）很快就可以过了。
可是看到快速排序的时候就怎么的也不能理解。
然后就到网上去搜了下，搜到的也就这么几种解释，多数都是大同小异。
网上搜到的，解析得也有点官方，看了会觉得还是看不懂。
怎么的......只能自己慢慢理解吧！
最后......也算是有点小成就吧，自己能理解，不知道对还是不对。
?
费话就不多说了，以下附上代码，和我自己对快速排序的理解！请指教！
?
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指针不可能也不需要指向第一个位置元素.顾不用做上移一位处理！ 以上是本人对快速排序的一点点理解！ 如果大家有什么更好的见解，可以分享一下哦！ 当然以上如果哪里本人理解错了，也请及时提出，以便纠正！谢谢！
?
相关文章
