采用部分快速排序算法实现数组的部分排序 - eaglet的专栏 - CSDN博客

eaglet的专栏
登录 注册 欢迎 jijo2005! 退出 我的博客 配置 写文章 文章管理 博客首页   全站 当前博客  空间 博客 好友 相册 留言 用户操作
[发私信]  [加为好友] 
肖波ID：eaglet共34973次访问，排名4242(1)，好友9人，关注者31人。eaglet的文章
原创 69 篇
翻译 0 篇
转载 5 篇
评论 89 篇
订阅我的博客
    
 
 
 
eaglet的公告
文章分类
.Net 技术
Hubble.net
Lucene
办公软件使用技巧
操作系统
数据库
数据挖掘
搜索引擎
算法
网络技术
.Net 技术
BLOG风格设置
C#中如何快速将SQL_SERVER数据库中导出的数据导入到EXCEL里面
WebBrowser脚本错误的完美解决方案
Windows Workflow Beta2 HOL学习笔记（一）：创建一个简单的WF项目
Windows Workflow Beta2 HOL学习笔记（三）：使用IfElse Activity，声明条件和自定义活动
Windows Workflow Beta2 HOL学习笔记（二）：向工作流中传递参数
其他
存档
2009年05月(14)
2009年03月(2)
2008年11月(3)
2008年10月(5)
2008年09月(1)
2008年08月(1)
2008年07月(3)
2008年06月(2)
2008年05月(9)
2008年04月(4)
2007年09月(1)
2007年08月(5)
2007年07月(6)
2007年06月(1)
2007年05月(2)
2007年04月(12)
2003年10月(1)
2003年05月(2)
  采用部分快速排序算法实现数组的部分排序 收藏
