import java.util.Arrays; /*  * 實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序  * 以及快速排序、歸并排序、堆排序和LST基數排序  * @author gkh178  */ public class EightAlgorithms {      //插入排序：時間復雜度o(n^2)    public static void insertSort(int a[], int n) {     for (int i = 1; i < n; ++i) {       int temp = a[i];       int j = i - 1;       while (j >= 0 && a[j] > temp) {         a[j + 1] =a[j];         --j;       }       a[j + 1] = temp;     }   }      //冒泡排序：時間復雜度o(n^2)    public static void bubbleSort(int a[], int n) {     for (int i = n - 1; i > 0; --i) {       for (int j = 0; j < i; ++j) {         if (a[j] > a[j + 1]) {           int temp = a[j];           a[j] = a[j + 1];           a[j + 1] = temp;             }       }       }     }      //選擇排序：時間復雜度o(n^2)    public static void selectSort(int a[], int n) {     for (int i = 0; i < n - 1; ++i) {       int min = a[i];       int index = i;       for (int j = i + 1; j < n; ++j) {         if (a[j] < min) {           min = a[j];           index = j;         }         }       a[index] = a[i];       a[i] = min;     }   }      //希爾排序：時間復雜度介于o(n^2)和o(nlgn)之間    public static void shellSort(int a[], int n) {     for (int gap = n / 2; gap >= 1; gap /= 2) {       for (int i = gap; i < n; ++i) {         int temp = a[i];         int j = i -gap;         while (j >= 0 && a[j] > temp) {           a[j + gap] = a[j];           j -= gap;         }         a[j + gap] = temp;       }     }     }      //快速排序：時間復雜度o(nlgn)    public static void quickSort(int a[], int n) {     _quickSort(a, 0, n-1);   }   public static void _quickSort(int a[], int left, int right) {     if (left < right) {       int q = _partition(a, left, right);       _quickSort(a, left, q - 1);       _quickSort(a, q + 1, right);     }   }   public static int _partition(int a[], int left, int right) {     int pivot = a[left];     while (left < right) {       while (left < right && a[right] >= pivot) {         --right;       }       a[left] = a[right];       while (left <right && a[left] <= pivot) {         ++left;       }       a[right] = a[left];     }     a[left] = pivot;     return left;   }      //歸并排序：時間復雜度o(nlgn)    public static void mergeSort(int a[], int n) {     _mergeSort(a, 0 , n-1);   }   public static void _mergeSort(int a[], int left, int right) {     if (left <right) {       int mid = left + (right - left) / 2;       _mergeSort(a, left, mid);       _mergeSort(a, mid + 1, right);       _merge(a, left, mid, right);     }   }   public static void _merge(int a[], int left, int mid, int right) {     int length = right - left + 1;     int newA[] = new int[length];     for (int i = 0, j = left; i <= length - 1; ++i, ++j) {       newA[i] = a[j];     }     int i = 0;     int j = mid -left + 1;     int k = left;     for (; i <= mid - left && j <= length - 1; ++k) {       if (newA[i] < newA[j]) {         a[k] = newA[i++];       }       else {         a[k] = newA[j++];       }     }     while (i <= mid - left) {       a[k++] = newA[i++];     }     while (j <= right - left) {       a[k++] = newA[j++];     }   }      //堆排序：時間復雜度o(nlgn)    public static void heapSort(int a[], int n) {     builtMaxHeap(a, n);//建立初始大根堆     //交換首尾元素，并對交換后排除尾元素的數組進行一次上調整     for (int i = n - 1; i >= 1; --i) {       int temp = a[0];       a[0] = a[i];       a[i] = temp;       upAdjust(a, i);     }   }   //建立一個長度為n的大根堆   public static void builtMaxHeap(int a[], int n) {     upAdjust(a, n);   }   //對長度為n的數組進行一次上調整   public static void upAdjust(int a[], int n) {     //對每個帶有子女節點的元素遍歷處理，從后到根節點位置     for (int i = n / 2; i >= 1; --i) {       adjustNode(a, n, i);     }   }   //調整序號為i的節點的值   public static void adjustNode(int a[], int n, int i) {     //節點有左右孩子     if (2 * i + 1 <= n) {       //右孩子的值大于節點的值，交換它們       if (a[2 * i] > a[i - 1]) {         int temp = a[2 * i];         a[2 * i] = a[i - 1];         a[i - 1] = temp;       }       //左孩子的值大于節點的值，交換它們       if (a[2 * i -1] > a[i - 1]) {         int temp = a[2 * i - 1];         a[2 * i - 1] = a[i - 1];         a[i - 1] = temp;       }       //對節點的左右孩子的根節點進行調整       adjustNode(a, n, 2 * i);       adjustNode(a, n, 2 * i + 1);     }     //節點只有左孩子，為最后一個有左右孩子的節點     else if (2 * i == n) {       //左孩子的值大于節點的值，交換它們       if (a[2 * i -1] > a[i - 1]) {         int temp = a[2 * i - 1];         a[2 * i - 1] = a[i - 1];         a[i - 1] = temp;       }       }   }      //基數排序的時間復雜度為o(distance(n+radix)),distance為位數，n為數組個數，radix為基數   //本方法是用LST方法進行基數排序，MST方法不包含在內   //其中參數radix為基數，一般為10；distance表示待排序的數組的數字最長的位數；n為數組的長度   public static void lstRadixSort(int a[], int n, int radix, int distance) {     int[] newA = new int[n];//用于暫存數組     int[] count = new int[radix];//用于計數排序，保存的是當前位的值為0 到 radix-1的元素出現的的個數     int divide = 1;     //從倒數第一位處理到第一位     for (int i = 0; i < distance; ++i) {       System.arraycopy(a, 0, newA, 0, n);//待排數組拷貝到newA數組中       Arrays.fill(count, 0);//將計數數組置0       for (int j = 0; j < n; ++j) {         int radixKey = (newA[j] / divide) % radix; //得到數組元素的當前處理位的值         count[radixKey]++;       }       //此時count[]中每個元素保存的是radixKey位出現的次數       //計算每個radixKey在數組中的結束位置，位置序號范圍為1-n       for (int j = 1; j < radix; ++j) {         count[j] = count[j] + count[j - 1];       }       //運用計數排序的原理實現一次排序，排序后的數組輸出到a[]       for (int j = n - 1; j >= 0; --j) {         int radixKey = (newA[j] / divide) % radix;         a[count[radixKey] - 1] = newA[j];         --count[radixKey];       }       divide = divide * radix;     }   } } 

public class TestEightAlgorithms {    public static void printArray(int a[], int n) {     for (int i = 0; i < n; ++i) {       System.out.print(a[i] + " ");       if ( i == n - 1) {         System.out.println();       }     }   }      public static void main(String[] args) {     for (int i = 1; i <= 8; ++i) {       int arr[] = {45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128};       switch(i) {       case 1:         EightAlgorithms.insertSort(arr, arr.length);         break;       case 2:         EightAlgorithms.bubbleSort(arr, arr.length);         break;       case 3:         EightAlgorithms.selectSort(arr, arr.length);         break;       case 4:         EightAlgorithms.shellSort(arr, arr.length);         break;       case 5:         EightAlgorithms.quickSort(arr, arr.length);         break;       case 6:         EightAlgorithms.mergeSort(arr, arr.length);         break;       case 7:         EightAlgorithms.heapSort(arr, arr.length);         break;       case 8:         EightAlgorithms.lstRadixSort(arr, arr.length, 10, 4);         break;       default:         break;       }       printArray(arr, arr.length);     }   } }