Java: Sort

 选择排序:

  protected static void selectSort(int[] array){
    int tmp;
    int minIndex;
    for(int i = 0; i < array.length - 1; i++){
      minIndex = i;
      for(int j = i + 1; j < array.length; j++){
        if(array[j] < array[minIndex]){
          minIndex = j;
        }
      }
      if(minIndex != i){
        tmp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = tmp;
      }
    }
  }

插入排序:

  protected static void insertSort(int[] array){
    int tmp;
    for(int i = 1; i < array.length; i++){
      tmp = array[i];
      int j = i - 1;  // 有序区最大索引
      while(j >= 0){
        if(array[j] > tmp){
          array[j + 1] = array[j];
        }else{
          // array[j + 1] = tmp;  // 不能在此处, tmp为最小值时, 不会执行
          // System.out.printf("\033[37;7m %s -- %s \033[0m\n", j + 1, tmp);
          break;
        }
        j--;
      }
      array[j + 1] = tmp;  // j + 1
      // System.out.println("\033[37;7m>>>>>> " + Arrays.toString(array) + " <<<<<<\033[0m");
    }
  }

 for循环格式插入

public class Sort{
  public static void main(String[] args){
    Random random = new Random(System.currentTimeMillis());
    int[] ints = new int[10];
    for(int i = 0; i < ints.length; i++){
      ints[i] = random.nextInt(10) + 1;
    }

    int[] copy = Arrays.copyOfRange(ints, 0, ints.length);
    Arrays.sort(copy);
    System.out.println("\033[37;7m>>>>>> " + Arrays.toString(copy) + " <<<<<<\033[0m");
    System.out.println("\033[37;7m>>>>>> " + Arrays.toString(ints) + " <<<<<<\033[0m");
    shellSort(ints);

    System.out.println("\033[37;7m>>>>>> " + Arrays.toString(ints) + " <<<<<<\033[0m");
  }

  private static void shellSort(int[] array){
    if(array.length < 2)
      return;

    // [7, 7, 3, 10, 6, 1, 3, 8, 3, 2]
    // [7, 7, 7, 7, 7, 7, 7, 7, 8, 10]
    int key;
    int cursor;
    for(int i = 1; i < array.length; i++){
      key = array[i];
      for(cursor = i - 1; cursor >= 0; cursor--){
        if(key < array[cursor]){
          array[cursor + 1] = array[cursor];
        }else{
          // array[cursor + 1] = key;  // 当key为最小值时, for循环结束没有把key赋值给有序区的最小值(即 cursor+1)
          break;
        }
      }
      array[cursor + 1] = key;  // 必须等for循环结束时, 才能找到key的位置
    }
  }

}

private static void shellSort(int[] array){
    if(array.length < 2)
      return;

    int key;
    int cursor;
    for(int i = 1; i < array.length; i++){
      key = array[i];
      cursor = i - 1;
      while(cursor >= 0){
        if(key < array[cursor]){
          array[cursor + 1] = array[cursor];
        }else{
          break;
        }
        cursor--;
      }
      array[cursor + 1] = key;
    }
  }

希尔排序

public class Sort{
  public static void main(String[] args){
    Random random = new Random(System.currentTimeMillis());
    int[] ints = new int[10];
    for(int i = 0; i < ints.length; i++){
      ints[i] = random.nextInt(10) + 1;
    }

    int[] copy = Arrays.copyOfRange(ints, 0, ints.length);
    Arrays.sort(copy);
    System.out.println("\033[37;7m>>>>>> " + Arrays.toString(copy) + " <<<<<<\033[0m");
    System.out.println("\033[37;7m>>>>>> " + Arrays.toString(ints) + " <<<<<<\033[0m");
    shellSort(ints);

    System.out.println("\033[37;7m>>>>>> " + Arrays.toString(ints) + " <<<<<<\033[0m");
  }

