精华内容
下载资源
问答
  • 快速排序 图解

    2021-02-13 16:39:43
    在待排序的n个元素中取一个元素K(通常取第一个元素),以元素K为分割标准,把所有小于K元素的元素都一道移到K前面,把所有打羽大于K元素的元素都移到K后面。...快速排序实际上是冒泡排序的优化。 ...

    在待排序的n个元素中取一个元素K(通常取第一个元素),以元素K为分割标准,把所有小于K元素的元素都一道移到K前面,把所有打羽大于K元素的元素都移到K后面。这样,是一趟排序。对K前后两个子表分别重复上述过程,直至子表长度为1。在这里插入图片描述
    图源网络
    快速排序实际上是冒泡排序的优化。

    展开全文
  • 快速排序图解

    2018-10-15 10:40:51
    http://www.cnblogs.com/clc2008/p/6853060.html
    展开全文
  • 快速排序,人称最快的排序(其实我不太赞同,只能说它整体上效率比较高,有些排序算法在特定的数据序列中远比快速排序效率高)。掌握快速排序,需要对递归有深入的了解,如果只是了解递归的用法「不知道为什么这样写」...

    快速排序,人称最快的排序(其实我不太赞同,只能说它整体上效率比较高,有些排序算法在特定的数据序列中远比快速排序效率高)。掌握快速排序,需要对递归有深入的了解,如果只是了解递归的用法「不知道为什么这样写」,却不知道递归原理和执行顺序,建议深入学习下递归思想(PS:公众号列表中已经躺了一篇关于递归的文章,只是没太想好如何能够通俗易懂把递归讲明白,后面我画一些图来聊一聊递归)。

    快速排序的核心思想是对待排序序列通过一个「支点」(支点就是序列中的一个元素,别把它想的太高大上)进行拆分,使得左边的数据小于支点,右边的数据大于支点。然后把左边和右边再做一次递归,直到递归结束。支点的选择也是一门大学问,我们以 (左边index + 右边index)/ 2 来选择支点。一图胜千言,看图吧。

    快速排序

    以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例,选择一个支点, index=  (L+R)/2 = (0+7)/2=3, 支点的值 pivot = arr[index] = arr[3] = 6,接下来需要把 arr 中小于 6 的移到左边,大于 6 的移到右边。快速排序使用一个高效的方法做数据拆分。用一个指向左边的游标 i,和指向右边的游标 j,逐渐移动这两个游标,直到找到 arr[i] > 6 和 arr[j] =j,停止移动。图中的 L,R 是指快速排序开始时序列的起始和结束索引,在一趟快速排序中,它们的值不会发生改变,直到下一趟排序时才会改变。文字描述的有点长,我怕你看不懂图就啰嗦了一下

    e5900782474036ebc8c34a910b52cd2f.png

    一趟快速排序完成后,分别对小于6和大于等于6的部分进行快速排序,递归就好了。对 [ 5, 1, 4, 3, 2 ] 进行一趟快速排序。

    a7cb641d40815481f734207b2297ca9f.png

    1eb9c34341e70a09905bc9a9cf6bed8b.png

    810d14d7bc1ffa2dcb236b4d53b0383c.png

    图中说明了快速排序的核心思想,每次递归过程都一样,掌握一趟快速排序思想和递归思想,即可掌握快速排序。

    代码

    /** 快速排序 @param unSortArray 待排序序列 @param lindex 待排序序列左边的index @param rIndex 待排序序列右边的index @return 排序结果 */+ (NSArray *)quickSort:(NSMutableArray *)unSortArray leftIndex:(NSInteger)lindex rightIndex:(NSInteger)rIndex {    NSInteger i = lindex; NSInteger j = rIndex;    // 取中间的值作为一个支点    NSNumber *pivot = unSortArray[(lindex + rIndex) / 2];    while (i <= j) {        // 向左移动,直到找打大于支点的元素        while ([unSortArray[i] integerValue] < [pivot integerValue]) {            i++;        }        // 向右移动,直到找到小于支点的元素        while ([unSortArray[j] integerValue] > [pivot integerValue]) {            j--;        }        // 交换两个元素,让左边的大于支点,右边的小于支点        if (i <= j) {            // 如果 i== j,交换个啥?            if (i != j) {                NSNumber *temp = unSortArray[i];                unSortArray[i] = unSortArray[j];                unSortArray[j] = temp; }            i++;            j--;        }    }    // 递归左边,进行快速排序    if (lindex < j) {        [self quickSort:unSortArray leftIndex:lindex rightIndex:j];    }    // 递归右边,进行快速排序    if (i < rIndex) {        [self quickSort:unSortArray leftIndex:i rightIndex:rIndex];    }    return [unSortArray copy];}

    特点

    稳定性在元素分组的时候,相同元素相对位置可能会发生变化,故不稳定。

    空间复杂度:不同实现空间复杂度不太一样;

    时间复杂度:它与选取的支点值有关系,如果支点值为最大或最小,导致只有一边进行快速排序,时间复杂度为 O(n*n) , 如果选择中间的值为 O(nlogn);

    感想

    快速排序理解起来确实比其它排序抽象一点,它的关键点是选择支点值,选最大或者最小,导致快速排序一边倒,性能会大打折扣。回顾一下前面提到的 3 种排序。冒泡排序,需要每次找到最大元素放到最后;插入排序,需要把待排序序列分组,把未排序序列插入到已排序序列;希尔排序,分多组让待排序序列逐渐变得有序,从而达到优化插入排序的目的。快速排序也是把待排序序列分组,不过它需要找到一个合适的支点。

    推荐阅读:

    图解排序 3/10 - 希尔排序

    图解排序 2/10 - 插入排序

    图解排序 1/10 - 冒泡排序

    微博@Lefe_x

    ceb49b7d767dea1b6f3c72f1fd28fb62.png

    展开全文
  • (给算法爱好者加星标,修炼编程内功)作者:小齐本齐 (本文来自作者投稿)快速排序算法首先选一个基准 pivot,然后过一遍数组,把小于 pivot 的都挪到 pivot 的左边,把大于 pivot 的都挪到 pivot 的右边。这样一来,...

    (给算法爱好者加星标,修炼编程内功)

    作者: 小齐本齐 (本文来自作者投稿)

    快速排序
    算法

    首先选一个基准 pivot,然后过一遍数组,

    • 把小于 pivot 的都挪到 pivot 的左边,
    • 把大于 pivot 的都挪到 pivot 的右边。

    这样一来,这个 pivot 的位置就确定了,也就是排好了 1 个元素。

    然后对 pivot 左边 ? 的数排序,
    对 pivot 右边 ? 的数排序,
    就完成了。

    那怎么排左边和右边?

    答:同样的方法。

    所以快排也是用的分治法的思想。

    「分」

    选择一个 pivot,就把问题分成了

    • pivot 左边
    • pivot 右边

    这两个问题。

    「治」

    就是最开始描述的方法,直到每个区间内没有元素或者只剩一个元素就可以返回了。

    「合」

    放在一起自然就是。

    但是如何选择这个 pivot?

    取中间的?

    取第一个?

    取最后一个?

    举个例子:{5, 2, 1, 0, 3}.

    比如选最后一个,就是 3.

    然后我们就需要把除了 3 之外的数分成「比 3 大」和「比 3 小」的两部分,这个过程叫做 partition(划分)

    这里我们仍然使用「挡板法」的思想,不用真的弄两个数组来存这两部分,而是用两个挡板,把区间划分好了。

    我们用「两个指针」(就是挡板)把数组分成「三个区间」,那么

    • 左边的区间用来放小于 pivot 的元素;
    • 右边的区间用来放大于 pivot 的元素;
    • 中间是未排序区间。
    cd132bc80ab53dc6bcf3bcd2d39019d4.png

    那么初始化时,我们要保证「未排序区间」能够包含除了 3 之外的所有元素,所以

    • 未排序区间 = [i, j]

    这样左边和右边的区间就成了:

    • [0, i):放比 3 小的数;
    • (j, array.length -2]:放比 3 大的数

    注意 ⚠️ i, j 是不包含在左右区间里的呢。

    那我们的目的是 check 未排序区间里的每一个数,然后把它归到正确的区间里,以此来缩小未排序区间,直到没有未排序的元素。

    从左到右来 check:

    Step1.

    5 > 3, 所以 5 要放在右区间里,所以 5 和 j 指向的 0 交换一下:

    25f649a7215d9e7badc5bf3c14ced40f.png

    这样 5 就排好了,指针 j --,这样我们的未排序区间就少了一个数;

    Step2.

    0 < 3,所以就应该在左边的区间,直接 i++;

    fba0759f64ab83e02c1e8cf110b740b9.png

    Step3.

    2 < 3,同理,i++;

    829e02ece0f39c0de6be0582f815cf9b.png

    Step4.

    1 < 3,同理,i++;

    3b03cd20d7793c3d7942e144dc3a1cc1.png

    所以当两个指针错位的时候,我们结束循环。

    但是还差了一步,3 并不在正确的位置上呀。所以还要把它插入到两个区间中间,也就是和指针 i 交换一下。

    06c2da278ec5353e852679cbf61ec227.png
    cea407349765b581fc5da498a8f44563.png

    声明:这里并不鼓励大家把 pivot 放最左边。

    基本所有的书上都是放右边,既然放左右都是一样的,我们就按照大家默认的、达成共识的来,没必要去“标新立异”。

    就比如围棋的四个星位,但是讲究棋道的就是先落自己这边的星位,而不是伸着胳膊去够对手那边的。

    那当我们把 pivot 换回到正确的位置上来之后,整个 partition 就结束了。

    之后就用递归的写法,对左右两边排序就好了。

    最后还有两个问题想和大家讨论一下:

    1. 回到我们最初选择 pivot的问题,每次都取最后一个,这样做好不好?

    答:并不好。

    因为我们是想把数组分割的更均匀均匀的时间复杂度更低;但是如果这是一个有序的数组,那么总是取最后一个是最不均匀的取法。

    所以应该随机取 pivot,这样就避免了因为数组本身的特点总是取到最值的情况。

    1. pivot 放在哪

    随机选取之后,我们还是要把这个 pivot 放到整个数组的最右边,这样我们的未排序区间才是连续的,否则每次走到 pivot 这里还要想着跳过它,心好累哦。

    class Solution {
      public void quickSort(int[] array) {
        if (array == null || array.length <= 1) {
          return;
        }
        quickSort(array, 0, array.length - 1);
      }
      private void quickSort(int[] array, int left, int right) {
        // base case
        if (left >= right) {
          return;
        }

        // partition
        Random random = new Random(); // java.util 中的随机数生成器
        int pivotIndex = left + random.nextInt(right - left + 1);
        swap(array, pivotIndex, right);

        int i = left;
        int j = right-1;
        while (i <= j) {
          if (array[i] <= array[right]) {
            i++;
          } else {
            swap(array, i, j);
            j--;
          }
        }
        swap(array, i, right);

        //「分」
        quickSort(array, left, i-1);
        quickSort(array, i+1, right);
      }
      private void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
      }
    }

    这里的时空复杂度和分的是否均匀有很大关系,所以我们分情况来说:

    1. 均分

    时间复杂度

    如果每次都能差不多均匀分,那么

    • 每次循环的耗时主要就在这个 while 循环里,也就是 O(right - left);
    • 均分的话那就是 logn 层;
    • 所以总的时间是 O(nlogn).
    33151dedf8c5d6eeb315c5d1968e27f5.png

    空间复杂度

    • 递归树的高度是 logn,
    • 每层的空间复杂度是 O(1),
    • 所以总共的空间复杂度是 O(logn).

    2. 最不均匀

    如果每次都能取到最大/最小值,那么递归树就变成了这个样子:

    1690e43dc92ffa825a7cef6bc0f42b96.png

    时间复杂度

    如上图所示:O(n^2)

    空间复杂度

    这棵递归树的高度就变成了 O(n).

    3. 总结

    实际呢,大多数情况都会接近于均匀的情况,所以均匀的情况是一个 average case.

    为什么看起来最好的情况实际上是一个平均的情况呢?

    因为即使如果没有取到最中间的那个点,比如分成了 10% 和 90% 两边的数,那其实每层的时间还是 O(n),只不过层数变成了以 9 为底的 log,那总的时间还是 O(nlogn).

    所以快排的平均时间复杂度是 O(nlogn)。

    稳定性

    那你应该能看出来了,在 swap 的时候,已经破坏了元素之间的相对顺序,所以快排并不具有稳定性。

    这也回答了我们开头提出的问题,就是

    • 为什么对于 primitive type 使用快排

      • 因为它速度最快;
    • 为什么对于 object 使用归并

      • 因为它具有稳定性且快。

    以上就是快排的所有内容了,也是很常考的内容哦!

    - EOF -

    推荐阅读  点击标题可跳转

    1、深入理解快速排序和 STL 的 sort 算法

    2、快速排序你真的会了吗?

    3、为什么说 O(n) 复杂度的基数排序没有快速排序快?

    觉得本文有帮助?请分享给更多人

    关注「算法爱好者」加星标,修炼编程内功

    9c150e30b5e3e1014582e404d84bc8cc.png

    好文章,我在看❤️

    展开全文
  • 算法05:Golang快速排序Quick Sort1.什么是快速排序(Quick Sort)快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较.在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见....
  • 快速排序是一种交换排序,它由C. A. R. Hoare在1962年提出。快速排序(quick sort)的采用了分而治之(divide and conquer)的策略:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后...
  • Python一一行行代代码码实实现现快快速速排排序序的的方方法法 排序算法是在高考或中考中出现频率最多的点所以大家要掌握今天小编给大家带来了通过Python一 代码实 现快速排序的方法感兴趣的朋友跟随小编一起看看吧 ...
  • Java实现快速排序图解

    2020-06-04 16:55:56
    快速排序快速排序法介绍图解代码理解 快速排序法介绍 快速排序(QuickSort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将 要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据...
  • 快速排序图解(分治)--算法学习

    千次阅读 2020-03-23 13:15:13
    思路 数组排序任务可以如下完成: 1)设k=a[0], 将k挪到适当位置,使得...2) 把k左边的部分快速排序 3) 把k右边的部分快速排序 图解 代码: #include <iostream> using namespace std; void swap(int &...
  • 本文转载于 SegmentFault 社区作者:七友一描述简介快速排序由 C. A. R. Hoare 在 1960 年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要...
  • 1. 快速排序分治思想不稳定时间复杂度:最差O(n^2),平均O(nlogn)空间复杂度:O(n+1)每次排序设置一个基准点,小于等于基准点的数放到基准点左边,大于等于基准点的数放到基准点右边。2. 堆排序完全二叉树不稳定时间...
  • 那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待...
  • 前言由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的...快速排序快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比...
  • 快速排序快速排序简称快排,是对气泡排序的一种改进,是一种递归算法,通过一趟排序将待排记录分为独立两部分,在某一枢轴量左侧,均是小于它的值,在其右侧,均是大于它的值,对序列不断分割,最后会形成有序序列。...
  • 下面先看一下快速排序的动态演示(一个超级好用的网站,各种算法相关的动态图都能演示) https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 代码实现 #include<bits/stdc++.h> using ...
  • 快速排序基本思想:通过一趟排序讲待排的记录分割成独立的两部分,其中一部分记录的关键字比另一部分的关键字小,然后再分别这两部分记录继续进行排序以达到整个序列有序。 快速排序,在所有同数量级的排序方法中...
  • 今天就来为大家介绍一下java中插入排序和分治、快速排序的主要内容,并且通过详细的图片为大家解析。第一个、插入排序:首先说一下一次插入排序的操作过程:1.将待插元素,依次与已排序好的子数列元素从后到前进行...
  • 答案是多种多样的,比如用冒泡排序、选择排序、堆排序、归并排序、快速排序等等,这些排序方法都可以实现对整数排序,而这篇文章要讲的就是选择排序本文将从以下几个问题对选择排序进行分析和讲解:1 选择排序的...
  • 答案是多种多样的,比如用冒泡排序、选择排序、堆排序、归并排序、插入排序、快速排序等等,这些排序方法都可以实现对整数排序,而这篇文章要讲的就是插入排序(直接插入如排序)。本文将从以下几...
  • 快速排序图解/动画及C语言实现

    千次阅读 2019-01-21 12:51:09
    用C语言实现快速排序
  • 快速排序示意图 快速排序思路分析: 快速排序完整代码: import java.util.Arrays; public class quickSort { public static void main(String[] args) { int[] arr = { 5, 1, 4, 7, 82, 6, 15, 12, 27, 14 }; ...
  • 接下来主要介绍六种排序算法:冒泡排序,选择排序,插入排序,堆排序,归并排序和快速排序,本次排序算法均以升序为例。 话不多说,整体代码先瞅一下,然后今天主要简单配合图解看看冒泡/选择和插入排序算法。#...
  • 每日编程中遇到任何疑问、意见、建议请公众号留言或直接撩Q474356284(备注每日编程)今日问题:示例 1:输入:4->2->...5解决方法:本文将对快速排序代码进行图解分析,为后面的每日一题链表排...
  • 代码实现 ... * 快速排序 **/ public class QuickSort { public static void main(String[] args) { int[] array = {12, 20, 5, 16, 15, 1, 30, 45}; int[] sort = quickSort(array, 0, array.le.
  • 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为...
  • 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个...
  • 因为是史上最详细快速排序,所以我写的非常细~~基本每一句代码都解释+图解到位了,需要耐心浏览, 先上代码,再对代码进行图解,大家也可以先把代码跑一遍,有个底… //快速排序 void my_sort(int arr[],int low,int...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,118
精华内容 447
关键字:

快速排序图解