搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 数据结构与算法 > 常用排序算法专题—快速排序

常用排序算法专题—快速排序

数据结构与算法 2019-11-08

点击右侧关注,了解黑客的世界!


作者丨就是彬彬呀
https://www.jianshu.com/p/17af5e10a661


快速排序


快速排序(Quicksort)是对冒泡排序的一种改进;它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


  • 基本思路


首先先举一个直观的例子,假设有一串int型的待排序数组为:49,38,65,76,97,13,27,49。假设第一个为基准数,即49。目标:本次排序后的数组,49的左边的数必定都小于49;49右边的数必定都大于或等于49。


{27,38,13},49,{76,97,65,49}

此时把目标放在子数组27,38,13上,假设第一个为基准数,即27。目标:本次排序后的(子)数组,27的左边的数必定都小于27;27右边的数必定都大于或等于27。

{13},27,{38},49,{76,97,65,49}

再把目标放在子数组76,97,65,49上,假设第一个为基准数,即76。目标:本次排序后的(子)数组,76的左边的数必定都小于76;76右边的数必定都大于或等于76。

{13},27,{38},49,{49,65},76,{97}


注:对子数组49,65继续进行同样的操作,排序完成。


由此可见,快速排序的原理在于:对于数组给定基准数(假设始终为第一个),保证基准数右边的数都比基准数大(或等于),左边的数都比基准数小。调节基准数至最佳位置,然后对基准数左右两边的子数组再继续进行相同操作,一般采用递归的方法,直到完成排序。


  • 如何将基准数调节至最佳位置?
      我们假设有一个含有7个元素的int型的一维数组变量,他们分别是5,2,4,1,6,7,3,显然基准数为5,我们要将比5大的放在右边,比5小的放在左边。我们准备两个哨兵指针,分别指向数组的头和尾:



右边的指针先向左运动,只要遇到比基准数小的数就停止运动,即3,将右指针的值赋予左指针:

常用排序算法专题—快速排序


左边的指针先向右运动,只要遇到比基准数大的数就停止运动,即6,将左指针的值赋予右指针:


常用排序算法专题—快速排序


重复以上操作,直到左右指针碰面停止循环,最后将基准数赋予左指针。

常用排序算法专题—快速排序


注:此时基准数5调节到了最佳位置,继续对5的左右子序列{3,2,4,1}和{7,6}分别再次以相同方式排序(递归)直至完成排序。


JAVA 代码:


package DataStructure;

public class QuickSort {
    private static int getIndex(int[] arr, int low, int high{
        int index = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= index)
                high--;
            arr[low] = arr[high];
            while (low < high && arr[low] <= index)
                low++;
            arr[high] = arr[low];
        }
        arr[low] = index;


        return low;

    }

    public static void sort(int[] arr, int low, int high{
        if (low < high) {
            int index = getIndex(arr, low, high);
            sort(arr, 0, index - 1);
            sort(arr, index + 1, high);
        }
    }

    public static void main(String[] args{
        int[] arr = { 6782431};
        sort(arr, 0, arr.length - 1);
        for (int n : arr)
            System.out.print(n + " ");
    }

}


  • 时间复杂度


在最坏的情况下,可能是相邻的两个数进行交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(n²),最佳时间复杂度为O(nlogn),且它的平均时间复杂度为O(nlogn)。


 推荐↓↓↓ 

👉】都在这里!

涵盖:程序员大咖、源码共读、程序员共读、数据结构与算法、黑客技术和网络安全、大数据科技、编程前端、Java、Python、Web编程开发、Android、iOS开发、Linux、数据库研发、幽默程序员等。

万水千山总是情,点个 “ 在看” 行不行

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《常用排序算法专题—快速排序》的版权归原作者「数据结构与算法」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注数据结构与算法微信公众号

数据结构与算法微信公众号:gh_006c831961f5

数据结构与算法

手机扫描上方二维码即可关注数据结构与算法微信公众号

数据结构与算法最新文章

精品公众号随机推荐