常见的排序算法梳理

下面列了几种比较常见面试可能会问到的排序算法，虽然我们平时使用的时候都是api直接调用，但是在面试中经常会考查这些内容。以下内容最好能完全掌握并且能手写出来。

一、冒泡排序

思路：需要两层循环，内层循环依次比较左右相邻的两个数字，如果大小关系与最终结果不一致则调换顺序，这样每一次完整的内层循环都会筛选出当前最大或最小的数，外层循环逐步缩小内层循环的范围。最终如果一次完整的内层循环没有发生交换则说明数组已经是有序的，可以提前退出算法。

时间复杂度：

图示：

代码：

public static int[] sort(int[] arr) {
    boolean sorted = true;
    for (int i = 0; i < arr.length - 1; i++) {
        sorted = true;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                sorted = false;
            }
        }
        System.out.println(Arrays.toString(arr));
        if (sorted) {
            return arr;
        }
    }
    return arr;
}

二、快速排序

思路：快速排序使用的是分而治之的方法。先取出一个基准值，然后处理整个数组，比它小的放在它的左边，比它大的放在它的右边，这样在数组处理完成时基准值一定在它正确的位置，这时我们再用同样的方法去处理它左边的数组和右边的数组。

时间复杂度：

图示：

代码：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int basePos = partition(arr, left, right);
        quickSort(arr, left, basePos - 1);
        quickSort(arr, basePos + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int i = left, j = right;
    int base = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= base) {//
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < base) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = base;
    return i;
}

三、选择排序

思路：依靠两层循环找出每一个位置上的数字

时间复杂度：

图示：

代码：

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

四、插入排序

思路：依次从数组的第二位开始取出一个数字，再依次与左边有序部分进行比较，将取出的数字插入对应的位置

时间复杂度：

图示：

代码：

public static void inertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int j = i;
        int temp = arr[i];
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }
        if ( j != i) {
            arr[j] = temp;
        }
        
    }
}

五、堆排序

思路：将数组抽象成完全二叉树，升序排列构建大根堆（父节点为最大值的完全二叉树），降序排列构建小根堆（父节点为最小值的完全二叉树）。每次构建完成后将根节点交换到数组的最后一位，再对n-1个数再进行前面进行的操作，直到所有数据都有序。

一个说的比较清楚的视频

时间复杂度：

图示：

代码：