开发者社区> 问答> 正文

快速排序算法原理与实现

知与谁同 2018-07-18 18:35:12 309
谁帮我说明一下,网上和书上写的文字没看明白。
搜索推荐
分享到
取消 提交回答
全部回答(4)
  • 聚小编
    2019-07-17 22:49:35
    概述
    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn)次比较。事实上,快速排序通常明显比其他Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,并且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。
    快速排序,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
    形象图示:

    步骤
    选择一个基准元素,通常选择第一个元素或者最后一个元素
    通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值均比基准值大
    此时基准元素在其排好序后的正确位置
    然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    实例
    原始数据:
    3 5 2 6 2
    选择 3 作为基准
    第一轮
    ?

    1234567

    从右往左找比3小的,2符合,将2和3对调2 5 2 6 3对调一次,查找的方向反向,从左向右找比3大的,5符合,对调2 3 2 6 5再从右往左找比3小的,2符合,对调2 2 3 6 5一轮结束

    第二轮
    ?

    12

    对 [2 2] 采用同上的方式进行,得到2 2 3 6 5

    第三轮
    ?

    12

    对 [6 5] 采用同上的方式进行,得到2 2 3 5 6

    最终结果
    2 2 3 5 6
    代码实现(Java)
    ?

    12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091

    package com.coder4j.main.arithmetic.sorting; public class Quick { private static int mark = 0; /** * 辅助交换方法 * * @param array * @param a * @param b */ private static void swap(int[] array, int a, int b) { if (a != b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; // 找到符合的,对调 System.out.println("对调" + array[a] + "与" + array[b] + ",得到"); for (int i : array) { System.out.print(i + " "); } System.out.println(); } } /** * 新一轮分隔 * * @param array * @param low * @param high * @return */ private static int partition(int array[], int low, int high) { int base = array[low]; mark++; System.out.println("正在进行第" + mark + "轮分隔,区域:" + low + "-" + high); while (low < high) { while (low < high && array[high] >= base) { high--; System.out.println("从右往左找比" + base + "小的,指针变动:" + low + "-" + high); } swap(array, low, high); while (low < high && array[low] <= base) { low++; System.out.println("从左往右找比" + base + "大的,指针变动:" + low + "-" + high); } swap(array, low, high); } return low; } /** * 对数组进行快速排序,递归调用 * * @param array * @param low * @param heigh * @return */ private static int[] quickSort(int[] array, int low, int heigh) { if (low < heigh) { int division = partition(array, low, heigh); quickSort(array, low, division - 1); quickSort(array, division + 1, heigh); } return array; } /** * 快排序 * * @param array * @return */ public static int[] sort(int[] array) { return quickSort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("最终结果"); for (int i : sorted) { System.out.print(i + " "); } } }

    测试输出结果:
    ?

    12345678910111213141516171819

    全选复制放进笔记正在进行第1轮分隔,区域:0-4对调2与3,得到2 5 2 6 3从左往右找比3大的,指针变动:1-4对调3与5,得到2 3 2 6 5从右往左找比3小的,指针变动:1-3从右往左找比3小的,指针变动:1-2对调2与3,得到2 2 3 6 5从左往右找比3大的,指针变动:2-2正在进行第2轮分隔,区域:0-1从右往左找比2小的,指针变动:0-0正在进行第3轮分隔,区域:3-4对调5与6,得到2 2 3 5 6从左往右找比6大的,指针变动:4-4最终结果2 2 3 5 6

    经测试,与实例中结果一致。
    0 0
  • 玄学酱
    2019-07-17 22:49:35
    1、设置两个变量I、J,排序开始的时候I:=1,J:=N;
    2、以第一个数组元素作为关键数据,赋值给X,即X:=A[1];
    3、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;
    4、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;
    5、重复第3、4步,直到I=J;
    0 0
  • 小哇
    2019-07-17 22:49:35
    我也是初学者,可能回答的你会理解。
    举个例子 char s[]={d , x , a ,r , p , j , i }
    s[0] s[1] s[2] s[3] s[4] s[5] s[6]
    在要排序的几个字母里,选一个固定的字母(我习惯选择中间一个r)
    从左边第一个起依次向右直到 r处 找出第一个比r大的 s[1 ]x
    从右边最后一个起一次向左直到r处 找出第一个比r小的 s[6] i
    交换这两个,此时为 d i a r p j x
    接着上面的继续找 左边一直到r已经没有比它大的,那就停在r处
    右边找到 j 比r小 将 r与j j交换 d i a j p r x
    右边继续往前找 发现p比r小 交换 d i a j r p x
    此时数组已经全部被遍历
    r左边全都是比它小的 右边全是比它大的
    通过循环再对左右进行相同的过程
    思想明白了,代码就好写了吧。。。
    不知道讲没讲明白 不明白可以发邮件问我
    2468233107@qq.com
    0 0
  • 行者武松
    2019-07-17 22:49:35
    快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是:

    1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;

    2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

    3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;

    4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

    5)、重复第3、4步,直到I=J;

    例如:待排序的数组A的值分别是:(初始关键数据X:=49)

    A[1] A[2] A[3] A[4] A[5] A[6] A[7]:

    49 38 65 97 76 13 27

    进行第一次交换后: 27 38 65 97 76 13 49

    ( 按照算法的第三步从后面开始找

    进行第二次交换后: 27 38 49 97 76 13 65

    ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )

    进行第三次交换后: 27 38 13 97 76 49 65

    ( 按照算法的第五步将又一次执行算法的第三步从后开始找

    进行第四次交换后: 27 38 13 49 76 97 65

    ( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )

    此时再执行第三不的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

    快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

    初始状态 {49 38 65 97 76 13 27}

    进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

    分别对前后两部分进行快速排序 {13} 27 {38}

    结束 结束 {49 65} 76 {97}

    49 {65} 结束

    结束

    图6 快速排序全过程

    1)、设有N(假设N=10)个数,存放在S数组中;

    2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K];

    3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

    如具体数据如下,那么第一躺快速排序的过程是:

    数组下标: 1 2 3 4 5 6 7 8 9 10

    45 36 18 53 72 30 48 93 15 36

    I J

    (1) 36 36 18 53 72 30 48 93 15 45

    (2) 36 36 18 45 72 30 48 93 15 53

    (3) 36 36 18 15 72 30 48 93 45 53

    (4) 36 36 18 15 45 30 48 93 72 53

    (5) 36 36 18 15 30 45 48 93 72 53

    通过一躺排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。

    一般来说,冒泡法是程序员最先接触的排序方法,它的优点是原理简单,编程实现容易,但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法,我不知道它是不是现有排序方法中最快的,但它是我见过的最快的。排序同样的数组,它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

    “快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53,12,98,63,18,72,80,46, 32,21},先找到第一个数--53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组,而这两个数组继续用同样的方式继续下去,一直到顺序完全正确。

    我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

    /*
    n就是需要排序的数组,left和right是你需要排序的左界和右界,
    如果要排序上面那个数组,那么left和right分别是0和9
    */

    void quicksort(int n[], int left,int right)
    {
    int dp;
    if (left<right) {

    /*
    这就是下面要讲到的函数,按照上面所说的,就是把所有小于53的数放
    到它的左边,大的放在右边,然后返回53在整理过的数组中的位置。
    */
    dp=partition(n,left,right);

    quicksort(n,left,dp-1);

    quicksort(n,dp+1,right); //这两个就是递归调用,分别整理53左边的数组和右边的数组
    }
    }

    我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后

    返回这中间值的位置,下面这函数就是做这个的。
    int partition(int n[],int left,int right)
    {
    int lo,hi,pivot,t;

    pivot=n[left];
    lo=left-1;
    hi=right+1;

    while(lo+1!=hi) {
    if(n[lo+1]<=pivot)
    lo++;
    else if(n[hi-1]>pivot)
    hi--;
    else {
    t=n[lo+1];
    n[++lo]=n[hi-1];
    n[--hi]=t;
    }
    }

    n[left]=n[lo];
    n[lo]=pivot;
    return lo;
    }

    这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。
    0 0
添加回答
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题