Pandaer 杂货铺

Appearance

多种多样的排序算法 ​

排序算法简单又基础，因为简单，我们很难在面试的场合遇到，因为基础，排序中很多解决问题的思路都会在很多地方有所体现。我们借着学习排序算法，去学习一些解决问题的思路。学习解决问题的思路才是我们的关键。很多文章都是从冒泡排序开始，然后进一步讲解归并排序，然后就是快速排序。但是我认为排序算法中我们最应该学习的是快速排序和归并排序，所以我们从归并排序开始

不过在探讨排序算法之前，我们先来看看排序算法的衡量指标，算法有两个衡量指标，一个是时间复杂度，一个是空间复杂度，而排序算法就多了两个，一个是原地性，一个是稳定性。原地性不需要过多的解释，就是有没有申请额外的空间存储数组中的内容，而稳定性主要就是如果元素数据相等，排序后的数据与排序前的数据，先后数据不变，主要作用主要是在多维度排序中使用。

归并排序 ​

所有的排序算法都是一些专门的研究人员提出来的，而我们要学习的是算法的处理思路，各个算法的优劣，然后在合适的场景选择合适的算法。至于为什么要这样操作需要很多前置知识，不是现在的我们能解释过来的，如果你感兴趣，可以去深入研究一下，里面充满了“数学的美”。好，说回来，归并排序的核心思路是这样的：将一个大数组分为两个小数组，我们先保证两个小数组有序，然后利用小数组有序的结果去推导出大数组有序的结果。仔细思考这个过程，这就是分治的思路，利用小问题的解(两个有序的小数组)去推导大问题(有序的大数组)的解。而这个推导的过程，我们通常称为merge，即合并，由于是在递归的归的过程中执行的合并操作，也被叫做归并，由于这个算法解决的是排序问题，所以整个算法被我们称为归并排序。

思路是大佬想出来的，但是代码我们却可以自己写出来。下面就是我写的参考代码

java
public class Code01_MergeSort {

    public void mergeSort(int[] arr, int n) {
        mergeSort_r(arr, 0, n - 1);
    }

    public void mergeSort_r(int[] arr, int start,int end) {
        if (start >= end) return;

        // 大变小
        int mid = start + (end - start) / 2; // 一分为二
        mergeSort_r(arr, start, mid);
        mergeSort_r(arr, mid + 1, end);

        // 合并
        merge(arr,start,mid,end);
    }

    private void merge(int[] arr, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            tmp[k++] = arr[i++];
        }

        while (j <= end) {
            tmp[k++] = arr[j++];
        }

        // 拷贝回去
        System.arraycopy(tmp, 0, arr, start, tmp.length);
    }
}

在这段代码中，我们可以复用的思路是merge的思路即如何将两个有序的小数组合并为一个有序的大数组。大致的思路就是：双指针 + 临时数组。

接下来我们来分析一下归并排序的衡量指标

  1. 时间复杂度：通过递归树分析，时间复杂度是O(nlogn)
  2. 空间复杂度：额外的空间是函数调用栈以及临时数组，函数调用栈是logn,临时数组是n,综合就是O(n)
  3. 是否原地：非原地算法
  4. 是否稳定：是稳定算法

快速排序 ​

快速排序是工业界常用的算法，比如JDK中的数组排序就用到了快速排序。快速排序的核心思路具体是这样的：从数组中选定一个target，将所有比target大的放数组的右边，将比target小的放数组的左边，自己放中间，这个过程称为分区。然后在大于target区域执行这个过程，在小于target区域执行这个过程。

同样给出参考代码

java
public void quickSort(int[] arr, int n) {
        quickSort_r(arr, 0, n - 1);
    }


    public void quickSort_r(int[] arr, int start,int end) {
        if (start >= end) return;

        // 分区
        int index = partition(arr,start,end);

        // 递归这个过程
        quickSort_r(arr,start,index-1);
        quickSort_r(arr,index+1,end);
    }

    private int partition(int[] arr, int start, int end) {
        int left = start -1;
        int right = end;

        int target = arr[end];
        while (left + 1 < right)  {
            if (arr[left + 1] < target) {
                left++;
            }else {
                // 交换
                swap(arr,right-1,left + 1);
                right--;
            }
        }

        swap(arr,left + 1,end);
        return left + 1;
    }

    private void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

在这段代码中，我们需要学习并熟练练习的技巧，是在不利用辅助数组的情况下，实现让数组中的一些数放左边，另外一些数放右边。也就是partition函数的具体逻辑。

  1. 时间复杂度：通过递归树分析，时间复杂度是O(nlogn)
  2. 空间复杂度：额外的空间是函数调用栈，即O(logn)
  3. 是否原地：原地算法
  4. 是否稳定：不是稳定算法

需要注意的是，快速排序的时间复杂度与分区是否均匀有很大关系，在极端情况下，时间复杂度会退化为O(n^2),即每次分区都分为这样长度的两个分区，一个分区长度为1，一个分区长度为len-1。

其他排序算法 ​

在其他的排序算法中，我们可借鉴的技巧就不多了，基本上就是按照思路就可以实现，这里就不过多的介绍了。可能后面会补充，但是现在不会。

  1. 冒泡排序
  2. 插入排序
  3. 选择排序