快速排序c语言.docx

《快速排序c语言.docx》由会员分享，可在线阅读，更多相关《快速排序c语言.docx（9页珍藏版）》请在课桌文档上搜索。

1、快速排序是由东尼霍尔所发展的一种排序和法。在平均状况下，排序n个项目要O(nlogn)次比较。在最坏状况下则需要0(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环(innerloop)可以在大部分的架构上很有效率地被实现出来。快速排序思路快排思路： 取一个元素P(第一个元素)，使元素pln位； 列表被P分成两部分，左边都比P小，右边都比P大; 递归完成排序。排序前：Tpl3I1I2I9T:算法关键点P归位：IlllllIlIII11:1 .整理2 ,递归Il标：11I2I3I6日I二c盾高细是字为基咫算法步骤：1从数列中挑出一个元素，

2、称为基准(pivot)。2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。3递归(recursive)的把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代(iteration)中，它至少会把一个元素摆到它最后的位置去。C代码的实现如下:voidquickSort(intnum,intcount,intleft,intri

3、ght)if(left三right)(return;intkey=numleft;左下标右下标intIp=left;intrp三right;while(Iprp)if(numrp=lp;i-)numi+1=numi;numlp三temp;Ip+；rp+;rp-；)对左半部分排序对右半鳖湾编程宇为菖quickSort(num,count,left,Ip-1);quickSort(num,count,rp+1,right);)下面开始单步分析，这里用一个数组的数据来分析开始数据：。815%耳语翱添首先将。作为比较的基准，由于右边所有的数据都比。大，所以数据不做移动。接下来将8作为比较基准，从最右边

4、开始和8比较。此时6比8小，将6移动到8前面，其他数据依次后移。key=8移动完成：0681胸C啰窣等鳖接着在将2和8比较，2比8小，继续将2移动到8前面，其他的数据依次后移。这样将8小的数据移动到8的前面，比8大的数据在8后面保持不变。移动完成后如下:移动完成：06273烟借言吟习a接下来比较的基准变为数字6,将比6小的数据移动到6前面。从最右边开始查找，找到1比6小，将1移动到6前面。key=6-移动完成：。1627号单号譬羿然后继续依次寻找比6小的数字，移动到6的前面，移动完成后如下:key三6移动完成：。1543。辞言朝争习a然后比较的基准变为数字5,从最右边开始寻找比5小的数移动到5

5、前面。查找到的数据为2。key=5移动完成：。125串科野臂电学依次查找其他比5小的数据，移动完成后如下:key=5移动完成：01234哈（fefe隐标到这里可以看到数据排序已经完成r。整体运行流程如下:下面测试一下最坏情况下的排序情况3 H 5 16 2 75 6 25 4 65 4 35 38 93 4 5 8 97 3 4 8 92 7 3 8 96 2 7 8 92 6 7 8 9开始数强：。123456789丸行时值为38 BS开始致格：8 123456789可吟数出：e 15 4 3 2 6 7 8 9开始数据：。8 15 4 3 7 9 2 64 3 7 6819 685 M 3

6、79O 671 5 H389e 6738 1 S M98 6734 8 1590 673H 5 8 19O 63H 5 1 89开始数格。8 15 4 3 7 9 2 6quicksort tst C语言编程学演OO0G成 宽成成 完格 数 始成 完成 完6动6动6动6动6动 移，移移移移 y y y y y? 2 6 Okey三8移动完成：key8移动完成：key三8移动完成：key三8移动先成：kyX8移动完成：key三8移动完成：ky三8移动完成：开始数据:。154326789key三5移动完成：8125436789key三5移动完成：8123546789key三5移动完成：812345

7、6789可以看到最坏情况下排序的次数并没有增多，反而感觉还减少了。在看一下最好情况下的排序情况：quicksorttst开始效梏：987654321。key三9移动完成：e98765321key三9移动完成：e198765H32key三9移动完成：e129876543ky三9移动完成：12398?654key三9移动完成：e123H98?65key19移动完成：01234S987Gkey三9移动完成：e123HS6987key三9移动完成：e123456798k”三3移动完成：e12356789开始数据:。123456789开始数据:日123456789开始数据:。123456789开始数据：

8、。12开始致客：。12开始数据：。123456开始数据：812开始数据：8123456789执行时间为30.8C语言编程学习基地山UKd请按任意爆继续.最好情况下数据也要进行比较9次。DDesktopsortqickSort.exeIquickSorttect开始数据:。开始数据：0开始数据:。开始数据：8开始数据:。开始数据：。开始数据：。开始数据:。执行时阊为12.9P黄接任修，:，TC语言编程学习基J下来随机生成一个包含IOooo个数字的数组,，测试下执行时间。可以看到对IoOOO个数字排序需要的时间为120mso下面用一张动图来演示一下快速排序的过程:13另外，对现在我们的大多数朋友来说还是学编程技术最重要！栽一棵树最好的时间是十年前，其次是现在。对于准备学习编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！