您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

高级排序算法之快速排序

时间:2022-08-08 10:08:25  来源:  作者:人生就是一场修行321

前言

今天继续算法学习,本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法,可在文章:简单排序算法之冒泡、插入和选择排序-JAVA实现版 ,高级排序之归并排序、希尔排序。中查找相关方法,另外,本文也提供测试时使用的完整代码,对其他算法不感兴趣,可在文末找到完整源代码。

 快速排序

快速排序的本质就是把一个数组划分为两个子数组,然后递归地调用自身为每一个数组进行“快速排序”来实现的。这里就涉及一个问题:如何划分?

在快速排序中,为了划分数组,提出了“枢纽”这个词,它代表待排序序列中的一个数据项。快速排序利用枢纽将数组划分成两部分,一部分(枢纽左侧)是所有小于该枢纽表示的数据项,另一部分(枢纽右侧)则都大于该枢纽表示的数据项(注意,此时左右两侧的数据项是无序的),枢纽放置在左右两侧的中间,此时该枢纽已经处在排序的正确位置上了(枢纽是快速排序所排序的对象,实现“排序”的关键点就是调整枢纽的位置)。通过递归的这样划分,最终出现左侧只有一个数据项(该数据项既是左侧子数组又是枢纽),则结束左侧递归,开始划分右侧数组。。。以此类推。这里又产生了一个问题,如何选择枢纽?

选择枢纽的算法:最简单的选择枢纽算法就是每次递归都选择数组的最后一个数据项做为枢纽(或者选择最左侧的数据项作枢纽)。

上图演示了以子数组最右侧数据项做枢纽的排序过程

