Quick Sort 与 Quick Selection 衍生

Neilyo 发布于2019-08-16 10:33 / 3199人阅读

摘要：理解最关键的是结束后各个指针的状态，以及下一步递归的起止点。上面的模板在结束时是的状态，但是不确定中间还有没有一个数，如下图今天在图书馆写码没有带板子，就先照个图了注意里是里一定要注意这个灵活多变照这个思路的相关题

首先是记录一个quick sort的模板（思想是遇到不符合顺序的就交换，很好理解）：
public void quickSort(int[] nums, int start, int end){

if(start < end){
    int i = start;
    int j = end;
    int pivot = nums[(i + j) / 2];
    
    while(i <= j){
        while(i <= j && nums[i] < pivot){
            i++;
        }
        while(i <= j && nums[j] > pivot){
            j--;
        }
        if(i <= j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
    
    quickSort(nums, start, j);
    quickSort(nums, i, end);
}

}
基于快速排序里这个pivot的思想，有一个衍生quick Select, 用来解决一些类似于求中位数啦，kth数字啦之类（第几个第几个可以联想到pivot）的问题，时间复杂度也比快速排序有所降低。理解quick sort, quick select最关键的是结束partition后各个指针的状态，以及下一步递归的起止点。上面的模板在结束时是i

注意quickSort里是（start < end）, quickSelect里一定要注意这个灵活多变
照这个思路的相关题：
[LeetCode 215] Kth Largest Element in an Array

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70020.html

Sorting

摘要：是稳定的排序，但是它需要额外的空间，时间复杂度为程序这个同上也是两个步骤，。最坏情况的时间复杂度为但是在实际情况中，通常是排序的最佳选择。就是有序的完全二叉树，所有我们要先根据已有的数组来建立一个。最后由后往前形成一个有序数组。 Bubble Sort就不说了，下面简单总结一个Selection Sort, Insertion Sort, Merge Sort和Quick Sort: ...

calx 2019-08-14 14:09 评论0 收藏0
排序算法sort.js(看源码，把它背下来吧)

摘要：对于实在不能理解的同学，听我的吧这是死东西，那你就背下来背下来背下来。就说三遍，背完之后，还不能理解，那我也不能理解了。 sort.js JavaScript to achieve the ten common sorting algorithm library 这个小库是对常见的十大排序算法的一个基本汇总，建议读者直接看源码|看源码|看源码。别怕，我注释十分清晰，你要是还看不懂，给...

史占广 2019-08-20 14:18 评论0 收藏0
[LintCode] Sort Integers II [Merge-sort, Quick-sor

Problem Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm. Example Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5]. Note 考察对Heap Sort, Q...

YorkChen 2019-08-14 14:23 评论0 收藏0
几种排序算法及 Python 实现

摘要：因为直接插入排序在元素基本有序的情况下接近最好情况，效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。插入排序 def insert_sort(list): n = len(list) for i in range(1, n): key = list[i] for j in range(i-1, -1, -1): ...

cod7ce 2019-07-31 11:05 评论0 收藏0
2017年最受欢迎的UI框架

摘要：年马上到尾声了，在这里总结一下基于和这四大框架衍生的，经受过时间检验深受广大开发者欢迎的框架。可以说是年最火的引擎类前端框架，以其美观的设计和高质量的组件很快俘获了一大批的芳心。　　前端领域最近几年发展的特别迅速，可以说是百家争鸣。在底层的前端框架领域中，最早是jquery称霸互联网，近两年MVVM类型的框架慢慢成为主流，Vue、React和Angular三大框架并驾齐驱。可以说，目...

ernest.wang 2019-07-01 12:24 评论0 收藏0