排序(上)

都升序排列

冒泡

​ 代码, 每一趟都找出最大的数沉底，比较相邻的两个元素，时间复杂度O(n*n)

​ 冒泡算法是稳定的，对于相同的两个值，冒泡排序不会改变它们的相对位置。

public void bubbleSort(int[] nums) {
  for (int i = 0; i < nums.length - 1; i++) {
    for (int j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        int t = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = t;
      }
    }
  }
}

选择

​ 选择排序是按顺序取出元素，并将当前元素与后面所有元素进行比较，如果后面元素小于该当前元素，则交换位置，保证每一趟选择排序都可以得到剩下数组元素中的最小值。

public void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = arr[i]; //最小值
        int index = i; //最小值的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                index = j;
            }
            
        } 
        
        if (index != i) {
            arr[index] = arr[i];
            arr[i] = min;
        }
    }
}

​ 选择排序的时间复杂度也是 O(n*n)，但是选择排序不稳定，在一轮排序中很有可能，例子如下是

现在有一个数组: int[] arr = {2,3,12,2,1}
进行第一轮选择时，min = arr[0] = 2， 最后arr[0] 会与arr[4] = 1 交换位置，
结果: int arr[] = {1,3,12,2,2},
此时，两个相同的数字的相对位置发生了变化，所以选择排序是不稳定的。

插入

​ 插入排序，遍历数组，将当前数组插入到在他之前的数组中，因为前面的数组已经排好序了，插入排序，会比较上一个元素，直到找到比自己小的元素，此时就是该元素的插入位置。

(PS: 忽略这个30上面的箭头。。。。)

在进行比较的过程中，如果前一个元素大于当前元素，则会让其数组后移。代码如下

public void insertSort(int[] nums) {
  for (int i = 0; i < nums.length; i++) {
    int insertVal = nums[i];
    int insertIndex = i;
    while (insertIndex >= 1 && insertVal < nums[insertIndex - 1]) {
      nums[insertIndex] = nums[insertIndex - 1];
      insertIndex--;
    }
    if (insertIndex != i) {
      nums[insertIndex] = insertVal;
    }
  }
}

​ 插入排序的时间复杂度也是O（n*n）, 并且很明显是稳定排序。

希尔排序

​ 希尔排序是基于插入排序改良过的，通过一个增量，来把数组分成若干小组，然后在进行插入排序，然后缩短增量，再来进行分组，在使用插入排序。到最后就只剩一组了，这个时候的数组的较小的值都会在数组前面，较大的值都会在数组后面，再来进行插入排序的话，会比较快。

​ 假设有一个数组如下

​

​ 定义一个增量gap，让gap = arr.length / 2, 即gap=5，那么就把数组分成了五组，步长是5.

进行插入排序之后。如下

进行第二次分组，gap = gap/2 = 5/2 = 2。被分为两组。并进行插入排序

在将增量缩短，gap = gap /2 = 1。则被分为一组，这个时候的数组已经将较小的数全部放在前面，较大值放在后面了，最后再进行插入排序。

代码如下

public void shellSort(int[] nums) {
  for (int step = nums.length / 2; step > 0; step /= 2) {
    for (int i = step; i < nums.length; i++) {
      int insertVal = nums[i];
      int insertIndex = i;
      if (nums[insertIndex] < nums[insertIndex - step]) {
        while (insertIndex - step >= 0 && nums[insertIndex - step] > insertVal) {
          nums[insertIndex] = nums[insertIndex - step];
          insertIndex -= step;
        }
        if (insertIndex != i) {
          nums[insertIndex] = insertVal;
        }
      }
    }
  }
}

希尔排序的时间复杂度是： O（nlogn），并且不稳定。