必看：70分钟掌握7道排序算法（Java实现 + 详细过程图解）

必看：70分钟掌握7道排序算法（Java实现 + 详细过程图解）

必须掌握的算法基础题 - 排序篇

目录

1.直接插入排序 - insertSort

2.希尔排序 - shellSort

3.直接选择排序 - selectSort

4.堆排序 - heapSort

5.冒泡排序 - bubbleSort

6.快速排序 - quickSort

7.归并排序 - mergeSort

---

1.直接插入排序 - insertSort

* 时间复杂度
* 最坏 - O(n^2)   最好 - O(n)
* 空间复杂度：O(1)
* 稳定性：稳定的

算法思想：

        维护一个有序区，将数据一个一个插入到有序区的适当位置，直到整个数组都有序。即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

图解算法：

待排序数组：

int[] arr = {26, 15, 79, 56, 77, 30};

代码实现：

public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

优化版本：

public static void insertSort2(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }

---

2.希尔排序 - shellSort

* 时间复杂度:O(n^1.3) ~ O(n^1.5)
* 空间复杂度：O(1)
* 稳定性：不稳定

算法思想：

        希尔排序也叫做缩小增量排序，它通过先设置一个增量n，大小为数组长度的一半，将间隔为n的元素视作一个组，然后对每个组内部的元素进行从小到大进行插入排序；然后再将增量n缩小一半，再次进行分组插入排序，直到增量n为1，因为增量为1的时候，所有的元素都为同一个组了

        希尔排序是插入排序的改进版本，通过间隔提高排序效率，每次排序完数组趋于有序性更好。

图解算法：

public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

public static void shellSort(int[] array) {
        int[] drr = {4, 2, 1};
        for (int j : drr) {
            shell(array, j);
        }
    }

 优化版：

public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 3 + 1;
            // gap /= 2;
            shell(array, gap);
        }
    }

代码实现：

public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void shellSort(int[] array) {
        int[] drr = {4, 2, 1};
        for (int j : drr) {
            shell(array, j);
        }
    }

---

3.直接选择排序 - selectSort

* 时间复杂度:O(n^2)
* 空间复杂度：O(1)
* 稳定性：不稳定

算法思想：

        每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
        实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

代码实现：

public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

---

4.堆排序 - heapSort

* 时间复杂度:O(N * logN)
* 空间复杂度：O(1)
* 稳定性：不稳定

算法思想：（以大根堆为例，小根堆也可以实现）

1. 先建立大根堆，使要排序数组趋近于有序；
2. 堆顶元素和堆底元素交换，将最大值放置最后；
3. 将最大值固定不动，将end前面所有元素进行向下调整为大根堆；

这里要用到堆调整思想，下面也会将如何建大根堆的向下调整一并解释。

图解算法：

• 堆排序 - heapSort

待排序数组：

int[] arr = {26, 15, 79, 56, 77, 30};

 排序过程：

 排序算法

public static void heapSort(int[] array) {
        creatHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            shiftDown(array, 0, end);
            end--;
        }
    }

• 建立大根堆 - creatHeap

private static void creatHeap(int[] array) {
        // 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (array.length - 1 - 1) >> 1; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
    }

• 向下调整 - shiftDown

private static void shiftDown(int[] array, int parent, int len) {
//        int child = 2 * parent + 1;
        int child = (parent << 1) + 1;//一定要加括号，+优先级高于<<
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;

                parent = child;
                child = (parent << 1) + 1;
            } else {
                break;
            }
        }
    }

总体代码实现：

    private static void shiftDown(int[] array, int parent, int len) {
//        int child = 2 * parent + 1;
        int child = (parent << 1) + 1;//一定要加括号，+优先级高于<<
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;

                parent = child;
                child = (parent << 1) + 1;
            } else {
                break;
            }
        }
    }

    private static void creatHeap(int[] array) {
        // 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (array.length - 1 - 1) >> 1; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
    }


    public static void heapSort(int[] array) {
        creatHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            shiftDown(array, 0, end);
            end--;
        }
    }

