选择排序 插入排序以及冒泡排序

选择排序 插入排序以及冒泡排序 选择排序

一种最简单的排序是这样的:首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置.再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换.如此往复,直到将整个数组排好序.代码比较简单.

public class Selection { //选择排序算法
  public static void main(String[] args) {
    int[] A = {9, 10, 7, 5, 4, 6, 2, 3, 2, 1, 0, 8};
    show(A);
    sort(A);
    assert isSorted(A);
    show(A);
  }
​
  public static void show(int[] A) {
    for (int i = 0; i < A.length; i++) {
      System.out.print(A[i] + " ");
    }
    System.out.println();
  }
  public static void sort(int[] A) {
    for (int i = 0; i < A.length; i++) {
      int min = i; //最小的元素下标设置为每次外层(大)循环的那个值
      for (int j = i + 1; j < A.length; j++) {
        if (A[min] > A[j]) { //每次小循环都找到最小元素的下标
          min = j;
        }
      }
      exah(A, i, min); //将大循环的当前下标的值与其之后最小的值交换
    }
  }
​
  public static void exah(int[] A, int i, int min) { //交换值函数
    int temp = A[i];
    A[i] = A[min];
    A[min] = temp;
  }
​
  public static boolean isSorted(int[] A) { //判断是否排序正确
    for (int i = 0; i < A.length; i++) {
      if (A[i] > A[i + 1])
        return false;
    }
    return true;
  }
}

其实选择排序进行一个小总结便是,首先设置两层循环,小循环每循环一轮便发生一次大循环当前下标与小循环里找到的最小的未排序的元素的交换.

插入排序

插入排序与选择排序一样,当前索引左边的元素都是有序的,但它们的最终位置还不确定,为了给更小的元素腾出空间,它们可能会向左移动,当索引到达元素的最左边时,排序就已经完成了.

public class Insertion { //选择排序算法
  public static void main(String[] args) {
    int[] A = {9, 10, 7, 5, 4, 6, 2, 3, 2, 1, 0, 8};
    show(A);
    sort(A);
    assert isSorted(A);
    show(A);
  }
​
  public static void show(int[] A) {
    for (int i = 0; i < A.length; i++) {
      System.out.print(A[i] + " ");
    }
    System.out.println();
  }
​
  public static void sort(int[] A) {
      for (int i = 1; i < A.length; i++) {
          for (int j = i; j > 0 && A[j - 1] > A[j]; j--) {
              exah(A, j - 1,j);
          }
      }
  }
​
  public static void exah(int[] A, int i, int min) { //交换值函数
    int temp = A[i];
    A[i] = A[min];
    A[min] = temp;
  }
​
  public static boolean isSorted(int[] A) { //判断是否排序正确
    for (int i = 0; i < A.length; i++) {
      if (A[i] > A[i + 1])
        return false;
    }
    return true;
  }
}

当然,选择排序有很多种写法,但上述写法或许是递推方式中比较简单的.

冒泡排序

public class Bubble { //选择排序算法
  public static void main(String[] args) {//冒泡排序
    int[] A = {9, 10, 7, 5, 4, 6, 2, 3, 2, 1, 0, 8};
    show(A);
    sort(A);
    assert isSorted(A);
    show(A);
  }
​
  public static void show(int[] A) {
    for (int i = 0; i < A.length; i++) {
      System.out.print(A[i] + " ");
    }
    System.out.println();
  }
​
  public static void sort(int[] A) {
      for (int i = 0; i < A.length-1; i++) {//第一层代表排序多少次,满足规律:循环次数等于数据元素个数-1
          for (int j = 0; j < A.length-i- 1; j++) {//第二层的两个值分别是0和大循环中间的值减去大循环当前下标
            if(A[j]>A[j+1])exah(A,j,j+1);
        }
    }
  }
​
  public static void exah(int[] A, int i, int min) { //交换值函数
    int temp = A[i];
    A[i] = A[min];
    A[min] = temp;
  }
​
  public static boolean isSorted(int[] A) { //判断是否排序正确
    for (int i = 0; i < A.length; i++) {
      if (A[i] > A[i + 1])
        return false;
    }
    return true;
  }
}

以上三种都是最简单的排序算法,其平均时间复杂度都为O(n^2),下表尝试列出了这三种最简单排序的时间复杂度,空间复杂度,稳定性等等.

三种排序的比较 排序方法最快时间时间复杂度空间复杂度稳定性选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n)O(n^2)O(1)稳定冒泡排序O(n)O(n^2)O(1)稳定