Java数据结构第一讲-排序算法（上）

public static void selectSort(int[] a) {
  int temp,flag = 0;
  int n = a.length;
  for (int i = 0; i < n; i++) {
    temp = a[i]; //第一个数据给temp a[i]为已排序区间的末尾
    flag = i;
    for (int j = i + 1; j < n; j++) {
      if (a[j] < temp) {
        temp = a[j]; // 值
        flag = j; // 位置
      }
    }
    if (flag != i) {
      // 最小数据与第一个数据进行交换
      a[flag] = a[i];
      a[i] = temp;
    }
  }
}

public static void insertSort(int[] a) {
  if (a != null) {
    for (int i = 1; i < a.length; i++) {
      // 寻找插入的位置
      int temp = a[i], j = i;
      if (a[j - 1] > temp) {
        while (j >= 1 && a[j - 1] > temp) {
          a[j] = a[j - 1];//依次后移
          j--;
        }
      }
      a[j] = temp;//插入合适的位置
    }
  }
}

public class 冒泡排序 {
  // 冒泡排序，a表示数组，n表示数组大小
  public void bubbleSort(int[] a, int n) {
    if (n <= 1)
      return;
    for (int i = 0; i < n; ++i) {
      boolean flag = false;// 提前退出冒泡循环的标志位
      for (int j = 0; j < n - i - 1; ++j) {
        if (a[j] > a[j + 1]) { // 交换
          int tmp = a[j];
          a[j] = a[j + 1];
          a[j + 1] = tmp;
          flag = true; // 表示有数据交换
        }
      }
      if (!flag)
        break; // 没有数据交换，提前退出
    }
  }
}

//Java 代码实现
 public class ShellSort implements IArraySort {
     @Override
     public int[] sort(int[] sourceArray) throws Exception {
         // 对 arr 进行拷贝，不改变参数内容
         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
         int gap = 1;
        while (gap < arr.length) {
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
        return arr;
    }
}

public static void sort(int array[], int low, int high) {
  int index;
  if (low >= high) {
    return;
  }
  int i = low;
  int j = high;
  //基准点
  index = array[i];
  while (i < j) {
    //由小到大排列   好吧，通过代码知道了扫描的顺序，从右开始向左扫描，若是交换了元素，从左往右扫描，然后依次进行
    while (i < j && array[j] >= index) {
      j--; //从右向左扫描
    }
    if (i < j) {//说明上述array[j]<index,while循环跳出，该值放置在基准左侧
      array[i++] = array[j];
    }
    while (i < j && array[i] < index) {
      i++; //从左向右扫描
    }
    if (i < j) {//说明上述array[i]>index,while循环跳出，该值放置在基准右侧
      array[j--] = array[i];
    }
  }
  //最后把基准元素放上去
  array[i] = index;
  sort(array, low, i - 1);
  sort(array, i + 1, high);
}

public class 查找无序数组的第K大的数 {
  public static int kthSmallest(int[] arr, int k){
    // 前置校验
    if (arr == null || arr.length < k) {
      return -1;
    }
    // 对数组 A[0…n-1] 进行分区
    int partition = partition(arr, 0, arr.length - 1);
    //经过一轮分区
    while(partition + 1 != k){
      if(partition + 1 < k){//说明第K大元素出现在A[p+1…n-1]区间
        partition = partition(arr, partition + 1, arr.length - 1);
      }else{//说明第K大元素出现在A[1…p-1]区间
        partition = partition(arr, 0, partition - 1);
      }
    }
    return arr[partition];//一次成功
  }
  private static int partition(int[] arr, int p, int r){
    int pivot = arr[r];
    int i = p;
    for(int j = p; j <= r-1; j++){
      // 这里要是 <= ，不然会出现死循环，比如查找数组 [1,1,2] 的第二小的元素   这操作真的秀
      if(arr[j] < pivot){//放基准元素左侧
        swap(arr, i, j);
        i++;
      }
    }
    swap(arr, i, r);
    return i;
  }
  private static void swap(int[] arr, int i, int j){
    if(i == j){
      return;
    }
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
}//时间复杂度O(n)

//使用分治的思想
public static void MergeSort(int array[], int p, int r) {
  if (p < r) {
    int q = (p + r)/2;
    MergeSort(array, p, q);
    MergeSort(array, q + 1, r);
    Merge(array, p, q, r);
  }
}
//Merge的作用：将已经有序的A[p…q]和A[q+1…r]合并成一个有序的数组，并且放入A[p…r]。
public static void Merge(int array[], int p, int q, int r) {
  int i, j, k, n1, n2;
  n1 = q - p + 1;
  n2 = r - q;
  int[] L = new int[n1];
  int[] R = new int[n2];
  for(i = 0, k = p; i < n1; i++, k++){
    L[i] = array[k];
  }
  for(i = 0, k = q + 1; i < n2; i++, k++){
    R[i] = array[k];
  }
  //相当于合并两条有序的链表  由大到小排列
  for(k = p, i = 0, j = 0; i < n1 && j < n2; k++){
    if (L[i] > R[j]) {
      array[k] = L[i];
      i++;
    } else {
      array[k] = R[j];
      j++;
    }
  }
  if(i < n1){
    for (j = i; j < n1; j++, k++){
      array[k] = L[j];
    }
  }
  if(j < n2){
    for (i = j; i < n2; i++, k++){
      array[k] = R[i];
    }
  }
}