代码演示(枢纽始终使用子数组的最右侧数据项)

  private static int partitionIt(int left,int right,int pivot,int[] array){    int leftPtr = left-1;    int rightPtr = right;    while(true){      // 查找左侧子数组大于枢纽的位置      while(compare(array[++leftPtr],pivot)<0){      }      // 查询右侧子数组小于枢纽的位置      while(rightPtr>0&&compare(array[--rightPtr],pivot)>0){      }      if(leftPtr>=rightPtr){        break;      }      // 交换需要调整位置的两个数据项      swap(leftPtr,rightPtr,array);    }    // 将枢纽挪到两侧中间    swap(leftPtr,right,array);    return leftPtr;  }  private static void recQuickSort(int left,int right,int[] array){    if(right-left<=0){      return;    }    // 选择的枢纽    int pivot = array[right];    int partition = partitionIt(left,right,pivot,array);    recQuickSort(left,partition-1,array);    recQuickSort(partition+1,right,array);  }  public static void quickSort(int[] array){    compareCount=0;    swapCount=0;    long start = new Date().getTime();    recQuickSort(0,array.length-1,array);    long end = new Date().getTime();    printResult("快速排序","交换次数",start,end);  }

运行结果

冒泡排序——比较次数:49995000,交换次数:25153125,耗时:173毫秒

选择排序——比较次数:49995000,交换次数:9987,耗时:65毫秒

插入排序——比较次数:25075792,复制次数:25075793,耗时:42毫秒

归并排序——比较次数:120459,复制次数:267232,耗时:3毫秒

希尔排序——比较次数:233896,复制次数:238266,耗时:5毫秒

对随机序列排序:快速排序——比较次数:165181,交换次数:31700,耗时:3毫秒

对逆序序列排序:快速排序——比较次数:49825881,交换次数:9976,耗时:54毫秒

从运行结果中,可以看到对于随机序列,快速排序算法执行速度是非常快的,和归并排序相同,但给逆序序列排序时,效果则非常差,几乎和选择排序一样的效率了。那这是为什么呢?

根本原因,就在于枢纽的选择上,快速排序期望枢纽能够将数组拆分成两个长度几乎相同的子数组,这样能最优的平衡比较次数和交换次数。对于随机序列,简单的选择最右侧数据项做为枢纽不至于频繁出现左右子数组极度不平衡的情况,而对于逆序序列,则几乎每次划分都是极度不平衡的两个子数组,最终导致较大侧的子数组要被划分更多次。

优化枢纽选择算法

快速排序的最优划分结果是划分的两个数组长度相等,为了达到这个目的,我们每次都要在划分前,先找到子数组的中间数据项吗?显然,不能这么做的,因为很可能你找中值的时间远远大于你排序的时间了。所以,我们只能选择一个实现既不是过于复杂,又比“选择最右侧数据项做为枢纽”的算法更具普适性。

 

上图所示取枢纽的方法叫“三数据项取中”,即从数组中选择第一个、最后一个以及中间的数据项,从这三个数据项中取出大小在中间的项做为枢纽,在选择过程中,我们实际上也对这三个数据项做了排序,那顺便把分别大于、小于枢纽的那两个数据项也放到正确的位置(即左侧小于枢纽,右侧大于枢纽)。

该方法每次划分都需要至少有三个数据项,所以当子数组项数不大于3个的时候,就可以结束递归划分了,此时的排序可以通过其他排序算法实现,如使用手动排序(待排序的数据项不大于3个,所以手动排序完全可以轻松搞定),也可以使用插入排序(如果使用插入排序,我们甚至可以当数据项不大于10(这个10没有具体意义,你也可以20、30)的时候就可以用插入排序来收尾了)。下面我们用该方法来选择枢纽(用插入排序来收尾),对代码进行修改。

代码演示

  private static int medianOf3(int left,int right,int[] array){    int center = (left+right)/2;    if(array[left]>array[center]){      swap(left,center,array);    }    if(array[left]>array[right]){      swap(left,right,array);    }    if(array[center]>array[right]){      swap(center,right,array);    }    swap(center,right-1,array);    return array[right-1];  }  private static void insertSort(int left,int right,int[] array){    for (int i = left+1; i <= right; i++) {      int temp = array[i];      int cur = i;      // 右移数字,实现cur下标的左侧都是有序的      while (cur > 0 && compare(temp, array[cur - 1]) < 0) {        copy(cur-1,cur,array);        cur--;      }      // 如果cur==i则说明数据项已经在正确的位置了,不需要进行交换      if (cur != i) {        // 不满足temp<array[cur-1]时,则当前正在排的项temp已经找到正确位置了        copyData(temp,cur,array);      }    }  }  private static int partitionIt(int left,int right,int pivot,int[] array){    int leftPtr = left;    int rightPtr = right-1;    while(true){      // 查找左侧子数组大于枢纽的位置      while(compare(array[++leftPtr],pivot)<0){      }      // 查询右侧子数组小于枢纽的位置      while(compare(array[--rightPtr],pivot)>0){      }      if(leftPtr>=rightPtr){        break;      }      // 交换需要调整位置的两个数据项      swap(leftPtr,rightPtr,array);    }    // 将枢纽挪到两侧中间    swap(leftPtr,right-1,array);    return leftPtr;  }  private static void recQuickSort(int left,int right,int[] array){    int size = right-left+1;    if(size <10){      insertSort(left,right,array);    }else{      int median = medianOf3(left,right,array);      int partition = partitionIt(left,right,median,array);      recQuickSort(left,partition-1,array);      recQuickSort(partition+1,right,array);    }  }  public static void quickSort(int[] array){    compareCount=0;    swapCount=0;    long start = new Date().getTime();    recQuickSort(0,array.length-1,array);    long end = new Date().getTime();    printResult("快速排序","交换次数",start,end);  }

运行结果

冒泡排序——比较次数:49995000,交换次数:25138570,耗时:170毫秒

选择排序——比较次数:49995000,交换次数:9990,耗时:65毫秒

插入排序——比较次数:25069178,复制次数:25069176,耗时:34毫秒

归并排序——比较次数:120483,复制次数:267232,耗时:2毫秒

希尔排序——比较次数:231598,复制次数:235991,耗时:6毫秒

对随机序列排序:快速排序——比较次数:154857,交换次数:44570,耗时:3毫秒

对逆序序列排序:快速排序——比较次数:188034,交换次数:20067,耗时:1毫秒

从执行结果可以看出,优化过枢纽选择算法后,无论是随机序列排序还是逆序序列排序,排序速度都非常快。

至此,本文结束

完整代码

package team.ngup.study;import java.util.Arrays;import java.util.Date;import java.util.concurrent.ThreadLocalRandom;/** * @author zww * @date 2022/8/4 10:35 */public class SortStudy {  static final int ARRAY_SIZE = 10000;  static int compareCount = 0;  static int swapCount = 0;  /**   * 生成随机数数组   *   * @return   */  public static int[] buildRandomArray() {    int[] array = new int[ARRAY_SIZE];    for (int i = 0; i < ARRAY_SIZE; i++) {      int randomWithThreadLocalRandom = ThreadLocalRandom.current().nextInt(0, 1000000);      array[i] = randomWithThreadLocalRandom;    }    return array;  }  /**   * a和b位置的数据交换   *   * @param a   * @param b   * @param array   */  public static void swap(int a, int b, int[] array) {    swapCount++;    int temp = array[a];    array[a] = array[b];    array[b] = temp;  }  /**   * 复制 位置 a->b   * @param a   * @param b   * @param array   */  private static void copy(int a,int b,int[] array){    swapCount++;    array[b] = array[a];  }  /**   * 复制 数值a->位置b   * @param a   * @param b   * @param array   */  private static void copyData(int a,int b,int[] array){    swapCount++;    array[b]=a;  }  /**   * dataa大于datab返回1,否则返回-1   *   * @param dataa   * @param datab   * @return   */  public static int compare(int dataa, int datab) {    compareCount++;    if (dataa >= datab) {      return 1;    }    return -1;  }  /**   * 输出排序结果   *   * @param name 排序方法名   * @param operName 交换/复制   * @param start 开始时间   * @param end 结束时间   */  private static void printResult(String name,String operName,long start,long end){    System.out.print(        name            + "——比较次数:"            + compareCount            + ","+operName+":"            + swapCount            + ",耗时:"            + (end - start)            + "毫秒");  }  /** 冒泡排序 */  public static void maopao(int[] array) {    compareCount = 0;    swapCount = 0;    // 待排序序列长度,    int length = array.length;    long start = new Date().getTime();    while (length > 0) {      for (int a = 0; a < length - 1; a++) {        if (compare(array[a], array[a + 1]) > 0) {          // 交换位置          swap(a, a + 1, array);        }      }      // 一次从头到尾的遍历,找出了最右端的值(最大值),这将缩短第二次遍历的序列长度      length--;    }    long end = new Date().getTime();    // 输出排序结果    printResult("冒泡排序","交换次数", start, end);  }  /** 选择排序 */  public static void xuanze(int[] array) {    compareCount = 0;    swapCount = 0;    int length = 0;    long start = new Date().getTime();    while (length != array.length - 1) {      // 最小值位置      int minPosition = -1;      // 最小值      int min = array[length];      for (int i = length + 1; i < array.length; i++) {        if (compare(array[i], min) < 0) {          min = array[i];          minPosition = i;        }      }      // 存在比当前值还要小的值,则进行位置对换,否则无需对调位置      if (minPosition != -1) {        // 交换位置        swap(length, minPosition, array);      }      length++;    }    long end = new Date().getTime();    printResult("选择排序","交换次数", start, end);  }  /** 插入排序 */  public static void charu(int[] array) {    swapCount = 0;    compareCount = 0;    // 第一次排序无需比较,所以直接从1开始    long start = new Date().getTime();    for (int i = 1; i < array.length; i++) {      int temp = array[i];      int cur = i;      // 右移数字,实现cur下标的左侧都是有序的      while (cur > 0 && compare(temp, array[cur - 1]) < 0) {        copy(cur-1,cur,array);        cur--;      }      // 如果cur==i则说明数据项已经在正确的位置了,不需要进行交换      if (cur != i) {        // 不满足temp<array[cur-1]时,则当前正在排的项temp已经找到正确位置了        copyData(temp,cur,array);      }    }    long end = new Date().getTime();    printResult("插入排序" ,"复制次数", start, end);  }  // ------------------高级排序------------------------  private static void merge(int[] array, int[] workSpace, int lowPtr, int highPtr, int upperBound) {    int j = 0;    int lowerBound = lowPtr;    int mid = highPtr - 1;    int n = upperBound - lowerBound + 1;    while (lowPtr <= mid && highPtr <= upperBound) {      if (compare(array[lowPtr],array[highPtr])<0) {        copyData(array[lowPtr++],j++,workSpace);      } else {        copyData(array[highPtr++],j++,workSpace);      }    }    while (lowPtr <= mid) {      copyData(array[lowPtr++],j++,workSpace);    }    while (highPtr <= upperBound) {      copyData(array[highPtr++],j++,workSpace);    }    for (j = 0; j < n; j++) {      copyData(workSpace[j],lowerBound+j,array);    }  }  private static void recMergeSort(int[] array,int[] workSpace, int lowerBound, int upperBound) {    if (lowerBound == upperBound) {      return;    }    int mid = (lowerBound + upperBound) / 2;    recMergeSort(array,workSpace, lowerBound, mid); // 分割左侧    recMergeSort(array,workSpace, mid + 1, upperBound); // 分割右侧    merge(array,workSpace,lowerBound,mid+1,upperBound); // 合并排序  }  /**   * 合并排序   * @param array   */  public static void mergeSort(int[] array){    compareCount=0;    swapCount=0;    int[] workspace = new int[array.length];    long start = new Date().getTime();    recMergeSort(array,workspace,0,array.length-1);    long end = new Date().getTime();    printResult("归并排序","复制次数",start,end);  }  /**   * 希尔排序   * @param array   */  public static void xierSort(int[] array){    compareCount=0;    swapCount=0;    int inner,outer;    int temp;    int h=1;    // 计算跨度    while(h<=array.length/3){      h=h*3+1;    }    long start = new Date().getTime();    while(h>0){      for(outer=h;outer<array.length;outer++){        temp = array[outer];        inner = outer;        while(inner>h-1 && compare(array[inner-h],temp)>0){          copy(inner-h,inner,array);          inner -= h;        }        copyData(temp,inner,array);      }      h=(h-1)/3;    }    long end = new Date().getTime();    printResult("希尔排序","复制次数",start,end);  }  //-------------快速排序---------------------//  private static int medianOf3(int left,int right,int[] array){    int center = (left+right)/2;    if(compare(array[left],array[center])>0){      swap(left,center,array);    }    if(compare(array[left],array[right])>0){      swap(left,right,array);    }    if(compare(array[center],array[right])>0){      swap(center,right,array);    }    swap(center,right-1,array);    return array[right-1];  }  private static void insertSort(int left,int right,int[] array){    for (int i = left+1; i <= right; i++) {      int temp = array[i];      int cur = i;      // 右移数字,实现cur下标的左侧都是有序的      while (cur > 0 && compare(temp, array[cur - 1]) < 0) {        copy(cur-1,cur,array);        cur--;      }      // 如果cur==i则说明数据项已经在正确的位置了,不需要进行交换      if (cur != i) {        // 不满足temp<array[cur-1]时,则当前正在排的项temp已经找到正确位置了        copyData(temp,cur,array);      }    }  }  private static int partitionIt(int left,int right,int pivot,int[] array){    int leftPtr = left;    int rightPtr = right-1;    while(true){      // 查找左侧子数组大于枢纽的位置      while(compare(array[++leftPtr],pivot)<0){      }      // 查询右侧子数组小于枢纽的位置      while(compare(array[--rightPtr],pivot)>0){      }      if(leftPtr>=rightPtr){        break;      }      // 交换需要调整位置的两个数据项      swap(leftPtr,rightPtr,array);    }    // 将枢纽挪到两侧中间    swap(leftPtr,right-1,array);    return leftPtr;  }  private static void recQuickSort(int left,int right,int[] array){    int size = right-left+1;    if(size <10){      insertSort(left,right,array);    }else{      int median = medianOf3(left,right,array);      int partition = partitionIt(left,right,median,array);      recQuickSort(left,partition-1,array);      recQuickSort(partition+1,right,array);    }  }  public static void quickSort(int[] array){    compareCount=0;    swapCount=0;    long start = new Date().getTime();    recQuickSort(0,array.length-1,array);    long end = new Date().getTime();    printResult("快速排序","交换次数",start,end);  }  public static void main(String[] args) {    int[] array = buildRandomArray();    int[] array2 = Arrays.copyOf(array, ARRAY_SIZE);    int[] array3 = Arrays.copyOf(array, ARRAY_SIZE);    int[] array4 = Arrays.copyOf(array,ARRAY_SIZE);    int[] array5 = Arrays.copyOf(array,ARRAY_SIZE);    int[] array6 = Arrays.copyOf(array,ARRAY_SIZE);    maopao(array);    System.out.println();    xuanze(array2);    System.out.println();    charu(array3);    System.out.println();    mergeSort(array4);    System.out.println();    xierSort(array5);    System.out.println();    // 随机数据项 进行快速排序    System.out.print("对随机序列排序:");    quickSort(array6);    System.out.println();    // 将array6逆序    int[] array6a = new int[array6.length];    for(int i=array6.length-1,j=0;i>=0;i--){      array6a[j] = array6[i];      j++;    }    // 对逆序的数组使用快速排序    System.out.print("对逆序序列排序:");    quickSort(array6a);  }}

 



Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)&mdash;&mdash...【详细内容】
2022-10-01  Tags: 排序算法  点击:(12)  评论:(0)  加入收藏
前言今天继续算法学习,本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法,可在文章:简单排序算法之冒泡、插入和选择排序-Java实现版 ,高级排序之归并排序、希尔排...【详细内容】
2022-08-08  Tags: 排序算法  点击:(53)  评论:(0)  加入收藏
排序算法大致分为内部排序和外部排序两种内部排序:待排序的记录全部放到内存中进行排序,时间复杂度也就等于比较的次数外部排序:数据量很大,内存无法容纳,需要对外存进行访问再排...【详细内容】
2022-06-08  Tags: 排序算法  点击:(76)  评论:(0)  加入收藏
冒泡排序是所有排序算法中最简单、最易实现的算法,有时也称为起泡排序算法。使用冒泡排序算法对 n 个数据进行排序,实现思路是:从待排序序列中找出一个最大值或最小值,这样的操...【详细内容】
2022-05-06  Tags: 排序算法  点击:(173)  评论:(0)  加入收藏
桶排序算法就是把数据平分到每一个桶中,然后对桶中的数据进行排序,再按桶的顺序依次倒出数据,桶排序算法很好理解。桶排序算法也是以空间换时间的算法。举例说明一下桶排序算法...【详细内容】
2022-03-24  Tags: 排序算法  点击:(114)  评论:(0)  加入收藏
10种经典排序算法包括冒泡排序、选择排序、快速排序、归并排序、堆排序、插入排序、希尔排序、计数排序、桶排序、基数排序等。当然,还有一些其他的排序算法,大家可以继续去...【详细内容】
2022-03-11  Tags: 排序算法  点击:(98)  评论:(0)  加入收藏
前言:本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记。内容主要是关于十大经典排...【详细内容】
2022-03-04  Tags: 排序算法  点击:(106)  评论:(0)  加入收藏
一、什么是选择排序1.1、文字描述选择排序是一种简单直观的排序方式,它的工作原理是每一次排序时先从待处理数据元素中选择出一个最大(或最小)的元素,并存放在序列的末尾(起始)位...【详细内容】
2022-01-04  Tags: 排序算法  点击:(180)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 排序算法  点击:(158)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 排序算法  点击:(167)  评论:(0)  加入收藏
▌简易百科推荐
作者:小傅哥 博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!一、前言:挂在树上!不知道你经历过HashMap的夺命连环问!为啥,面试官那么喜欢让你聊聊 HashMap?因...【详细内容】
2022-10-10  小傅哥    Tags:红黑树   点击:(12)  评论:(0)  加入收藏
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  掂掂三生有幸  今日头条  Tags:数据结构   点击:(9)  评论:(0)  加入收藏
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  legendarykk  CSDN  Tags:链表   点击:(10)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  掂掂三生有幸    Tags:递归算法   点击:(10)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  掂掂三生有幸  今日头条  Tags:链表   点击:(9)  评论:(0)  加入收藏
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)&mdash;&mdash...【详细内容】
2022-10-01  掂掂三生有幸  今日头条  Tags:排序算法   点击:(12)  评论:(0)  加入收藏
实现优先级队列最常用的数据结构是堆,堆的常见实现有二叉堆、斐波那契堆、二项堆等。二叉堆堆是一种完全二叉树,我们以小根堆为例,小根堆的性质就是,每个节点都小于其左孩子和右...【详细内容】
2022-09-29  51Testing软件测试网     Tags:数据结构   点击:(9)  评论:(0)  加入收藏
简介布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回tru...【详细内容】
2022-09-13  java保佑我发大财  今日头条  Tags:布隆过滤器   点击:(51)  评论:(0)  加入收藏
1、A GPU accelerated Genetic Algorithm for the Construction of Hadamard Matrices Andras Balogh, Raven Ruiz这篇论文使用遗传算法来构建Hadamard矩阵。 生成随机矩...【详细内容】
2022-09-06  deephub  今日头条  Tags:遗传算法   点击:(63)  评论:(0)  加入收藏
导读:ClickHouse已经成为行业主流且热门的开源引擎。随着业务数据量扩大,场景覆盖变广泛,在复杂query场景下,ClickHouse容易存在查询异常问题,影响业务正常推进。本次主要分享字...【详细内容】
2022-09-05  互联共商     Tags:ClickHouse   点击:(43)  评论:(0)  加入收藏
站内最新
站内热门
站内头条