本文将介绍一种另类的快速排序（其实也不是什么新方法，估计也有不少朋友见过了）。一般的quicksort如果不是同时从左和从右找，发现前值小于后值就交换，然后递归继续；就是先假定一个位置的元素为pivot，然后不同方向搜索。这些方法都需要循环几次，所以一般在网上看到的代码都有用到几个while，然后再递归两次。下面你将看到一个quicksort只用了一次while。
原理依然是使用分区法，比如以下这个数组
[60, 30, 80, 70, 50, 20]
先假定 60 是pivot，选择它下一个值，我们称为smallend，稍后我们再解释它的意思。
根据以上所述，pivot的index在0，该值为60；smallend的index在1，该值为30。
然后我们从smallend开始往前，我们把往前的那个指针称为idx，现在idx为1，因为我们是从smallend的位置开始往前的。只有发生以下三种情况：
1．当我们发现一个比pivot大的值，什么野不做。
2． 当我们发现一个比pivot小的值，把它和smallend位置的那个元素交换，并让smallend++
3．Smallend = idx，不交换，但是让smallend++
比如上面那个数组，idx=1，元素为30，因为<60，但是发现这个位置就是smallend了，于是直接加1，现在数组个元素位置不变，smallend=2。
接下来idx=2，元素为80，因为 >60，什么也不做，继续往前；idx=3，元素为70，什么也不做。Idx=4，元素为50，把它和smallend位置的元素交换，并增加smallend，数组变成
[60, 30, 50, 70, 80, 20]
现在smallend为3，idx为4。
继续往前走，idx=5，元素为20，交换，增加smallend。数组变为
[60, 30, 50, 20, 80, 70]
循环已经结束。Smallend=4，也就是正指向元素80那个位置。
相信大家现在大概直到，smallend就是指所有比pivot小的元素在数组中后面那个位置。
现在，我们把smallend减1，smallend=3，指向元素20的位置。我们把这个元素和pivot交换。那么pivot已经找到它的位置了——它左边的所有值都比自己小，右边所有值都比自己大。数组已经变成
[20, 30, 50, 60, 80, 70]
然后，再开始递归，quicksort（左边），quicksort（右边）。结束！
具体实现的代码如下：
|
private static void QuickSort(int[] arr,int left, int right) { if (right>left) { int smallend= left + 1; int idx = left + 1; // start from the element next to the first element int rightIdx; // reserved to backup the smallend
// check from left+1 to right while (idx<=right) { if (arr[idx]<arr[left]) { swap(arr, idx, smallend); smallend++; } // increase the next element position idx++; } // end while
rightIdx = smallend; smallend–; swap(arr, left, smallend); // 到这一句结束就已经把数组分好两块了
// recursively quick sort the left partition QuickSort(arr, left, smallend) ; // recursively quick sort the right partition QuickSort(arr, rightIdx, right); } // end if }
private static void swap(int[] arr, int index1, int index2) { if (index1==index2) return; int temp =arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } |
实现过程中只用了一次while，但是道理上还是使用了quicksort的原则。
注：请勿修改或转至刊登于盈利性刊物，欢迎网上自由转载。谢谢。
