文档章节

快速排序算法及其变体快速选择算法详解

爱宝贝丶
 爱宝贝丶
发布于 2016/08/27 22:13
字数 2555
阅读 455
收藏 3

       快速排序算法在实际实际生产应用中使用非常多,比如java类库中Arrays类中的sort()方法,以及Collections类中的sort()方法,其一个是对数组进行排序,一个是对集合进行排序。不过这里需要说明的是,在Arrays.sort()和Collections.sort()方法底层实现中不仅采用了快速排序算法,也采用了归并排序算法,因为快速排序算法相对于归并排序算法而言,其对比较(compareTo())方法的调用的开销比归并排序要大,而对于对象类型,其主要是依赖于compareTo()方法进行比较,而对于基本数据类型,其主要是依赖于基本数据类型的数值比较,因而快速排序算法适用于基本数据类型的排序,而归并排序算法则适用于对象类型的排序。java类库中的Arrays.sort()和Collections.sort()利用多态对传入数组或集合的具体类型来判断是使用快速排序算法还是快速选择算法。

       快速排序算法的核心思想其实是一个通过递归不断选取枢纽元的过程,每次选取枢纽元之后,在枢纽元左边的元素都将比枢纽元要小,在枢纽元右边的元素都将比枢纽元要大,比如下图所示的一个集合:

我们选取48作为枢纽元,那么经过一次递归后该集合将被48分割,分割后的集合如下图所示:

从图中可以形象的看出,分割一次之后枢纽元左边的部分的值都比枢纽元要小,枢纽元右边的值都比枢纽元要大。自此,我们可以将枢纽元左边的元素和右边的元素分别看作一个集合,然后对两个集合分别递归的选取枢纽元并进行分割,最终我们的原数组将得到排序。

       根据上边的分析,快速排序算法的核心思想是不断地选取枢纽元,并对原集合进行分割,那么这里如何选取枢纽元,并且每次递归时如何通过枢纽元进行分割呢?首先我们来解决第一个问题,假设原集合元素的下表是从left到right,我们如果选取下标为left + 1的元素为枢纽元,并且要求对集合进行升序排序,那么当我们的原集合本来就是一个降序排序的集合的时候,集合中最小的元素将需要通过不断的换位操作从最右边移动到最左边,由于要进行N - 2次,因而时间复杂度将达到O(N^2);同理,如果枢纽元靠近下标right,其也不是一个好的选择;一般的,我们都是将枢纽元选择为集合的中间元素。对于第二个问题,由于我们只要求枢纽元左边的元素比枢纽元要小,枢纽元右边的元素比枢纽元要大即可,那么分割思路可以分为三步(假设集合为arr,下标从left到right):①将集合最左边的元素、中间的元素和最右边的元素进行对比,然后将其中最小的值放在最左边,最大的值放在中间,中等值得元素放在最右边(也即中间元pivot放在最右边);②声明变量i、j,分别指向最左边的元素的右边一位和最右边的元素的左边一位,将arr[i]和pivot进行比较,如果arr[i]小于pivot,那么就让i自增,同理,将arr[j]与pivot进行比较,如果arr[j]大于pivot时让j自减。此时将出现两种情况:a.i<j,此时arr[i] < pivot,arr[j] > pivot,由于i和j中间部分的元素还未与中间元进行比较,处理方法是将i和j所指向的元素值进行互换,继续第二步;b.i > j,此时arr[i] < pivot,arr[j] > pivot,但是i和j中间部分的元素已经与中间元比较完全,说明i左边的元素都比中间元小,i右边的元素都比中间元大(除中间元外),此时可以进入最后一步;③将中间元(在集合最右边)与下标为i的元素进行互换位置。假设我们现在有一个数组arr = {5, 7, 4, 2, 9, 6, 3, 8, 1};。那么具体的转换步骤如下图所示:

初始位置如上图所示,接着要选取中间元,这里中间元下标为(0 + 9) / 2 = 4,按照步骤①将5,9,1进行比较,并交换位置:

