首页 algorithm sort

# 交换排序

# 冒泡排序

思路：从底部开始，两两比较，最小的上浮冒泡。

代码：

public class BubbleSort {
  int[] array;
  public BubbleSort(int[] array) {
    this.array = array;
  }
  public void sort() {
    int i, j;
    for (i = 0; i < array.length - 1; i++) {
      // 1. 从尾部（底部）开始
      for (j = array.length - 1; j > 0; j--) {
        // 2. 两两比较      
        if (array[j] < array[j - 1]) {
        　//　3. 小的上浮（冒泡）
          swap(j, j - 1);
        }
      }
    }
  }
  private void swap(int i, int j) {
    array[i] -= array[j];
    array[j] += array[i];
    array[i] = array[j] - array[i];
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println("");
  }
  public static void main(String args[]) {
    int[] array = { 1, 7, 4, 9, 2, 8, 3, 6, 5};
    BubbleSort bs = new BubbleSort(array);
    // before sort
    bs.display();
    bs.sort();
    // after sort
    bs.display();
  }
}
# 快速排序
思路：
  1. 分区：基准值的插入位置。
  2. 分治：基准值两边重复快速排序。
分区：
  1. 找基准值；尾部。
  2. 左边向右边方向一直扫描，直到比 pivot 大，low 插入到 height 位置。
  3. 右边向左边方向一直扫描，直到比 pivot 小，height 插入到 low 位置。
  4. low = height，pivot 插入到 low 与 height 重叠的位置。
  5. 返回插入位置。
代码：
public class QuickSort {
  int[] array;
  public QuickSort(int[] array) {
    this.array = array;
  }
  public void sort() {
    this.quickSort(0, array.length - 1);
  }
  private void quickSort(int low, int height) {
    if (low < height) {
      int p = partition(low, height);
      quickSort(low, p - 1);
      quickSort(p + 1, height);
    }
  }
  private int partition(int low, int height) {
    // 找基准值，尾部
    int pivot = array[height];
    // 循环条件
    while(low<height) {
　　　// 左边扫描　
      while(low < height && array[low] <= pivot) {
        low++;
      }
      // 左边的值大，跟右边交换
      array[height] = array[low];
      // 右边扫描
      while(low < height && array[height] >= pivot) {
        height--;
      }
      // 右边的值小，跟左边交换
      array[low] = array[height];
    }
    //low 与 height 重合，插入 pivot
    array[low] = pivot;
    // 找出插入的位置
    return low;
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println("");
  }
  public static void main(String[] args) {
    int[] array = { 5, 7, 3, 4, 8, 2, 9, 1, 6};
    QuickSort qs = new QuickSort(array);
    // before sort
    qs.display();
    qs.sort();
    // after sort
    qs.display();
  }
}
# 选择排序
# 直接选择排序
思路：每趟排序选择最小的值。
代码：
public class SelectSort {
  private int[] array;
  public SelectSort(int[] array) {
    this.array = array;
  }
  public void sort() {
    int min, i, j;
    for (i = 0; i < array.length - 1; i++) {
      // 1. 这趟排序，第一个最小
      min = i;
      // 2. 往后找比当前更小的值
      for (j = i + 1; j < array.length; j++) {
      　// 3. 设置更小的值的下标
        if (array[j] < array[min])
          min = j;
      }
      // 4. 最小值插入到这趟排序的开头位置
      swap(i, min);
    }
  }
  print void swap(int i, int j) {
    array[i] -= array[j];
    array[j] += array[i];
    array[i] = array[j] - array[i];
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println();
  }
  public static void main(String[] args) {
    int[] array = {5, 2, 3, 7, 4, 9, 1, 8, 6};
    SelectSort ss = new SelectSort(array);
    // before sort
    ss.display();
    ss.sort();
    // after sort;
    ss.display();
 }
}
# 堆排序
思路：
  1. 将[0,n−1][0, n - 1] 个元素建立成大根堆。
  2. 第一个肯定是最大的，将第一个与最后一个交换。
  3. 继续将[0,n−2][0, n - 2] 个元素建立成大根堆。
  4. 继续第 2 步骤，直到元素从右往左排序好。
