《漫谈经典排序算法一》由会员分享，可在线阅读，更多相关《漫谈经典排序算法一（21页珍藏版）》请在金锄头文库上搜索。
1、11月热门下载资源TOP100强力推荐！ 点击了解英特尔云计算 漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析分类： Data Structures And Algorithms2011-09-12 10:542657人阅读评论(11)收藏举报1、序言这是漫谈经典排序算法系列第一篇，该篇从最简单的选择排序算法谈起，由浅入深的详细解析两种选择排序算法的过程及性能比较。逐步揭露选择排序的本质及其基本思想。各种排序算法的解析请参考如下： 漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析漫谈经典排序算法:二、各种插入排序解析及性能比较漫谈经典排序算法:三、冒泡排序 & 快速排序漫谈经典排
2、序算法:四、归并排序漫谈经典排序算法:五、线性时间排序(计数、基数、桶排序)漫谈经典排序算法:六、各种排序算法总结 注：为了叙述方便，本文以及源代码中均不考虑A0,默认下标从1开始。2、提出问题（1）简单选择排序和堆排序的基本思想是什么？（2）选择排序的本质是什么？相信看完这篇文章，读者一定可以找到答案。 3、漫谈简单选择排序3.1 从一个简单问题谈起给定待排序序列A 1.n ，选择出A中最小的记录（也可以理解为求一个无序数组A中的最小的元素）。下面给出代码如下：view plaincopy to clipboardprint?1. /选择待排序序列a中的最小记录,其下标为index 2. f
3、or(index=i=1;i=n;i+) 3. if(aiaindex) 4. index=i; 5. 相信这段代码大家都能看懂，其中Aindex即为要找的最小记录。也许有人要问作者是在写选择排序，干嘛要谈这个简单的问题呢？请不要急，看到后面自然就知道了。3.2 简单选择排序的过程描述：给定待排序序列A 1.n ，选择出第i小元素，并和Ai交换，这就是一趟简单选择排序。代码：view plaincopy to clipboardprint?1. /简单选择排序 2. void simpleSelectionSort1(int *a,int n) 3. 4. int i,j,index; 5.
4、/1.进行n-1趟选择，每次选出第i小记录 6. for(i=1;in;i+) 7. index=i; 8. /2.选择第i小记录为aindex 9. for(j=i+1;j=n;j+) 10. if(ajaindex) 11. index=j; 12. /3.与第i个记录交换 13. if(index!=i) 14. ai=ai+aindex; 15. aindex=ai-aindex; 16. ai=ai-aindex; 17. 18. 19. 示例：假设给定数组A1.6= 3,5,8,9,1,2 ，我们来分析一下A数组进行选择排序的过程第一趟：i=1，index=5， a1 和 a5 进
5、行交换。得到序列： 1,5,8,9,3,2 第二趟：i=2，index=6， a2 和 a6 进行交换。得到序列： 1,2,8,9,3,5 第三趟：i=3，index=5， a3 和 a5 进行交换。得到序列： 1,2,3,9,8,5 第四趟：i=4，index=6， a3 和 a5 进行交换。得到序列： 1,2,3,5,8,9 第五趟：i=5，index=5， 不用交换。得到序列： 1,2,3,5,8,9 （6-1）趟选择结束，得到有序序列： 1,2,3,5,8,9 3.3 性能分析容易看出，简单选择排序所需进行记录移动的操作次数较少，这一点上优于冒泡排序，最佳情况下（待排序序列有序）记录移
6、动次数为0，最坏情况下（待排序序列逆序）记录移动次数n-1。外层循环进行了n-1趟选择，第i趟选择要进行n-i次比较。每一趟的时间：n-i次的比较时间+移动记录的时间（为一常数0或1，可以忽略）。总共进行了n-1趟。忽略移动记录的时间，所以总时间为(n-1)*(n-i)=n2-(i+1)*n+i。时间复杂度为O（n2）。不管是最坏还是最佳情况下，比较次数都是一样的，所以简单选择排序平均时间、最坏情况、最佳情况 时间复杂度都为O（n2）。同时简单选择排序是一种稳定的原地排序算法。当然稳定性还是要看具体的代码，在此就不做深究。 3.4 简单选择排序引发的思考 第一趟排序后： 1,5,8,9,3,2
7、 ，此时A 1 已经有序，我们可以把待排序序列缩减到A 2.6 第二趟排序后： 1,2,8,9,3,5 ，此时A 1.2 已经有序，我们可以把待排序序列缩减到A 3.6 第三趟排序后： 1,2,3,9,8,5 ，此时A 1.3 已经有序，我们可以把待排序序列缩减到A 4.6 第四趟排序后： 1,2,3,5,8,9 ，此时A 1.4 已经有序，我们可以把待排序序列缩减到A 5.6 第五趟排序后： 1,2,3,5,8,9 ，此时A 1.5 已经有序，我们可以把待排序序列缩减到A 6.6 也就是说第i趟后，A 1.i 已经有序，待排序序列缩减为A (i+1).n 。这是一个待排序序列中记录不断减少的
8、递归过程。也许很多读者已经发现，我们每次都是从待排序序列中选择最小的那个记录然后跟待排序序列的首元素进行交换。于是可以用一个递归函数来进行简单选择排序，代码如下：view plaincopy to clipboardprint?1. /递归函数进行简单选择排序 2. void simpleSelectionSort2(int *a,int n) 3. 4. int index,i; 5. if(n=1) 6. return; 7. /1.选择待排序序列a中的最小记录,其下标为index 8. for(index=i=1;i=n;i+) 9. if(aiaindex) 10. index=i;
9、11. 12. /2.最小记录与待排序序列首元素进行交换 13. if(index!=1) 14. a1=a1+aindex; 15. aindex=a1-aindex; 16. a1=a1-aindex; 17. 18. /3.待排序序列元素个数减少，递归对剩下的无序序列排序 19. simpleSelectionSort2(a+1,n-1); 20. 看到这里，不知大家是否还记得上文3.1中谈到的简单的问题。由此可以看出这个简单的问题正是简单选择排序的本质所在。4、深入堆排序4.1 堆排序的引入从上文我们知道简单选择排序的时间复杂度为O（n2），熟悉各种排序算法的朋友都知道，这个时间复杂度
10、是很大的，所以怎样减小简单选择排序的时间复杂度呢？从上文分析中我们知道简单选择排序主要操作是进行关键字的比较，所以怎样减少比较次数就是改进的关键。 简单选择排序中第i趟需要进行n-i次比较，如果我们用到前面已排好的序列a1.i-1是否可以减少比较次数呢？答案是可以的。举个例子来说吧，A、B、C进行比赛，B战胜了A，C战胜了B，那么显然C可以战胜A，C和A就不用比了。正是基于这种思想，有人提出了树形选择排序：对n个记录进行两两比较，然后在（n/2向上取整）个较小者之间在进行两两比较，如此重复，直到选出最小记录。但是这种排序算法需要的辅助空间比较多，所以威洛姆斯在1964年提出了另一种选择排序，这
11、就是下面要谈的堆排序。4.2 什么是堆首先堆是一种数据结构，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值，如下是一个堆得示例：98,95;83,81;52 由此发现非叶子结点的值均不小于左右孩子结点的值，所以这是个大顶堆，即堆顶的值是这个堆中最大的一个。下面的问题是我们怎么样在计算机中存储这个堆呢？也许有人会想到树的存储，确实，刚看这个堆我也是这么想的。然而事实并非如此，这个堆可以看成是一个一维数组A6=9,8,5,3,1,2，那么相应的这个数组需满足性质：Ai=A2*i & Ai=A2*i+1 。其中Ai对应堆中的非叶子结点，A2*i和A2*i+1对应
12、于左右孩子结点。并且最后一非叶子结点下标为n/2向下取整。为什么是n/2向下取整呢？在这里我简单的说明一下：设n1表示完全二叉树中有一个孩子的结点，n2表示表示完全二叉树中有两个孩子的结点，d表示非叶子结点的个数，那么总的结点个数：n=n1+2*n2+1。（1）当n为奇数时，n1=0，n2=(n-1)/2，d=n2+n1=(n-1)/2（2）当n为偶数时，n1=1，n2=n/2-1，d=n2+n1=n/2由此可以看出d=n/2向下取整.注：请大家一定要结合完全二叉树形式的堆以及堆的数组存储形式来看下面的内容，这样才能真正理解堆排序的过程及其本质。4.3 筛选法调整堆（1）引出：现给定一个大顶堆
13、： 即：A6=9,8,5,3,1,2，如果我们稍做破坏，把9跟2互换，同时把a6这个结点从堆中去掉，于是得到下面这个完全二叉树：A5=2,8,5,3,1显然它不是一个堆，那我们怎么把它调整为一个堆呢？首先观察，我们只是改变了根结点的值，所以根结点左、右子树均是大顶堆。其次思考，既然是根结点可能破坏了堆的性质，那我们就可以把根结点往下沉，让最大值网上浮，即比较根结点和左、右孩子的值，若根结点的值不小于孩子结点的值，说明根结点并没有破坏堆的性质，不用调整；若根结点的值小于左右孩子结点中的任意一个值，则根结点与孩子结点中较大的一个互换，互换之后又可能破坏了左或右子树的堆性质，于是要对子树进行上述调整
14、。这样的一次调整我们称之为一次筛选。（2）代码：view plaincopy to clipboardprint?1. /调整堆，保持大顶堆的性质,参数i指向根结点 2. void maxHeap(int *a,int n,int i) 3. 4. /left、right、largest分别指向 5. /左孩子、右孩子、ai,aleft中最大的一个 6. int left,right,largest; 7. largest=left=2*i; 8. if(leftn) 9. return; 10. right=2*i+1; 11. if(rightaleft) 12. largest=right; 13. 14. if(aialargest)/根结点的值不是最大时,交换ai，alargest 15. ai=ai+alar
