1 package sort; 2  3 /** 4  * @Description 5  * @Author Created by t.wu on 2017/8/21. 6  */ 7 public class QuickSort { 8  9     public void sort(int[] a, int l, int r) {10         if (l < r) {11             int split = partition(a, l, r);12             sort(a, l, split);13             sort(a, split + 1, r);14         }15     }16 17     /**18      * 直接就地把小于pivot的数顺序放到a的起始位置19      * @param a20      * @param l21      * @param r22      * @return23      */24     public static int partition(int[] a, int l, int r) {25         int pivot = a[r];26         int i = l - 1;27         int j;28         for (j = l; j <= r - 1; j++) {29             if (a[j] <= pivot) {30                 i++;31                 int temp = a[i];32                 a[i] = a[j];33                 a[j] = temp;34             }35         }36         // 这时i的左边都是小于 pivot的，所以把i+1的位置和pivot调换37         pivot = a[i + 1];38         a[i + 1] = a[r];39         a[r] = pivot;40         return i + 1;41     }42 }

1 package sort; 2  3 /** 4  * @Description 堆排序 5  * 算法思想： 6  * @Author Created by t.wu on 2017/8/21. 7  */ 8 public class HeapSort { 9 10     /**11      * 保证任意节点的值都大于其子节点的值12      * 如何保证这个树的中任意节点都有左右两个子节点？13      * 答案就在建树的过程中。14      * 注意 数组索引从0开始，左右子树的索引正确的算法，就应该分别是 2 * 1 + 1 , 2 * i + 215      * @param a16      * @param heapSize17      * @param index18      */19     public void heapfy(int[] a, int heapSize, int index) {20         int left = 2 * index +1;21         int right = 2 * index + 2;22         int max = index;23         if (left < heapSize && a[max] < a[left]) {24             max = left;25         }26         if (right < heapSize && a[max] < a[right]) {27             max = right;28         }29         if (max != index) {30             int tmp = a[index];31             a[index] = a[max];32             a[max] = tmp;33             heapfy(a, a.length, max);34         }35     }36 37     public void createHeap(int[] a) {38         int middle = a.length / 2 -1;39         for (int i = middle; i >= 0; i--) {40             heapfy(a, a.length,i);41         }42     }43 44     /**45      * 取出最大的a[0]，放在最后，再对剩下的数组进行heapfy。46      * @param a47      */48     public void sort(int[] a){49         for(int i = a.length-1 ; i >=0 ; i--){50             int tmp = a[0];51             a[0] = a[i];52             a[i] = tmp ;53 54             heapfy(a,i,0);55             System.out.println("====dd====");56             for(int j : a){57                 System.out.print(j+" ");58             }59         }60     }61 62     public static void main(String[] args) {63         int[] a = new int[] {17,13,4,51,67,5};64         HeapSort hs = new HeapSort();65         hs.createHeap(a);66         hs.sort(a);67         System.out.println("========");68         for(int i : a){69             System.out.print(i+" ");70         }71     }72 }

1 package sort; 2  3 /** 4  * @Description 插入排序 5  * 算法思想：从数组第二个位置开始，以当前位置的值和其前面所有值进行比较，凡是比当前值大的都向后移一位。 6  * @Author Created by t.wu on 2017/8/19. 7  */ 8 public class InsertSort { 9     /**10      *11      * @param a12      */13     public void sort(int[] a){14         for(int i=1; i
     
      =0 && a[j]> pivot){18                 a[j+1] = a[j];19                 j--;20             }21             // 跳出循环，意味着 j=-1<0 or a[j] < pivot,22             // j=-1时，j+1 = 0 ,也就从j >=1 开始的位置逗比 pivot大，则a[0] = pivot23             // a[j] < pivot 意味着 a[j+1] 开始都大于pivot，原来的j+1位置因为大于pivot，所以已经后移了，这时j+1的位置其实是“空”的。24             // 所以pivot 放在j+1 正好，前面都比他小，后面都比他大。25              a[j+1] = pivot;26         }27     }28 29     public static void main(String[] args) {30         int[] a = new int[] {17,13,4,51,67,5};31         new InsertSort().sort(a);32         for(int i : a){33             System.out.println(i);34         }35     }36 }
     

1 package sort; 2  3 /** 4  * @Description 归并排序 5  * 算法思想：想象两叠牌，两叠牌都是有序的，如何让他们合并成一个有序的数列？ 6  * 1. 首先二分数组 length /2  并下取整。 7  * 2. 每次从左右队列中各取一个数，进行比较，小的放进原数组的相应位置。 8  * 3. 注意：边界条件，当p>=r时，说明没有可再二分的数。所以一定是最先分到左右数组各有一个数为止，开始合并这两个数组。 9  * @Author Created by t.wu on 2017/8/19.10  */11 public class MergeSort {12 13     private void merge(int[] a , int p,int q, int r ){14         int n1 = q-p+1+1;15         int n2 = r-q+1;16         int[] left = new int[n1];17         int[] right = new int[n2];18         for(int i = 0 ; i< left.length-1; i++){19             left[i]= a[p+i];20         }21         for(int i = 0 ; i< right.length-1; i++){22             right[i]= a[q+1+i];23         }24         left[q-p+1] = Integer.MAX_VALUE;   // （1） 最大的数放在这里，方便比较且不会越界25         right[r-q] = Integer.MAX_VALUE;26 27         int j =0;28         int i =0;29         for(int k = p; k<=r; k++ ){30             if(left[i]