彻底理解快速排序及其优化和应用、随机三路快排、链表快速排序、寻找第K大元素、颜色分类、奇偶排序

[视频作者] 内卷心菜2023

[视频时长] 23:19

[视频类型] 职业职场

排序算法有很多，最好时间复杂度为nlogn的排序算法有快速排序、堆排序、归并排序等等，而快速排序在这些算法中时间复杂度的常数项又是最低的，所以快速排序是相对来说最快，但是快速排序有几个缺点：快速排序是非稳定排序; 快速排序在序列基本有序的情况下，时间复杂度为n^2。第一个缺点一般我们算法很少用到，只是在工程中需要做到排序的稳定性，或者自定义比较器来排序，所以我们只需要关注第二点，那么就要采用随机策略选出枢纽元素，并且在一次排序的过程中固定所有相等的值在其合适的位置！