在步骤②中首先声明变量i和j分别指向7和8:

由于7比5大,故i停在此处,而8比5大,将j自减一位:

此时由于j所指向的元素值比5要小,j停在此处,由于i比j要小,故将i和j所指向的元素进行互换:

此时3比5小,7比5大,i自增一位,j自减一位:

此时4比5小,6比5大,i自增一位,j自减一位:

此时2比5小,9比5大,i自增一位,j自减一位:

由于9比5大,故i停在此处,2比5小,故j也停在此处,并且由于i比j大,因而步骤②结束,进入步骤③,将i所指向的元素与中间元位置互换:

此时,中间元5(也即i所指向的位置)左边的元素都比中间元要小,右边的元素则是大于等于中间元的。此时,我们就达到了通过中间元对集合进行分割的目的。

       这里需要说明的是,当我们要进行排序的集合较小(如大小为20以内)时,快速排序算法没有插入排序算法快(具体原因请查看相关文献),因而对于小集合我们将通过插入排序算法对其排序,具体的代码如下:

public class Sort {
  public static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] arr, int left, int right) {
    if (left + LENGTH_DIFF <= right) {

      AnyType pivot = medium(arr, left, right);

      int i = left, j = right;
      while (true) {
        while (arr[++i].compareTo(pivot) < 0);
        while (arr[--j].compareTo(pivot) > 0);

        if (i < j) {
          swapReferences(arr, i, j);
        } else {
          break;
        }
      }

      swapReferences(arr, i, right);
      quickSort(arr, left, i - 1);
      quickSort(arr, i + 1, right);
    } else {
      insertionSort(arr, left, right);
    }
  }

  private static <AnyType extends Comparable<? super AnyType>> AnyType medium(AnyType[] arr, int left,
      int right) {
    int center = (left + right) / 2;
    if (arr[center].compareTo(arr[left]) < 0) {
      swapReferences(arr, center, left);
    }
    if (arr[left].compareTo(arr[right]) > 0) {
      swapReferences(arr, left, right);
    }
    if (arr[center].compareTo(arr[right]) < 0) {
      swapReferences(arr, center, right);
    }

    return arr[right];
  }

  private static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] arr, int i, int j) {
    AnyType tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  private static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a, int left, int right) {
    int j;  // 记录第一个比tmp小的元素的后边一位的位置

    for (int p = left; p <= right; p++) {
      AnyType tmp = a[p];
      for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
        a[j] = a[j - 1];
      }
      a[j] = tmp;
    }
  }

  private final static int LENGTH_DIFF = 20;
}

       快速选择问题指的是获取一个集合中前k大(或小)的元素的集合。快速选择算法则是快速排序算法的一种变体,其思路和快速排序算法非常类似,在快速排序算法每次递归之后,中间元左边的元素都比中间元要大,中间元右边的元素都比中间元要小,由于中间元的下标为i,那么如果i小于k - 1的时候,那么i和i左边的元素都属于要求解的集合的元素,我们只需要对i右边的集合递归调用快速选择算法即可;如果i大于k - 1,那么前k大的集合肯定是i左边集合的子集,我们只需对i左边的集合递归调用快速选择算法即可;如果i等于k - 1,说明i所指的元素及其左边集合的元素正好是前k大的元素,那么递归调用可以终止。快速选择算法的实现例程和快速排序非常相似,只是在每次递归之后对下次递归集合的选取上有所不同,具体代码如下:

public class QuickSelect {
  private final static int LENGTH_DIFF = 20;
  public static <AnyType extends Comparable<? super AnyType>> void quickSelect(AnyType[] a, int left, int right, int k) {
    if (left + LENGTH_DIFF <= right) {
      AnyType pivot = medium(a, left, right);

      int i = left, j = right - 1;
      while (true) {
        while (a[++i].compareTo(pivot) < 0);
        while (a[--j].compareTo(pivot) > 0);

        if (i < j) {
          swapReferences(a, i, j);
        } else {
          break;
        }
      }

      swapReferences(a, i, right - 1);

      if (k <= i) {
        quickSelect(a, left, i - 1, k);
      } else if (k > i + 1) {
        quickSelect(a, i + 1, right, k);
      }
    } else {
      insertionSort(a, left, right);
    }
  }

