数据结构与算法-排序

冒泡排序

冒泡排序是最基础，最经典的排序算法。联想一下可乐，最大的气泡总是会最快的上升到最上面。所以，冒泡的原理就是，对于一个数组， 每一次循环都让最大的元素冒泡到最后面 。
核心规则：

1. 从数组的第一个元素开始，比较相邻两个元素的大小；
2. 如果前者比后者大，就交换位置；
3. 如果后者比前者大，位置不改变；
4. 依次后移，每次循环都让最大的元素排到最后面。

代码如下：

// 冒泡排序
public static void bubbleSort(int[] array) {
    // 1. 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次
    for (int i = 0; i < array.length; i++) {
        // 2. 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因为之后的元素都已经是最大的了
        for (int j = 0; j < array.length - i - 1; j++) {
            //3. 交换元素
            if (array[j] > array[j + 1]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

时间复杂度分析

比较的次数为：

N + (N - 1) + (N - 2) + ... + 2 + 1 = (N^2 + N)/2

最坏情况下，每次比较都要交换，所以交换的次数为 (N^2 + N)/2
所以时间复杂度为 O(N^2) 。

选择排序

选择排序的重点在于 选择 ，每次从剩余数组中， 选择最大或者最小 的一个，放到数组的一端。
核心规则：

1. 维护两个变量，一个用来存储当前最大值，另一个用来存储最大值的索引
2. 将当前最大值依次与后面的元素进行比较，如果比当前最大值大，就更新最大值及其索引
3. 遍历结束，将最大值放到数组的最右边，即将最右边的元素位置和最大值的位置进行交换
4. 重复上面的步骤，直到完成排序

代码如下：

// 选择排序
  public static void selectSort(int[] array) {
    // 遍历N次，每次选择数组剩余元素中最大的元素
    for (int i = 0; i < array.length; i++) {
      // 暂时把第一个元素当做最大元素，并且记录最大元素的索引
      int maxIndex = 0;
      int max = array[0];
      // 注意 j 从 索引1 开始，到 array.length - i 截止
      for (int j = 1; j < array.length - i; j++) {
        // 如果元素大于当前最大值，则替换 max，maxIndex
        if (array[j] > max) {
          max = array[j];
          maxIndex = j;
        }
      }
      // 交换最大值元素 和 数组末尾元素
      int temp = array[maxIndex];
      array[maxIndex] = array[array.length - i - 1];
      array[array.length - i - 1] = temp;
    }
  }

时间复杂度分析

比较次数：

N + (N - 1) + (N - 2) + ... + 2 + 1 = (N^2 + N)/2

冒泡 vs 选择

和冒泡排序一样，时间复杂度为 O(N^2) ，但是明显 选择排序要快一点 ，因为冒泡排序需要频繁的交换相邻的两个元素，而选择排序每次遍历只需要交换一次，所以 选择排序真实情况速度要比冒泡快一倍 。

插入排序

插入排序的重点是 插入 ，每次抽离一个元素当作临时元素，将临时元素依次和后面的元素比较，通过比较的大小移动后面元素的位置，找到临时元素最合适的位置插入。
核心规则：

1. 第一轮，先将倒数第二个元素抽离作为临时元素
2. 将临时元素与后面的元素进行比较，如果后面的元素小于临时元素，则后面的元素左移
3. 如果后面的元素大于临时元素，或者已经到达数组末尾，就将临时元素插入当前空隙位置
4. 重复上面步骤，完成排序

插入排序已经不是选择最大元素，而是通过每次迭代，将部分元素排好序，以达到全部排序的效果。
这里用图解来解释以上步骤：

1. 第一次迭代

1. 第二次迭代

1. 第三次迭代

可以看到，每次迭代都将 末尾元素排好序 。
代码如下：
一定要记得处理到达尾部的情况。

 // 插入排序
  public static void insertSort(int[] array) {
    // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
    for (int i = array.length - 2; i >= 0; i--) {
      // 存储当前抽离的元素
      int temp = array[i];
      // 从抽离元素的右侧开始遍历
      int j = i + 1;
      while (j <= array.length - 1) {
        // 如果某个元素，小于临时元素，则这个元素左移
        if (array[j] < temp) {
          array[j - 1] = array[j];
        } else {
          // 如果大于，则直接将临时元素插入，然后退出循环。
          array[j - 1] = temp;
          break;
        }
        j++;
      }
      // 处理到达尾部的情况
      if (j == array.length) {
        array[j - 1] = temp;
      }
    }
  }

也可以抽离第二个元素，比较其和前面的有序数组的大小来找到合适的位置。代码比较简洁：

/**
     * 插入排序
     * 每次在排好序的数组中找到合适的位置插入
     * 插入排序的大部分时间都浪费在了移动元素上面
     * 升序-具体算法：
     * 1.将第一个元素作为有序数组，抽离后面一个元素
     * 2.从后向前扫描有序数组
     * 3.如果元素大于抽离的元素，就向后移动一位
     * 4.直到找到小于或者等于抽离元素的元素，将抽离元素插入到它的后面
     * @param nums
     */
    public static void insertSorted(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > temp) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = temp;
        }
    }

时间复杂度分析

• 最好情况下，数组本身就是升序的，每次迭代不需要进行移动，那么时间复杂度就是 O(N)
• 最坏情况下，数组为降序排列，每次迭代每次比较都需要进行移动，那么比较次数为 (N^2 + N)/2 ,

移动次数为 (N^2 + N)/2 ,时间复杂度为 O(N^2)

冒泡 vs 选择 vs 插入

冒泡相比较而言肯定是最差的。
选择和插入就要分情况而定了，如果数组本身有很多元素就已经按照希望的顺序排好序了，那就使用插入排序，否则就使用选择排序。

插入排序的进阶-二分插入排序

插入排序的核心逻辑是找到临时元素的插入位置，而且是在 有序 数组中查找临时元素需要插入的位置，这就立刻可以想到 二分查找 。
所以可以写一个二分查找函数，用来查找元素的插入位置：

// 查找应该插入的索引位置
public static int searchIndex(int[] array, int left, int right, int aim) {
    // 循环查找节点位置
    while (left < right) {
        int middle = (left + right) / 2;
        if (array[middle] < aim) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    // 根据当前元素和目标元素进行对比，判断是否需要插入到当前元素之前
    if(array[left] > aim){
        return left -1;
    }
    // 否则就是当前位置
    return left;
}

修改插入排序的代码：

// 插入排序
public static void insertSort(int[] array) {
    // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
    for (int i = array.length - 2; i >= 0; i--) {
        // 存储当前抽离的元素
        int temp = array[i];
        int index = searchIndex(array, i + 1, array.length - 1, temp);
        // #1. 根据插入的索引位置，进行数组的移动和插入
        int j = i + 1;
        while (j <= index) {
            array[j - 1] = array[j];
            j++;
        }
        array[j - 1] = temp;
    }
}

注释 #1 处，已经找到了抽离元素的插入位置 index ，就需要让小于抽离元素的元素左移，然后插入 temp 。

归并排序-分治思想

分治就是将一个大问题分解为几个子问题进行求解，最后再合并几个子问题的解得到原问题的解。分治常常和递归一起使用。
生活中就有很多这样的例子，在疫情期间学校就有统计任务，学校会将任务分配给各个学院的院长，再由院长分配给各个年纪辅导员，辅导员再分配给各个班级的班长….

而利用分治的思想就实现了归并排序~
归并排序的核心思想就是将要排序的数组分解为小数组，将小数组排好序进行合并就得到排序数组。

    public static void main(String[] args) {
        int[] nums = {2,45,6,8,43,24,0};
         mergeSort(nums,0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
    /**
     * 归并排序 - 分治
     * 归并排序是先将数组拆分然后分别排好序再合并
     * 重点在于将两个排好序的数组进行合并
     * @param arr
     * @param left
     * @param right right = nums.length - 1,注意下标越界问题
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (right <= left) return;
        int mid = (left + right) >> 1;//右移一位相当于除以2
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    /**
     * 将两个排好序的数组进行合并，并且保证合并之后的数组是排好序的
     * 具体算法：
     * 首先需要维护一个中间数组temp,用来放合并的元素
     * 循环遍历两个子数组，放入temp中
     * 记得将最后剩余的元素放入temp
     * 再复制
     给原数组
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        //i表示左数组的第一个元素的下标，j表示右数组的第一个元素下标，k用来记录放入temp中的元素个数
        int i = left,j = mid + 1,k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
        }
        //System.arraycopy(temp, 0, arr, left, temp.length);
    }

快速排序 - 分治

快排也用到了分治的思想，但是和归并排序刚好是反过来的。
归并是先排序左右子数组，然后将有序子数组进行合并排序；快排是先调配出左右子数组，然后对两个子数组进行排序。
所以，快排的重点是如何调配出左右子数组。

1. 我们可以通过找到一个基准元素（这个基准元素可以随便选）
2. 将数组元素分别与基准元素比较
3. 比基准元素大的就放右边，比基准元素小的就放左边
4. 然后对分出的两个子数组进行排序
5. 达到全部排好序 ```java /**
   • 快速排序
   • 快排是通过一个基准元素，将数组分为小于基准元素和大于基准元素的两个子数组
   • 然后分别排序以达到全排好序
   • @param arr
   • @param begin
   • @param end / public static void quickSorted(int[] arr, int begin, int end) { if (end <= begin) return; int pivot = partition(arr, begin, end); quickSorted(arr, begin, pivot - 1); quickSorted(arr, pivot + 1, end); } /*
   • 这个方法的作用就是返回基准元素pivot的下标
   • 且保证pivot左侧的元素都小于pivot，右侧的元素都大于pivot
   • 方法巧妙的地方在于维护一个变量counter记录小于pivot的数量，counter初始化为begin，
   • 只要有小于pivot的元素就和counter交换位置，最后counter就是基准元素的下标位置
   • @param arr
   • @param begin
   • @param end
   • @return */ private static int partition(int[] arr, int begin, int end) { //基准元素随便选 int pivot = end, counter = begin; for (int i = begin; i < end; i++) {

      if (arr[i] < arr[pivot]) {
          int temp = arr[counter];
          arr[counter] = arr[i];
          arr[i] = temp;
          counter++;
      }

     } int temp = arr[pivot]; arr[pivot] = arr[counter]; arr[counter] = temp; return counter; }

```