---

5.冒泡排序 - bubbleSort

* 时间复杂度:O(n^2) - 不优化      O(n) - 优化
* 空间复杂度：O(1)
* 稳定性：稳定

算法思想：

        左边大于右边交换一趟排下来最大的在右边。

代码实现：

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

优化版本：加入一个flag，当本次遍历结果均有序，跳出本次循环。

public static void bubbleSort2(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

---

6.快速排序 - quickSort

* 时间复杂度:O(N*logN) - 最好    O(N^2) - 最坏
* 空间复杂度：O(logN) - 最好    O(N) - 最坏
* 稳定性：不稳定

算法思想：（递归和非递归）

总览：

1. 从待排序区间选择一个数，作为基准值(pivot)；
2.  Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
3. 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

图解算法：

• 挖坑法（在多数笔试情况下，默认均为挖坑法）

待排序数组：

int[] arr = {26, 15, 79, 56, 77, 30};

 1.找到每组基准值（挖坑+填坑）

public static int partition(int[] array, int start, int end) {
        int tmp = array[start];
        while (start < end) {
            while (start < end && array[end] >= tmp) {
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= tmp) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

2.分而治之

public static void quick(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivot = partition(array, low, high);
        quick(array, low, pivot - 1);
        quick(array, pivot + 1, high);
    }

代码实现：

划分基准：

挖坑法划分基准

private static int partition1(int[] array, int start, int end) {
        //这里是给的随机start值作为开始，此处可用三数取中法优化
        int tmp = array[start];
        while (start < end) {
            //end处的值如果大于tmp，则end向前走
            while (start < end && array[end] >= tmp) {
                end--;
            }
            //start值为空，先将新end处值放到start在进行判断
            array[start] = array[end];
            //start处的值如果小于tmp，则start向后走
            while (start < end && array[start] <= tmp) {
                start++;
            }
            //end处值为空，将start处值放入end
            array[end] = array[start];
        }
        //循环跳出时,(array[start] == array[end])start处为空，将tmp中值赋给start
        array[start] = tmp;
        //返回pivot基准下标
        return start;
    }

hoare法划分基准

private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static int partition2(int[] array, int start, int end) {
        int i = start;
        int j = end;
        int pivot = array[start];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            while (i < j && array[i] <= pivot) {
                i++;
            }
            swap(array, i, j);
        }
        swap(array, i, start);
        return i;
    }

 递归：分治（使用三数取中法优化）：

private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

private static void mid_three(int[] array, int i, int j) {
//        int mid = i + (j - i) / 2;
        int mid = (i + j) >> 1;
        //要得到左值为中间值
        //左值>右值 -> 左值 <= 右值
        if (array[i] > array[j]) {
            swap(array, i, j);
        }
        //左值<中值 ->左值 >= 中值
        if (array[i] < array[mid]) {
            swap(array, i, mid);
        }
        //中值<右值 -> 右值 >= 中值
        if (array[mid] < array[j]) {
            swap(array, mid, j);
        }
    }

    private static void quick(int[] array, int low, int high) {
        //跳出条件
        if (low >= high) {
            return;
        }

        //三数取中法进行优化，取中值放到开头
        mid_three(array, low, high);

        //每次递归找基准下标
//        int pivot = partition1(array, low, high);
        int pivot = partition2(array, low, high);
        //分而治之
        quick(array, low, pivot - 1);
        quick(array, pivot + 1, high);
    }

非递归：用栈实现

 

public static void quickSort(int[] array) {
        Stack stack = new Stack<>();
        int low = 0;
        int high = array.length - 1;
        int pivot = partition(array, low, high);
        if (pivot > low + 1) {
            stack.push(low);
            stack.push(pivot - 1);
        }

        if (pivot < high - 1) {
            stack.push(pivot + 1);
            stack.push(high);
        }

        while (!stack.empty()) {
            high = stack.pop();
            low = stack.pop();
            pivot = partition(array, low, high);
            if (pivot > low + 1) {
                stack.push(0);
                stack.push(pivot - 1);
            }
            if (pivot < high - 1) {
                stack.push(pivot + 1);
                stack.push(high);
            }
        }
    }

挖坑法整体实现：

private static int partition(int[] array, int start, int end) {
        //这里是给的随机start值作为开始，此处可用三数取中法优化
        int tmp = array[start];
        while (start < end) {
            //end处的值如果大于tmp，则end向前走
            while (start < end && array[end] >= tmp) {
                end--;
            }
            //start值为空，先将新end处值放到start在进行判断
            array[start] = array[end];
            //start处的值如果小于tmp，则start向后走
            while (start < end && array[start] <= tmp) {
                start++;
            }
            //end处值为空，将start处值放入end
            array[end] = array[start];
        }
        //循环跳出时,(array[start] == array[end])start处为空，将tmp中值赋给start
        array[start] = tmp;
        //返回pivot基准下标
        return start;
    }

private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

private static void mid_three(int[] array, int i, int j) {
        int mid = (i + j) >> 1;
        //要得到左值为中间值
        //左值>右值 -> 左值 <= 右值
        if (array[i] > array[j]) {
            swap(array, i, j);
        }
        //左值<中值 ->左值 >= 中值
        if (array[i] < array[mid]) {
            swap(array, i, mid);
        }
        //中值<右值 -> 右值 >= 中值
        if (array[mid] < array[j]) {
            swap(array, mid, j);
        }
    }

    private static void quick(int[] array, int low, int high) {
        //跳出条件
        if (low >= high) {
            return;
        }

        //三数取中法进行优化，取中值放到开头
        mid_three(array, low, high);

        //每次递归找基准下标
        int pivot = partition(array, low, high);
        //分而治之
        quick(array, low, pivot - 1);
        quick(array, pivot + 1, high);
    }

    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

优化总结：

1. 选择基准值很重要，通常使用几数取中法； 2. partition 过程中把和基准值相等的数也选择出来； 3. 待排序区间小于一个阈值时 ，使用直接插入排序。

---

7.归并排序 - mergeSort

* 时间复杂度:O(N*logN)
* 空间复杂度：O(N)
* 稳定性：稳定

算法思想：

        归并排序是建立在归并 *** 作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，直至有序。

图解算法：

代码实现：

• 递归实现

private static void merge(int[] array, int low, int mid, int high) {
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;
        int[] tmpArr = new int[high - low + 1];
        int k = 0;
        //逐层分开
        while (s1 <= e1 && s2 <= e2) {
            //不加等号就不稳定
            if (array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            } else {
                tmpArr[k++] = array[s2++];
            }
        }
        //一边为偶数一边为单数时，将多出的直接加到tmpArr中
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //写回到原来的数组
        for (int i = 0; i < k; i++) {
            array[i + low] = tmpArr[i];
        }
    }

    private static void mergeSortIn(int[] array, int low, int high) {
        //跳出条件
        if (low >= high) {
            return;
        }
        int mid = low + ((high - low) >> 1);
        mergeSortIn(array, low, mid);
        mergeSortIn(array, mid + 1, high);

        merge(array, low, mid, high);
    }

    public static void mergeSort(int[] array) {
        mergeSortIn(array, 0, array.length - 1);
    }

• 非递归实现

private static void merge(int[] array, int low, int mid, int high) {
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;
        int[] tmpArr = new int[high - low + 1];
        int k = 0;
        //逐层分开
        while (s1 <= e1 && s2 <= e2) {
            //不加等号就不稳定
            if (array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            } else {
                tmpArr[k++] = array[s2++];
            }
        }
        //一边为偶数一边为单数时，将多出的直接加到tmpArr中
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //写回到原来的数组
        for (int i = 0; i < k; i++) {
            array[i + low] = tmpArr[i];
        }
    }

    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i = i + gap * 2) {
                int low = i;
                int mid = low + gap - 1;
                int high = mid + gap;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                if (high >= array.length) {
                    high = array.length - 1;
                }

                merge(array, low, mid, high);
            }
            gap = gap * 2;
        }
    }