import java.util.Arrays; 
/* 
 * 實現(xiàn)了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序 
 * 以及快速排序、歸并排序、堆排序和LST基數(shù)排序 
 * @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);//建立初始大根堆 
    //交換首尾元素，并對交換后排除尾元素的數(shù)組進行一次上調(diào)整 
    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的數(shù)組進行一次上調(diào)整 
  public static void upAdjust(int a[], int n) { 
    //對每個帶有子女節(jié)點的元素遍歷處理，從后到根節(jié)點位置 
    for (int i = n / 2; i >= 1; --i) { 
      adjustNode(a, n, i); 
    } 
  } 
  //調(diào)整序號為i的節(jié)點的值 
  public static void adjustNode(int a[], int n, int i) { 
    //節(jié)點有左右孩子 
    if (2 * i + 1 <= n) { 
      //右孩子的值大于節(jié)點的值，交換它們 
      if (a[2 * i] > a[i - 1]) { 
        int temp = a[2 * i]; 
        a[2 * i] = a[i - 1]; 
        a[i - 1] = temp; 
      } 
      //左孩子的值大于節(jié)點的值，交換它們 
      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; 
      } 
      //對節(jié)點的左右孩子的根節(jié)點進行調(diào)整 
      adjustNode(a, n, 2 * i); 
      adjustNode(a, n, 2 * i + 1); 
    } 
    //節(jié)點只有左孩子，為最后一個有左右孩子的節(jié)點 
    else if (2 * i == n) { 
      //左孩子的值大于節(jié)點的值，交換它們 
      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; 
      }   
    } 
  } 
   
  //基數(shù)排序的時間復雜度為o(distance(n+radix)),distance為位數(shù)，n為數(shù)組個數(shù)，radix為基數(shù) 
  //本方法是用LST方法進行基數(shù)排序，MST方法不包含在內(nèi) 
  //其中參數(shù)radix為基數(shù)，一般為10；distance表示待排序的數(shù)組的數(shù)字最長的位數(shù)；n為數(shù)組的長度 
  public static void lstRadixSort(int a[], int n, int radix, int distance) { 
    int[] newA = new int[n];//用于暫存數(shù)組 
    int[] count = new int[radix];//用于計數(shù)排序，保存的是當前位的值為0 到 radix-1的元素出現(xiàn)的的個數(shù) 
    int divide = 1; 
    //從倒數(shù)第一位處理到第一位 
    for (int i = 0; i < distance; ++i) { 
      System.arraycopy(a, 0, newA, 0, n);//待排數(shù)組拷貝到newA數(shù)組中 
      Arrays.fill(count, 0);//將計數(shù)數(shù)組置0 
      for (int j = 0; j < n; ++j) { 
        int radixKey = (newA[j] / divide) % radix; //得到數(shù)組元素的當前處理位的值 
        count[radixKey]++; 
      } 
      //此時count[]中每個元素保存的是radixKey位出現(xiàn)的次數(shù) 
      //計算每個radixKey在數(shù)組中的結(jié)束位置，位置序號范圍為1-n 
      for (int j = 1; j < radix; ++j) { 
        count[j] = count[j] + count[j - 1]; 
      } 
      //運用計數(shù)排序的原理實現(xiàn)一次排序，排序后的數(shù)組輸出到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); 
    } 
  } 
}