代码：
public class HeapSort {
  private int[] array;
  public HeapSort(int[] array) {
    this.array = array;
  }
　/**
　 * 建立大根堆：
　 * 1. 左右节点比较，选择最大者；
　 * 2. 第 1 步的结果再与父节点比较，选择最大者
　 */
  private void maxHeapify(int i, int len) {
  　// 左节点
    int left = (i << 1) + 1;
    // 右节点
    int right = left + 1;
    // 默认左节点最大
    int max = left;
    // 左节点不存在，返回
    if (left > len) return;
    // 右节点存在且大于左节点，然后交换
    if (right <= len && array[right] > array[left]) {
      max = right;
    }
    /* 最大的值再与父节点比较，
     * 如果比父节点大，则交换父节点，
     * 但这样会改变了该节点下的大根堆属性，
     * 则继续修复该节点下的关系。
     */
    if (array[i] < array[max]) {
      swap(i, max);
      maxHeapify(max, len);
    }
  }
  public void sort() {
    int len = array.length - 1;
    int beginIndex = len >> 1;
    // 从最后一个父节点开始，到开头，循环建堆
    for (int i = beginIndex; i >= 0; i--) {
      maxHeapify(i, len);
    }
    // 第一个与最后交换，再重新建堆
    for (int i = len; i > 0; i--) {
      swap(0, i);
      maxHeapify(0, i - 1);
    }
    
  }
  private void swap(int i, int j) {
    array[i] -= array[j];
    array[j] += array[i];
    array[i] = array[j] - array[i];
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println("");
  }
  public static void main(String args[]) {
    int[] array = {1, 7, 4, 9, 2, 8, 3, 6, 5};
    HeapSort hs = new HeapSort(array);
    // before sort
    hs.display();
    hs.sort();
    // after sort
    hs.display();
  }
}
# 插入排序
# 直接插入排序
思路：类似打牌时采用的排序方式。
  1. 分有序区和无序区。
  2. 将无序区中的第一个元素插入到有序区的适合位置中。（在有序区中：从右往左扫描）
代码：
public class InsertSort {
  int[] array;
  public InsertSort(int[] array) {
    this.array = array;
  }
  public void sort() {
    int i, j, tmp;
    for (i = 1; i < array.length; i++) {
      // 1. 抽出无序区第一张牌，记录无序区第一个元素；
      tmp = array[i];
　　　
　　　// 2. 有序区，从右往左，如果比 tmp 大，则往后移；
      for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
          array[j + 1] = array[j];
      }
      // 3. 在有序区合适位置插入
      array[j + 1] = tmp;
    }
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println("");
  }
  public static void main(String args[]) {
    int[] array = { 1, 7, 4, 9, 2, 8, 3, 6, 5};
    InsertSort is = new InsertSort(array);
    // before sort
    is.display();
    is.sort();
    // after sort
    is.display();
  }
}
# 希尔排序
思路：按一定增量的直接插入算法。
代码：
public class ShellSort {
  int[] array;
  public ShellSort(int[] array) {
    this.array = array;
  }
  public void sort() {
    int i, j, gap, tmp;
    // 1. 增量每次递减，直到 gap =1
    //gap 每次减半
    for (gap = array.length >> 1; gap > 0; gap >>= 1) {
      for (i = gap; i < array.length; i++) {
        tmp = array[i];
        for (j = i - gap; j >= 0 && array[j] > tmp; j-=gap) {
            array[j + gap] = array[j];
        }
        array[j + gap] = tmp;
      }
    }
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println("");
  }
  public static void main(String args[]) {
    int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    ShellSort is = new ShellSort(array);
    // before sort
    is.display();
    is.sort();
    // after sort
    is.display();
  }
}
# 合并排序
# 合并排序
思路：已经排好的两个数组合并到新的数组上。
代码：
public class MergeSort {
  int[] array;
  public MergeSort(int[] array) {
    this.array = array;
  }
  public void sort() {
    // 1. 复制一份，将会合并到该新的数组上
    int[] result = new int[array.length];
    this.mergeSortRecursive(array, result, 0, array.length - 1);
  }
  public void mergeSortRecursive(int[] array, int[] result, int start, int end) {
    if (start >= end) {
      return;
    }
    // 2. 从中间分隔开两个数组
    int len = end - start;
    int mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    // 3. 排好第一个数组
    mergeSortRecursive(array, result, start1, end1);
    // 4. 排好第二个数组
    mergeSortRecursive(array, result, start2, end2);
    int k = start;
    // 5. 将两个排好的数组，合并到新数组上
    while(start1 <= end1 && start2 <= end2) {
      result[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    }
    // 6. 两个数组同时扫描，
    // 肯定有一个数组先结束，
    // 所以还要判断另外一个数组是否结束。
    while(start1 <= end1) {
      result[k++] = array[start1++];
    }
    while(start2 <= end2) {
      result[k++] = array[start2++];
    }
    // 再复制回给原来的数组
    for (k = start; k <= end; k++) {
      array[k] = result[k];
    }
  }
  public void display() {
    for (int e : array) {
      System.out.print(e + " ");
    }
    System.out.println("");
  }
  public static void main(String[] args) {
    int[] array = { 1, 7, 4, 9, 2, 8, 3, 6, 5};
    MergeSort ms = new MergeSort(array);
    // before sort
    ms.display();
    ms.sort();
    // after sort
    ms.display();
  }
}