  private static <AnyType extends Comparable<? super AnyType>> AnyType medium(AnyType[] arr, int left,
      int right) {
    int center = (left + right) / 2;
    if (arr[center].compareTo(arr[left]) < 0) {
      swapReferences(arr, center, left);
    }
    if (arr[left].compareTo(arr[right]) > 0) {
      swapReferences(arr, left, right);
    }
    if (arr[center].compareTo(arr[right]) < 0) {
      swapReferences(arr, center, right);
    }

    return arr[right];
  }

  private static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] arr, int i, int j) {
    AnyType tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  private static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a, int left, int right) {
    int j;  // 记录第一个比tmp小的元素的后边一位的位置

    for (int p = left; p <= right; p++) {
      AnyType tmp = a[p];
      for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
        a[j] = a[j - 1];
      }
      a[j] = tmp;
    }
  }
}

       本文详细叙述了快速选择算法的实现思想,分割策略以及每次分割的具体历程,并且简要概述了快速排序算法的变体快速选择算法及其实现例程。

© 著作权归作者所有

下一篇: 二叉树遍历
爱宝贝丶

爱宝贝丶

粉丝 354
博文 141
码字总数 481251
作品 0
武汉
程序员
私信 提问
加载中

评论(1)

每周精粹
每周精粹
不错 写的很好
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
29
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
64
0
Dart语法进阶篇(一)-- Dart源码的排序算法详解

版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/44ae73a58ebc 转载请标明出处: https://www.jianshu.com/p/44ae73a58ebc 本文出自 AWeiLoveAndroid的博客...

AWeiLoveAndroid
07/04
0
0
快速排序实现及其pivot的选取

coursera上斯坦福的算法专项在讲到快速排序时,称其为最优雅的算法之一。快速排序确实是一种比较有效的排序算法,很多类库中也都采用了这种排序算法,其最坏时间复杂度为$O(n^2)$,平均时间复...

xinyuexy
2018/10/05
0
0
java中常用算法(面试)

排序:对一组数据进行从小到大(或从大到小)的顺序排列。 排序算法有很多种,这里介绍Java中面试经常出现的三种排序方式:冒泡、选择、快速。 冒泡: 顾明思义,是气泡从液体的底部到顶部的...

u012843873
2017/04/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊nacos的notifyConfigInfo

序 本文主要研究一下nacos的notifyConfigInfo CommunicationController nacos-1.1.3/config/src/main/java/com/alibaba/nacos/config/server/controller/CommunicationController.java @Cont......

go4it
昨天
5
0
队列-顺序(c/c++实现)

队列是在线性表功能稍作一改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。 队列(顺序)实现的三个步骤: 定义所需的功能(...

白客C
昨天
5
0
安装tomcat部署网站/nginx代理tomcat/tomcat部署多个网站

来源:https://blog.csdn.net/Powerful_Fy 安装jdk: Oracle官方下载 https://www.oracle.com/technetwork/java/javase/downloads/index.html yum安装openjdk: 1.查找可使用的jdk包: [roo......

asnfuy
昨天
4
0
Linux 安装 Android studio

官网下载linux 版本 android xxxxx-xxxx.tar.gz 然后 找到它 解压缩 得到 android-studio文件夹 执行 [root@monkey java]# mv ./android-studio /opt [root@monkey java]# cd /opt/android-s......

MrLins
昨天
6
0
VMware vSphere虚拟机的迁移

VMware vSphere 6.7下,虚拟机的迁移按照移动的内容,可以分为4种: 1)冷迁移(cold migration) 2)热迁移(vMotion) 3)存储热迁移(storage vMotion) 4)完全热迁移(shared-nothing ...

大别阿郎
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部