1 public class Sort {
 2     /*
 3      * 直接插入排序： 先确定一个有序数组，然后把插入的数与有序数组从最后依次进行比较， 直到插入的数比有序数组的数大，此数换为插入的数字，从此位置以后
 4      * 的数依次向后移动一位。
 5      */
 6     public static void insert(int[] a) {
 7         for (int i = 1; i < a.length; i++) {
 8             int b = a[i], j;
 9             for (j = i - 1; j >= 0 && b < a[j]; j--) {
10                 a[j + 1] = a[j];
11             }
12             a[j + 1] = b;
13 
14         }
15     }
16 
17     /*
18      * 折半插入排序法： 对有序数组确定最小下标，最大下标， 然后将插入的值与中间值进行比较，
19      * 如果小于中间值，则最大下标为中间下标-1，否则最小下标为中间下标+1; 循环确定插入位置为最小下标，然后把插入的数字赋值给最小下标对应
20      * 的数，后面的数依次往后移动一位。
21      */
22     public static void halfInsert(int[] a) {
23         for (int i = 1; i < a.length; i++) {
24             int b = a[i], low = 0, high = i - 1;
25             while (low <= high) {
26                 int mid = (low + high) / 2;
27                 if (b > a[mid]) {
28                     low = mid + 1;
29                 } else {
30                     high = mid - 1;
31                 }
32             }
33 
34             for (int j = low; j < i; j++) {
35                 a[j + 1] = a[j];
36             }
37             a[low] = b;
38         }
39 
40     }
41 
42     /*
43      * 冒泡排序： 双重循环，最多进行n-1趟排序，每相邻两个数进行比较，如果前面的大，则进行交换，
44      * 用exchange判断两数是否变换了，如果没有变换，则不必再进行上述步骤进行排序，直接输出结果。
45      */
46     public static void bubblseSort(int[] a) {
47         boolean exchange = true;// 是否交换的标志
48         for (int i = 1; i < a.length && exchange; i++) {
49             exchange = false;
50             for (int j = 0; j < a.length - 1; j++) {
51                 if (a[j + 1] < a[j]) {
52                     int b = a[j + 1];
53                     a[j + 1] = a[j];
54                     a[j] = b;
55                     exchange = true;
56                 }
57             }
58 
59         }
60     }
61 /*
62  * 快速排序算法：
63  * 找第一个数做基准量，从后往前找，比基准量大的数放到后边，小的就把数往前移动，
64  * 从前往后找，比基准量小的放到前面，大的就往后移动，
65  * 循环执行上述步骤，直到前后端序列都变为1个数为止，用递归算法实现。
66  */
67     public static void quickSort(int[] a, int b, int e) {
68         int i = b, j = e, x = a[i];
69         while (i < j) {
70             while (i < j && x < a[j])
71                 j--;
72             if (i < j)
73                 a[i++] = a[j]; // 后端小的数向前移动
74             while (i < j && x > a[i])
75                 i++;
76             if (i < j)
77                 a[j--] = a[i]; // 前端大的数向后移动
78 
79         }
80         ;
81         // 此时，i=j;
82         a[i] = x;
83         if (b < i)
84             quickSort(a, b, i - 1);
85         if (i < e)
86             quickSort(a, i + 1, e);
87     }
88 }