算法二快速排序

经典算法 “挖坑填数+分治”

 1 public class QuickSort {
 2     public static void main(String[] args) {
 3         QuickSort quickSort=new QuickSort();
 4         int arr[]={3,5,2,66,7,33,1,4,9,10};
 5         quickSort.quickSort(arr,0,arr.length-1);
 6         for (int num :
 7                 arr) {
 8             System.out.print(num+" ");
 9         }
10 
11     }
12 
13     public void quickSort(int[] arr, int start, int end) {
14         if (arr == null || start >= end) return;
15         int i = start, j = end;
16         int pivotKey = arr[start];
17         while (i < j) {
18             while (i < j && arr[j] >= pivotKey) j--;
19             if (i < j) arr[i++] = arr[j];
20             while (i < j && arr[i] <= pivotKey) i++;
21             if (i < j) arr[j--] = arr[i];
22         }
23         arr[i] = pivotKey;
24         quickSort(arr, start, i - 1);
25         quickSort(arr, i + 1, end);
26 
27     }
28 }

看快排代码的时候在想为什么别人总是说先要从后往前比较呢？

今天研究代码逻辑终于明白了！！！

选择中枢的时候是 pivotKey=arr[0];

我们先从后往前查找，

while (i < j && arr[j] >= pivotKey) j--;

if (i < j) arr[i++] = arr[j];

若找到比中枢小的则直接放在arr[0]的位置，将arr[0]的值覆盖掉了。不要担心，pivotKey存有arr[0]的值。

此时再从前往后找，碰上比中枢大的值直接放在 arr[j]的位置（arr[j]的值已经存入arr[0]）

=======================================================================================

若从前往后的话（我的想法）

将大于中枢的值先放在arr[0]位置，再从后往前查找小于中枢的值存入arr[i],再将arr[0]的值放入arr[j]

这样挪动好麻烦啊。。。

算法二 快速排序

算法二快速排序