您好,欢迎来到网暖!

当前位置:网暖 » 站长资讯 » 建站基础 » 网络技术 » 文章详细 订阅RssFeed

排序之快排

来源:网络整理 浏览:254次 时间:2020-08-09
  • 排序是将一串数据按照其某个或者某些关键字的大小进行递增或递减排列的操作我,通常指的排序是升序,排序方式是原地排序
  • 下面介绍下快速排序,简称快排
快排
  • 原理:
    • 从待排序区间选择一个数,作为基准值(pivot)
    • Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基准值大的(可以包含相等的)放到基准值的右边
    • 采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度等于1,代表已经有序,或者小区间的长度等于0,代表没有数据。
  • 快排是一个不稳定的排序
实现方式
  1. 快排的逻辑其实很简单,

    • 递归分治
    • 代码如下:

      public static void quickSort(int[] array) {        //待排序区间为[0, array.length - 1]        quickSortIternal(array, 0, array.length - 1);}private static void quickSortIternal(int[] array, int left, int right) {        if(left >= right)                return;        //这里的就选择最左边的元素作为基准值来操作        //index表示基准值停留的下标        int index = partition(array, left, right);        quickSortIternal(array, left, index - 1);        quickSortIternal(array, index + 1, right);}
    • 非递归分治
    • 通过使用栈实现,将数组的左右下标放入栈中
    • 每次取出判断left和right的关系,如果left >= right 表示该小区间排序完毕
    • 存入每个区间的左右两下标,依次循环,当栈为空时,表示排序结束
    • 代码如下:

      public static void quickSort2(int[] array) {            Stack<Integer> stack = new Stack<>();            stack.push(array.length - 1);            stack.push(0);            while(!stack.isEmpty()) {                    int left = stack.pop();                    int right = stack.pop();                    if(left >= right) {                            continue;                    }                    int index = partition(array, left, right);                    stack.push(right);                    stack.push(index + 1);                    stack.push(index - 1);                    stack.push(left);            }    }
  2. 重点是partition的实现

    • 实现方法一: Hoare法
    • 使用双引用的的方式,一个指向区间的最左边,一个指向区间的最右边,两个引用向中间遍历的靠拢
    • 如果左引用指向的值小于等于基准值就移动
    • 如果右引用指向的值大于等于基准值就移动
    • 当左引用遇到大于基准值的数据且右引用遇到小于基准值的数据时,交换这两个引用处的数据
    • 当两个引用相遇时说明本次partition结束,返回基准值的下标
    • 代码如下:

      public int partition(int[] array, int left, int right) {            int pivot = array[left];            int l = left;            int r = right;            while(l < r) {                    while(l < r && array[r] >= pivot) {                            r--;                    }                    while(l < r && array[l] <= pivot) {                            l++;                    }                    swap(array, l, r);            }            swap(array, left, l);            return l;    }    private static void swap(int[] array, int i, int j) {            int tmp = array[i];            array[i] = array[j];            array[j] = tmp;    }
    • 实现方法二:填坑法
    • 同样需要双引用,指定一个变量保存基准值,假象基准值的位置是一个“坑”
    • 右引用遇到大于等于基准值的数值就向左移动,直到遇到第一个小于基准值的数值,将该数值填到“坑”中,此处的位置是一个新的“坑”
    • 开始移动左引用,只有遇到一个大于基准值的数值时,填到“坑”中
    • 直到左引用和右引用相遇时说明只剩最后一个坑了,将基准值填到“坑”中,返回基准值的下标,本次partition结束
    • 代码如下:

      public int partition(int[] array, int left, int right) {    int pivot = array[left];    int l = left;    int r = right;    while(l < r) {            while(l < r && array[r] >= pivot) {                    r--;            }            array[l] = array[r];            while(l < r && array[l] <= pivot) {                    l++;            }            array[r] = array[l];    }    array[l] = pivot;    return l;}
    • 实现方法三:前后遍历法
    • 同样是使用双引用slow和fast,起初同时指向基准值的后一个元素left + 1
    • 引用fast向后遍历,如果遍历到的数值大于基准值就向后移动
    • 遇到小于基准值的数值时,交换slow引用和fast引用指向的值,slow向后移动一位
    • 始终保证slow之前的值都是小于基准值的数值,slow和fast之间的是大于等于基准值的数值,当fast移动到区间最右端right时,遍历结束
    • 此时show - 1处的数值为最遍历结束后最后一个小于基准值的数值
    • 交换left和slow - 1两位置处的数值,slow - 1表示下标即是基准值的下标,返回slow - 1
    • 代码如下:

      private int partition(int[] array, int left, int right) {            int pivot = array[left];            int slow = left + 1;            int fast = left + 1;            while(fast <= right) {                    if(array[fast] < pivot) {                            swap(array, slow, fast);                            slow++;                    }                    fast++;            }            swap(array, left, slow - 1);            return slow - 1;    }
  3. 基准值的选择
    • 两边取其一(左或者右)
    • 随机选择
    • 几数取中(例三数取中:array[left], array[mid], array[right] 大小是中间的为基准值 )
性能分析
  • 时间复杂度:
    • 最好的情况:O(N*logN)
    • 平均情况:O(N*logN)
    • 最坏的情况:O(N^2)
  • 空间复杂度:O(1)
    • 最好的情况:O(logN)
    • 平均情况:O(logN)
    • 最坏的情况:O(N)
  • 稳定性:不稳定

推荐站点

  • 腾讯腾讯

    腾讯网(www.QQ.com)是中国浏览量最大的中文门户网站,是腾讯公司推出的集新闻信息、互动社区、娱乐产品和基础服务为一体的大型综合门户网站。腾讯网服务于全球华人用户,致力成为最具传播力和互动性,权威、主流、时尚的互联网媒体平台。通过强大的实时新闻和全面深入的信息资讯服务,为中国数以亿计的互联网用户提供富有创意的网上新生活。

    www.qq.com
  • 搜狐搜狐

    搜狐网是全球最大的中文门户网站,为用户提供24小时不间断的最新资讯,及搜索、邮件等网络服务。内容包括全球热点事件、突发新闻、时事评论、热播影视剧、体育赛事、行业动态、生活服务信息,以及论坛、博客、微博、我的搜狐等互动空间。

    www.sohu.com
  • 网易网易

    网易是中国领先的互联网技术公司,为用户提供免费邮箱、游戏、搜索引擎服务,开设新闻、娱乐、体育等30多个内容频道,及博客、视频、论坛等互动交流,网聚人的力量。

    www.163.com
  • 新浪新浪

    新浪网为全球用户24小时提供全面及时的中文资讯,内容覆盖国内外突发新闻事件、体坛赛事、娱乐时尚、产业资讯、实用信息等,设有新闻、体育、娱乐、财经、科技、房产、汽车等30多个内容频道,同时开设博客、视频、论坛等自由互动交流空间。

    www.sina.com.cn
  • 百度一下百度一下

    百度一下,你就知道

    www.baidu.com