排序算法原理及实现

插入排序

 1     public static void insertSort(Comparable[] array)
 2     {
 3         int j = 0;
 4         
 5         for (int i = 1; i < array.length; i++) {
 6             Comparable temp = array[i];
 7             
 8             for (j = i; j > 0 && (temp.compareTo(array[j - 1]) < 0); j--) {
 9                 array[j] = array[j - 1];
10             }
11             array[j] = temp;
12         }
13     }

归并排序

 1     public static void mergeSort(Comparable[] array)
 2     {
 3         Comparable[] copy = new Comparable[array.length];
 4         mergeSort(array, copy, 0, array.length - 1);
 5     }
 6     
 7     
 8     private static void mergeSort(Comparable[] array, Comparable[] temp, int left, int right)
 9     {
10         if (left < right) {
11             int middle = (left + right) >> 1;
12             mergeSort(array, temp, left, middle);
13             mergeSort(array, temp, middle + 1, right);
14             merge(array, temp, left, middle + 1, right);
15         }
16     }
17     
18     
19     private static void merge(Comparable[] array, Comparable[] temp, int left, int right, int rightEnd)
20     {
21         int leftEnd = right - 1;
22         int tempIdx = left;
23         int length  = rightEnd - left + 1;
24         
25         while (left <= leftEnd && right <= rightEnd) {
26             if (array[left].compareTo(array[right]) < 0) {
27                 temp[tempIdx++] = array[left++];
28             }
29             else {
30                 temp[tempIdx++] = array[right++];
31             }
32         }
33         
34         while (left <= leftEnd) {
35             temp[tempIdx++] = array[left++];
36         }
37         
38         while (right <= rightEnd) {
39             temp[tempIdx++] = array[right++];
40         }
41         
42         for (int i = 0; i <length; i++, rightEnd--) {
43             array[rightEnd] = temp[rightEnd];
44         }
45     }

快速排序

 1     public static void quickSort(Comparable[] array)
 2     {
 3         quickSort(array, 0, array.length - 1);
 4     }
 5     
 6     
 7     private static void quickSort(Comparable[] array, int left, int right)
 8     {
 9         if (left + 3 <= right) {
10             Comparable middle = just(array, left, right);
11             
12             int i = left, j = right - 1;
13             
14             for (;;) {
15                 while (array[++i].compareTo(middle) < 0) {}
16                 while (array[--j].compareTo(middle) > 0) {System.out.println(j);}
17                 if (i < j) swap(array, i, j); else break;
18             }
19             
20             swap(array, i, right - 1);
21             quickSort(array, left, i);
22             quickSort(array, i + 1, right);
23         }
24         else {
25             insertSort(array);
26         }
27     }
28     
29     
30     private static Comparable just(Comparable[] array, int left, int right)
31     {
32         int middle = (left + right) >> 1;
33                 
34         if (array[left].compareTo(array[middle]) > 0)  swap(array, left, middle);
35         if (array[middle].compareTo(array[right]) > 0) swap(array, middle, right);
36         if (array[right].compareTo(array[left]) > 0)   swap(array, left, right);
37         
38         swap(array, middle, right);
39         return array[right];
40     }
41     
42     
43     private static void swap(Comparable[] array, int i, int j)
44     {
45         Comparable tmp = array[i];
46         array[i] = array[j];
47         array[j] = tmp;
48     }

先放上代码，原理及注释随后补全