注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

C# 快速排序  

2011-02-25 09:48:27|  分类: C# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

快速排序(Quick Sort)的基本思想是:通过不断比较关键码,以某个记录为界(该记录称为支点),将待排序列分成两部分。其中,一部分满足所有记录的关键码都大于或等于支点记录的关键码,另一部分记录的关键码都小于支点记录的关键码。把以支点记录为界将待排序列按关键码分成两部分的过程,称为一次划分。对各部分不断划分,直到整个序列按关键码有序为止。
设待排序的顺序表sqList中有n个记录,一般地,第一次划分把第一个记录作为支点。首先,把支点复制到一个临时存储空间中,并设两个指示器,一个指示器low,指向顺序表的低端(第一个记录所在位置),一个指示器high,指向顺序表的高端(最后一个记录所在位置)。然后,从high所指向的记录开始,将记录的关键码与支点(在临时存储空间中)的关键码进行比较,如果high所指向的记录的关键码大于支点的关键码,high指示器向顺序表的低端方向移动一个记录的位置,否则,将high所指的记录复制到low所指的存储空间中。接着,又将low移到下一个记录,从low所指向的记录开始,将记录的关键码与临时存储空间的记录的关键码进行比较,如果low所指向的记录的关键码小于临时存储空间的记录的关键码,low指示器向顺序表的高端方法移动一个记录的位置,否则,将low所指的记录复制到high所指的存储空间中,high指示器向顺序表的低端移动一个记录的位置。如此重复,直到low和high指示器指向同一个记录,将临时空间的记录赋给low所指向的存储空间,第一次划分结束。
快速排序的算法实现如下所示,算法中记录的比较表示记录关键码的比较,

顺序表中只存放了记录的关键码:

public void QuickSort(List<int> sqList, int low, int high)
        {
            int i = low;
            int j = high;
            int tmp = sqList[low];
            while (low < high)
            {
                while ((low < high) && (sqList[high] >= tmp))
                {
                   --high;
                }
                sqList[low] = sqList[high];
                ++low;
                while ((low < high) && (sqList[low] <= tmp))
                {
                  ++low;
                }
                sqList[high] = sqList[low];
                --high;
            }
            sqList[low] = tmp;
            if (i < low-1)
            {
                QuickSort(sqList, i, low-1);
            }
            if (low+1 < j)
            {
               QuickSort(sqList, low+1, j);
            }
        }
【例7-4】关键码序列为(42,20,17,27,13,8,17*,48),写出用快速排序算法进行排序的过程。
快速排序过程如下所示。

C 快速排序 - 海里的贝壳 - apple的博客

 

C 快速排序 - 海里的贝壳 - apple的博客
C 快速排序 - 海里的贝壳 - apple的博客
 快速排序算法的时间复杂度和每次划分的记录关系很大。如果每次选取的记录都能均分成两个相等的子序列,这样的快速排序过程是一棵完全二叉树结构(即每个结点都把当前待排序列分成两个大小相当的子序列结点,n个记录待排序列的根结点的分解次数就构成了一棵完全二叉树),这时分解次数等于完全二叉树的深度log2n。每次快速排序过程无论把待排序列这样划分,全部的比较次数都接近于n-1次,所以,最好情况下快速排序的时间复杂度为O(nlog2n)。快速排序算法的最坏情况是记录已全部有序,此时n个记录待排序列的根结点的分解次数就构成了一棵单右支二叉树。所以在最坏情况下快速排序算法的时间复杂度为O(n2)。一般情况下,记录的分布是随机的,序列的分解次数构成一棵二叉树,这样二叉树的深度接近于log2n,所以快速排序算法在一般情况下的时间复杂度为O(nlog2n)。
另外,快速排序算法是一种不稳定的排序的方法。
  评论这张
 
阅读(754)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017