gr8vyguy@Blogjava

Insertion-Sort和Merge-Sort

Insertion-SortMerge-Sort是两种非常有代表性的排序算法。Insertion-Sort逐个将未排序的元素插入到正确的位置,下面这张图很形象的描述了Insertion-Sort.


所以Insertion-Sort也是一种incremental的算法。Merge-Sort采用一种完全不同的方式,即是divide-and-conquer, 将元素分成两组,先分别将这两组排好序,然后再组合起来,就如下图所示,


Java实现

Insertion-Sort

/**
     * sort A in nondecreasing order
     * 
     * 
@param A
     *            The array to sorted
     
*/

    
public static void sort(int[] A) {
            sort(A, 
0, A.length - 1);
        }


    
public static void sort(int[] A, int p, int r) {
        
for (int j = p + 1; j <= r; j++{
                 
int key = A[j];
                 
// Insert A[j] into the sorted sequence A[0 .. j-1]
                  int i = j - 1;
             
while (i >= p && A[i] > key) {
                        A[i 
+ 1= A[i];
                        i 
= i - 1;
                  }

                 A[i 
+ 1= key;
            }

       }

Merge-Sort

/**
     * Sort A[p .. r] with Merge Sort
     
*/

  public static
 void mergeSort(int[] A, int p, int r) {
        
if (p < r) 
{
                 
int q = (p + r) / 
2;
                  mergeSort(A, p, q);
                  mergeSort(A, q 
+ 
1, r);
                  merge(A, p, q, r);
            }

      }

merge函数

/**
     * merge sorted A[p .. q] and A[q+1 .. r] into A[p .. r]
     
*/

    
private static void merge(int[] A, int p, int q, int r) 
{
             
int[] L = new int[q - p + 1
];
             
int[] R = new int[r -
 q];
         
for (int i = 0; i < L.length; i++
{
                    L[i] 
= A[p +
 i];
             }

         
for (int j = 0; j < R.length; j++{
                   R[j] 
= A[q + 1 +
 j];
             }

        
             
int i = 0;
            
int j = 0
;
            
int k =
 p;
        
while (i < L.length && j < R.length) 
{
             
if (L[i] < R[j]) 
{
                      A[k
++= L[i++
];
              }
 else {
                      A[k
++= R[j++
];
                 }

            }

         
while (i < L.length) {
                 A[k
++= L[i++
];
             }

        
while (j < R.length) {
                A[k
++= R[j++
];
            }

     }


复杂度分析

最差情况下Insertion-Sort的复杂度是O(n2), 而Merge-Sort是O(nlgn)。就是说Merge-Sort比Insertion-Sort好了一个n对lgn的程度,相差大吗?当然是n越大,Merge-Sort相比于Insertion-Sort的优势越明显。有多明显呢?做个实验看看,将一百万个整数排序。在我的电脑上,Merge-Sort用了731 ms,而Insertion-Sort跑了5分钟还没出来,就不等了,没这个耐心。不过可以估算大概需要多长时间。Insertion-Sort排10000个整数所需的时间
T(10000)=191 ms,假设T(n) = cn^2.


约需32分钟,如果你有兴趣可以在你的电脑上试试看,所有的源代码和测试程序可以在下面下载。

Insertion-Sort和Merge-Sort的结合

虽然Insertion-Sort是平方级的复杂度,而Merge-Sort是nlgn级的复杂度,但是当n比较小的时候,Insertion-Sort反而要快一些,因为复杂度分析是一种增长级速的分析,对大的输入情况才有意义。既然n小的时候,Insertion-Sort比Merge-Sort要快,那么一个改善Merge-Sort的方法就呼之欲出了。当divide(回归调用)到一定程度的时候,即元素个数小于某个值K的时候,用Insertion-Sort排序。这种算法可以称作Insertion-Merge-Sort.

Insertion-Merge-Sort的Java实现

    public static void sort(int[] A) {
            mergeSort(A, 
0, A.length - 1);
       }


    
private static void mergeSort(int[] A, int p, int r) {
        
if (r - p + 1 <= K) {
                 InsertionSort.sort(A, p, r);
        }
 else {
               
int q = (p + r) / 2;
                mergeSort(A, p, q);
                mergeSort(A, q 
+ 1, r);
                merge(A, p, q, r);
          }

       }


    
private static void merge(int[] A, int p, int q, int r) {
            
int n1 = q - p + 1;
           
int n2 = r - q;
           
int[] L = new int[n1 + 1];
           
int[] R = new int[n2 + 1];
        
for (int i = 0; i < n1; i++{
               L[i] 
= A[p + i];
           }

           L[n1] 
= Integer.MAX_VALUE; // put the sentinel
        for (int j = 0; j < n2; j++{
              R[j] 
= A[q + 1 + j];
            }

           R[n2] 
= Integer.MAX_VALUE;
          
int i = 0;
          
int j = 0;
       
for (int k = p; k <= r; k++{
            
if (L[i] < R[j]) {
                     A[k] 
= L[i];
                     i 
= i + 1;
            }
 else {
                    A[k] 
= R[j];
                    j 
= j + 1;
                }

           }

    }

Insertion-Merge-Sort比Merge-Sort快多少? 用Insertion-Merge-Sort对一百万个整数排序需要大约541ms. 相比于Merge-Sort的731ms,快了将近26%.

Insertion-Merge-Sort的复杂度分析

假设当输入个数为K时,采用Insertion-Sort, 那么有n/K个小组要用Insertion-Sort,所需时间为,
n/K * K2=nK, 将n/K个小组组合起来,所需的时间是n*lg(n/K), 那么加起来就是Insertion-Merge-Sort的复杂度O(nK + nlg(n/K)).

还有一个问题,某个值K应该取多大才算是最合适呢? 

当K=1时,Insertion-Merge-Sort就成了Merge-Sort, 当K=n时,Insertion-Merge-Sort就成了Insertion-Sort。理论上,K的取值不应该使得Insertion-Merge-Sort的复杂度高于Merge-Sort的复杂度即O(nlgn), 如果按这个要求推理,那么K应该属于O(lgn)。 在实践中,K可以取所有Insertion-Sort还比Merge-Sort快的最大值。但是在不同的计算环境和不同的输入下,这个值也会不一样。我们只能根据实验的情况取一个多数情况下比较好的K值。Java的Arrays.sort(.)函数取的是7,你可以看JDK的源代码。好像Java的Arrays类以前用的是Quick-Sort算法, 不知道什么时候换成Insertion-Merge-Sort了。

本文所有源代码

注脚
以上所有的复杂度实际上即是上限,也是下限,习惯上应该用Theta表示,而O一般只表示一个上限,由于Theta不好打,只好这样了,而且O的知名度要高很多,也被人滥用了很多。具体参照Knuth的论文Big Omicron and big Omega and big Theta


转载请保留http://www.blogjava.net/xilaile/archive/2007/04/29/114453.html


posted on 2007-04-28 22:36 gr8vyguy 阅读(3748) 评论(2)  编辑  收藏 所属分类: 计算机科学基础

评论

# re: Insertion-Sort和Merge-Sort 2007-05-06 07:45 InPractice

JDK中既有快速排序,也有merge-insertation 排序。
前者基本上用于 primitive 的排序。
后者基本上用于对象数数组的排序。  回复  更多评论   

# re: Insertion-Sort和Merge-Sort 2007-05-06 23:17 Pande

@InPractice
你说对,的确是如此,JDK的QuickSort也是用InsertionSort优化过的  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
<2007年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

公告

  • 转载请注明出处.
  • msn: gr8vyguy at live.com
  • 常用链接

    留言簿(9)

    随笔分类(68)

    随笔档案(80)

    文章分类(1)

    My Open Source Projects

    搜索

    积分与排名

    最新评论