采用部分快速排序算法实现数组的部分排序 Author: Eaglet      快速排序算法，网上相关文章已经介绍的很多了，数据结构教材中也有很详细的介绍。本文需要阐述的不是全排序快速排序算法，而是部分快速排序算法。所谓部分快速排序算法是指通过排序获取一个数列中最大的若干条有序记录。比如我们需要从一个有1百万记录的数组中获取前100条有序记录，并按从大到小顺序显示给用户，这种应用在搜索引擎中经常被使用，很少会有人有耐心将100万条搜索出来的记录都阅读一遍，一般阅读前几百条纪录就可以得到自己满意的答案。其实这种算法很像SQLSERVER 中的 TOP n 的实现，不过数据库是预先已经将记录通过B+树索引的方式进行了组织，实现方法完全不同。本文需要阐述的是不通过数据库，如何高效完成Top n 这种部分排序的功能。      在开始之前，我们先来分析一下2种其他的排序方法，如果进行部分排序。      1. 选择排序      选择排序方法实现部分排序非常简单，如果你需要获取长度为M的数组中前N条排序记录，你只需要对M条记录进行N次扫描，每次扫描都找出剩余序列中的最大（或最小值）就可以完成。当N 远小于 M 时，选择排序的时间复杂度大概为O(M*N)。      2. 堆排序      对排序可以说是实现部分排序时最常被用到的算法，包括著名的搜索组件Lucene在内都采用了堆排序来实现部分排序。具体算法我在网上找了一个，请参见 部分排序问题 。根据这篇文章所述，堆排序实现部分排序的实现复杂度是 O（MlogN)       现在让我们开始部分快速排序算法。       快速排序的一趟排序，可以根据一个基准值将数组分割成两个部分，基准前的所有数都比基准小，基准后的所有数都比基准大。如上图所示，5 就是这个基准值。全排序的快速排序算法，在实现了一趟排序后，通过递归分别对基准前后的数列再进行相同的排序直到所有数据都有序。      我们可以巧妙的利用这种基准分割的方法来实现部分排序。如果要实现部分排序，我们不需要对所有的数据都进行排序，其实每次只需要对基准的一边进行一趟排序就可以了，其原理很像二分查找。如上图，如果我们希望得到最小的前2个排序数据，我们只需要在第二次排序时对5之前的数列重新做一次一趟排序，而不需要对 5之后的数据做，因为5在一趟排序后被排在了第6位，其之后的数据肯定不可能出现在前2位。假设第二次我们选取5之前的数列的中间位置的值2作为基准，那么第二次一趟排序的过程如下3 4 2 1 5 5 9 8 7_ 4 3 1 5 5 9 8 7  (2)1 4 3 _ 5 5 9 8 7  (2)1 _ 3 4 5 5 9 8 7  (2)1 2 3 4 5 5 9 8 7两次一趟排序后，前2条排序记录已经算出，但从结果可以看出，这时整个数列并没有被完全排序，因为我们不需要完整的排序数列。 第二轮的演化过程请参考严蔚敏的数据结构教材，采用的是相同的算法。下面来分析一下部分快速排序的时间复杂度理想情况我们假设理想情况下，每次基准都选择在数列的中间位置，那么其扫描的趟数是1 + 1/2 + 1/4 + 1/8 ... 1/ K   (K = log(M/N)) + NlogN这个等比级数，如果K趋近为无穷的时候值为2，为什么是2，参考高等数学，这里不多阐述。那么现在我们可以看出，在这种情况下时间复杂度 < O(2M + NlogN), 当N远小于M时，时间复杂度近似为小于 O(2M)这个时间复杂度在N>4时要比部分堆排序的 O（MlogN)要小，而且随着N 的增大，部分快速排序的优势越来越明显。最佳情况 最佳情况并不是每次基准都出现的中间位置，而是第一趟排序选择的基准正好位于第N个位置。这时时间复杂度为O(M)最坏情况 每次基准出现在M-i 的位置，这时时间复杂度为 O (M*M)下面是测试结果：测试1 数组中为随机数据，数组长度M从2的16次方到2的22次方，N=100，每组长度下测试100次计算平均用时平均用时(单位毫秒)/
数组长度 65536 131072 262144 524288 1024857 2097152 41944304
部分快速排序 0.55 1.61 3.13 7.46 13.04 30.1 62.96
完全快速排序 10.45 21.85 45.55 93.97 197.3 405.54 841.75 测试2 数组中为以排序好的数据，数组长度M从2的16次方到2的22次方，N=100，每组长度下测试100次计算平均用时平均用时(单位毫秒)/
数组长度 65536 131072 262144 524288 1024857 2097152 41944304
部分快速排序 0.03 0 0.11 1.12 3.04 6.66 12.87
完全快速排序 2.12 4.9 10.49 21.6 44.29 91 185.77 从测试结果看采用部分快速排序获取前100条有序记录要比采用完全快速排序要快10到100倍。下面给出代码，由于.Net的Array.Sort就是完全快速排序，所以直接使用，没有自己实现完全快速排序。 QuickSort 类 using  System;
 using  System.Collections.Generic;
 using  System.Text;
 
 namespace  Sort
   {
       /**/ ///  

      ///  Quick Sort
      ///  

      ///  
      public   class  QuickSort < T >
        {
          // Partition for int
          private   static   int  PartitionInt( int [] array,  int  low,  int  high,  int  pivotIndex)
            {
              int  pivotValue  =  array[pivotIndex];
             array[pivotIndex]  =  array[low];
             array[low]  =  pivotValue;
 
              while  (low  <  high)
                {
                  while  (array[high]  >=  pivotValue  &&  high  >  low)
                    {
                      -- high;
                 }
 
                  if  (high  >  low)
                    {
                     array[low]  =  array[high];
                 }
 
                  while  (array[low]  <=  pivotValue  &&  high  >  low)
                    {
                      ++ low;
                 }
 
                  if  (high  >  low)
                    {
                     array[high]  =  array[low];
                 }
 
             }
 
             array[low]  =  pivotValue;
 
              return  low;
         }
 
          // Partition for long 
          private   static   int  PartitionLong( long [] array,  int  low,  int  high,  int  pivotIndex)
            {
              long  pivotValue  =  array[pivotIndex];
             array[pivotIndex]  =  array[low];
             array[low]  =  pivotValue;
 
              while  (low  <  high)
                {
                  while  (array[high]  >=  pivotValue  &&  high  >  low)
                    {
                      -- high;
                 }
 
                  if  (high  >  low)
                    {
                     array[low]  =  array[high];
                 }
 
                  while  (array[low]  <=  pivotValue  &&  high  >  low)
                    {
                      ++ low;
                 }
 
                  if  (high  >  low)
                    {
                     array[high]  =  array[low];
                 }
 
             }
 
             array[low]  =  pivotValue;
 
              return  low;
         }
 
          // Normal Partition
          private   static   int  Partition(T[] array,  int  low,  int  high,  int  pivotIndex, IComparer < T >  comparer)
            {
              if  (comparer  ==   null )
                {
                 Array arr  =  array;
 
                  if  ( typeof (T)  ==   typeof ( int ))
                    {
                      return  PartitionInt(( int [])arr, low, high, pivotIndex);
                 }
                  else   if  ( typeof (T)  ==   typeof ( long ))
                    {
                      return  PartitionLong(( long [])arr, low, high, pivotIndex);
                 }
             }
 
             T pivotValue  =  array[pivotIndex];
             T pLow  =  array[low];
 
              while  (low  <  high)
                {
                  while  (comparer.Compare(array[high], pivotValue)  >=   0   &&  high  >  low)
                    {
                      -- high;
                 }
 
                  if  (high  >  low)
                    {
                     array[low]  =  array[high];
                 }
 
                  while  (comparer.Compare(array[low], pivotValue)  <=   0   &&  high  >  low)
                    {
                      ++ low;
                 }
 
                  if  (high  >  low)
                    {
                     array[high]  =  array[low];
                 }
 
             }
 
             array[low]  =  pLow;
 
              return  low;
         }
 
          public   static   void  TopSort(T[] array,  int  top)
            {
             TopSort(array, top,  null );
         }
 
          public   static   void  TopSort(T[] array,  int  top, IComparer < T >  comparer)
            {
              // If comparer is null
              if  (comparer  ==   null )
                {
                 Array arr  =  array;
 
                  if  ( typeof (T)  !=   typeof ( int )  &&
                      typeof (T)  !=   typeof ( long ))
                    {
                     Array.Sort(array);
                      return ;
                 }
             }
 
              // Judge input
              if  (array.Length  <=   2   ||  top  >=  array.Length  /   2 )
                {
                 Array.Sort(array, comparer);
                  return ;
             }
 
              // One time partition
              int  pivot  =  Partition(array,  0 , array.Length  -   1 , array.Length  /   2 , comparer);
              int  lastPivot  =  pivot;
 
              // Run until pivot near the top
              while  (( ! (lastPivot  >=  top  &&  pivot  <=  top)))
                {
                 lastPivot  =  pivot;
 
                  if  (pivot  >  top)
                    {
                     pivot  =  Partition(array,  0 , pivot, pivot / 2 , comparer);
 
                      if  (pivot  ==  lastPivot)
                        {
                         pivot -- ;
                     }
                 }
                  else
                    {
                      if  (pivot  >=  array.Length  -   1 )
                        {
                         lastPivot  =  array.Length  -   1 ;
                          break ;
                     }
                    
                     pivot  =  Partition(array, pivot  +   1 , array.Length  - 1 , (array.Length  -  pivot)  /   2 , comparer);
                 }
             }
 
              // Finally sort
              if  (lastPivot  <  array.Length)
                {
                 Array.Sort(array,  0 , lastPivot  +   1 , comparer);
             }
              else
                {
                 Array.Sort(array,  0 , lastPivot, comparer);
             }
         }
     }
 }
 
 测试代码          static   void  Main( string [] args)
            {
              int [] testArr  =   null ;
              int [] testArr1  =   null ;
             Stopwatch sw  =   new  Stopwatch();
             List < int >  testValues  =   new  List < int > ();
 
             Random rand  =   new  Random();
 
              int  pow  =   16 ;
 
              int  count  =  ( int )Math.Pow( 2 , pow);
              int  top  =   100 ;
 
              while  (pow  <   23 )
                {
                 Console.WriteLine( string .Format( " Test count={0} " , count));
 
                  double  topSortElapsedMilliseconds  =   0 ;
                  double  fullSortElapsedMilliseconds  =   0 ;
 
                  for  ( int  j  =   0 ; j  <   100 ; j ++ )
                    {
 
                     testValues.Clear();
 
                      for  ( int  i  =   0 ; i  <  count; i ++ )
                        {
                         testValues.Add(rand.Next());
                          // testValues.Add(i);
                     }
 
                     testArr  =   new   int [testValues.Count];
                     testArr1  =   new   int [testValues.Count];
 
                     testValues.CopyTo(testArr);
                     testValues.CopyTo(testArr1);
 
                     sw.Reset();
                     sw.Start();
                     Sort.QuickSort < int > .TopSort(testArr, top);
 
                     sw.Stop();
 
                     topSortElapsedMilliseconds  +=  sw.ElapsedMilliseconds;
 
                     sw.Reset();
                     sw.Start();
                     Array.Sort(testArr1);
 
                     sw.Stop();
 
                     fullSortElapsedMilliseconds  +=  sw.ElapsedMilliseconds;
 
                      // Compare result
                      for  ( int  i  =   0 ; i  <  top; i ++ )
                        {
                          if  (testArr[i]  !=  testArr1[i])
                            {
                             Console.WriteLine( string .Format( " Wrong at {0}! {1} {2} " ,
                                 i, testArr[i], testArr1[i]));
 
                             Console.ReadKey();
                            
                              // For test
                              while  ( true )
                                {
                                 testValues.CopyTo(testArr);
                                 Sort.QuickSort < int > .TopSort(testArr, top);
                             }
                         }
                     }
 
                 }
 
                 Console.WriteLine( string .Format( " Top sort elapses {0} ms " ,
                     topSortElapsedMilliseconds / 100 ));
                 Console.WriteLine( string .Format( " Full sort elapses {0} ms " ,
                     fullSortElapsedMilliseconds / 100 ));
 
                 count  *=   2 ;
                 pow ++ ;
             }
 
             Console.ReadKey();
 
         }
发表于 @ 2009年05月25日　09:34:00 | 评论( 0 ) | 编辑| 举报| 收藏 旧一篇:Hubble.net 持久化方面3个重大改进 | 新一篇:对 String 的几个错误认识姓   名：
校验码：重新获得验证码
 Csdn Blog version 3.1a
Copyright © eaglet   本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/eaglet/archive/2009/05/25/4213568.aspx