写点什么

七日算法先导(三)—— 快速排序,插入排序

作者:秋名山码民
  • 2022 年 8 月 04 日
  • 本文字数:1482 字

    阅读完需:约 5 分钟

作业解答

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

快速排序


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


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


  1. 算法步骤

  2. 从数列中挑出一个元素,称为 "基准"(pivot);

  3. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

  4. 递归地(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
用户头像

卷不死,就往…… 2021.10.19 加入

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

评论

发布
暂无评论
七日算法先导(三)—— 快速排序,插入排序_8月月更_秋名山码民_InfoQ写作社区