  private static void shellSort(int[] array){
    if(array.length < 2)
      return;

    int key, cursor;
    // step不断变小, 分组随之变少, 分组数 = step
    for(int step = array.length / 2; step > 0; step /= 2){
      // i++: 才能保证所有分组比较, i+=step: 只进行了一个分组迭代
      /**
       * 迭代过程(设有三个分组0,1,2): 迭代过程每个分组的有序区不断交替变大
       * 第一轮: 0,1,2 每个分组有序区+1 => 2
       * 第二轮: 0,1,2 每个分组有序区+1 => 3
       * 第三轮: 0,1,2 每个分组有序区+1 => 4
       * ...
       */
      for(int i = step; i < array.length; i++){
        key = array[i];
        cursor = i - step;
        while(cursor >= 0){
          if(key < array[cursor]){
            array[cursor + step] = array[cursor];
          }else{
            break;
          }
          cursor -= step;
        }
        array[cursor + step] = key;
      }
    }
  }
}

单边快排

private static void quickSort(int[] array, int low, int high){
    if(low > high){  // low==high: 分区只有一个值,  low>high: pivot为分区极小值,  pivot为分区极大值: 此时右分区low为high+1, 不满足条件
      return;
    }
    int base = partition(array, low, high);
    quickSort(array, low, base - 1);  // 左分区
    quickSort(array, base + 1, high);  // 右分区

  }

  private static int partition(int[] array, int low, int high){
    int pivot = array[high];
    int base = low;
    int tmp;
    for(int cursor = base; cursor < high; cursor++){  // base左边的值小于pivot
      if(array[cursor] < pivot){
        if(cursor != base){
          tmp = array[cursor];
          array[cursor] = array[base];
          array[base] = tmp;
        }
        base++;  // base右移
      }
    }

    if(base != high && array[base] != array[high]){  // base==high, pivot为分区最大值
      tmp = array[base];
      array[base] = pivot;
      array[high] = tmp;
    }

    return base;
  }

双边快排

private static void doubleQuickSort(int[] array, int low, int high){
    // System.out.printf("\033[37;7m low: %d, high: %d \033[0m\n", low, high);
    if(low >= high)
      return;
    int partition = partition(array, low, high);
    doubleQuickSort(array, low, partition - 1);
    doubleQuickSort(array, partition + 1, high);
  }

  private static int partition(int[] array, int low, int high){
    int pivot = array[low];
    int lowCursor = low + 1;
    int highCursor = high;
    int tmp;
    while(lowCursor < highCursor){
      while(pivot < array[highCursor]){
        highCursor--;
      }
      while(lowCursor < highCursor && array[lowCursor] <= pivot){
        lowCursor++;
      }
      if(lowCursor == highCursor){
        System.out.printf("\033[37;7m Cursor: %d, lowCursor == highCursor \033[0m\n", lowCursor);
        break;
      }else{
        tmp = array[lowCursor];
        array[lowCursor] = array[highCursor];
        array[highCursor] = tmp;
      }
    }
    tmp = array[highCursor];
    array[highCursor] = pivot;
    array[low] = tmp;

    return lowCursor;
  }

归并排序

  private static void mergeSort(int[] array, int low, int high){
    if(low < high){
      int mid = (low + high) / 2;
      mergeSort(array, low, mid);  // divide
      mergeSort(array, mid + 1, high);  // divide

      merge(array, low, mid, high);  // merge
    }
  }

  private static void merge(int[] array, int low, int mid, int high){
    int[] ints = new int[high - low + 1];
    int lowCursor = low;
    int highCursor = mid + 1;
    int intsCursor = 0;
    while(lowCursor <= mid && highCursor <= high){
      if(array[lowCursor] < array[highCursor]){
        ints[intsCursor++] = array[lowCursor++];
      }else{
        ints[intsCursor++] = array[highCursor++];
      }
    }

    while(lowCursor <= mid){  // [low, mid] 长
      ints[intsCursor++] = array[lowCursor++];
    }
    while(highCursor <= high){
      ints[intsCursor++] = array[highCursor++];
    }

    System.arraycopy(ints, 0, array, low, ints.length);
  }