java中快速排序的实现思路

Python015

java中快速排序的实现思路,第1张

快速排序法：快速排序法号称是目前最优秀的算法之一，实现思路是，将一个数组的排序问题看成是两个小数组的排序问题，而每个小的数组又可以继续看成更小的两个数组，一直递归下去，直到数组长度大小最大为2

初级的排序方法有泡泡,插入和选择.高级的排序方法还有堆排序,希尔排序法,快速排序法. 快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n2)，但是在多数的情况下，快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。 1. 将最左边的数设定为轴，并记录其值为 s 循环处理： 1. 令索引 i 从数列左方往右方找，直到找到大于 s 的数 2. 令索引 j 从数列左右方往左方找，直到找到小于 s 的数 3. 如果 i >= j，则离开循环 4. 如果 i <j，则交换索引i与j两处的值 5. 将左侧的轴与 j 进行交换 6. 对轴左边进行递归 7. 对轴右边进行递归 透过以下算法，则轴左边的值都会小于s，轴右边的值都会大于s，如此再对轴左右两边进行递归，就可以对完成排序的目的，例如下面的实例，*表示要交换的数，[]表示轴： [41] 24 76* 11 45 64 21 69 19 36* [41] 24 36 11 45* 64 21 69 19* 76 [41] 24 36 11 19 64* 21* 69 45 76 [41] 24 36 11 19 21 64 69 45 76 21 24 36 11 19 [41] 64 69 45 76 在上面的例子中，41左边的值都比它小，而右边的值都比它大，如此左右再进行递归至排序完成。 public class QuickSort { public static void sort(int[] number) { sort(number, 0, number.length-1)} private static void sort(int[] number, int left, int right) { if(left <right) { int s = number[left]int i = leftint j = right + 1while(true) { // 向右找 while(i + 1 <number.length &&number[++i] <s) // 向左找 while(j -1 >-1 &&number[--j] >s) if(i >= j) breakswap(number, i, j)} number[left] = number[j]number[j] = ssort(number, left, j-1)// 對左邊進行遞迴 sort(number, j+1, right)// 對右邊進行遞迴 } } private static void swap(int[] number, int i, int j) { int tt = number[i]number[i] = number[j]number[j] = t}}