七日算法先导（三）—— 快速排序，插入排序

2022 年 8 月 04 日
本文字数：1482 字
阅读完需：约 5 分钟

作业解答

昨天的作业都比较简单，力扣的题解也解释比较清楚，我就不在啰嗦了，今天我们来看快速排序和插入排序，其中快排，更是在面试中频频出现，整体难度也更上一层楼

快速排序

《信息学奥赛一本通》中讲到：快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

具体时间复杂度分析：快速排序时间复杂度分析

算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

public class QuickSort implements IArraySort {
    @Override    public int[] sort(int[] sourceArray) throws Exception {        // 对 arr 进行拷贝，不改变参数内容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return quickSort(arr, 0, arr.length - 1);    }
    private int[] quickSort(int[] arr, int left, int right) {        if (left < right) {            int partitionIndex = partition(arr, left, right);            quickSort(arr, left, partitionIndex - 1);            quickSort(arr, partitionIndex + 1, right);        }        return arr;    }
    private int partition(int[] arr, int left, int right) {        // 设定基准值（pivot）        int pivot = left;        int index = pivot + 1;        for (int i = index; i <= right; i++) {            if (arr[i] < arr[pivot]) {                swap(arr, i, index);                index++;            }        }        swap(arr, pivot, index - 1);        return index - 1;    }
    private void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }
}

复制代码

插入排序

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

像斗地主插入一样，简单的来说就是将一个记录插入到已经排好的有序表中，从而得到一个新的，记录数据+1 的有序表

void insertionSort(int *arr, int len) {    if (len<2) {        return ;    }        for (int i=1; i<len; i++) {        int insertValue = arr[i];//暂存需要插入元素        int j = i-1;         //从右向左比较元素        for (; j>=0 && insertValue<array[j]; j--) {            arr[j+1] = arr[j];        }         arr[j+1] = insertValue;    }}

复制代码

插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

动图：

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/daadaf9e57f81776db6f1db7d】。

秋名山码民

关注

卷不死，就往…… 2021.10.19 加入

2019NOIP退役成员，华为云享专家，阿里云专家博主，csdn博主，努力进行算法分享，有问题欢迎私聊

发布

暂无评论

创作场景

七日算法先导（三）—— 快速排序，插入排序

作业解答

快速排序

插入排序

秋名山码民

评论