[关闭]
@BIGBALLON 2015-08-01T16:17:17.000000Z 字数 10746 阅读 1447

排序算法小结

本博文诞生原因

前几天有同学找我要排序算法的代码，说实话我已经有几百万年没写过排序了。
电脑里找了一下发现代码都不见了，留下的也都是丑得一B的代码，不忍直视。。
冒泡，选择这样的东西自从开始用sort之后就几百年没用过了。
另外这个博客仅仅用于我自己整理我自己的排序算法代码。
至于找工作什么的要强行加上 函数返回值 和 assert。。就自己就加上吧。
现在也就这水平了，只能写写排序了，splay、 sbtree什么的早就写不出来了。。。
如果有巨巨看到我的这篇博文别喷我。毕竟半退役ACM弱渣。。。

直接插入排序

直接插入排序，属于最基本的插入排序。
基本思想就如同打扑克抓牌：

  1. 时间复杂度：
    很容易看出插入操作需要进行 n−1 次。
    对于最好情况，也就是序列本身有序，如我们抓牌的顺序是 {1，2，3，4，5}
    我们共比较了 (n−1)次，且没有交换次数，故时间复杂度为 O(n)
    对于最好情况，也就是序列本身逆序，如我们抓牌的顺序是 {5，4，3，2，1}
    此时比较次数为
    ∑i=2n(i−1)=1+2+3+⋯+n−1=(n−1)n2

    交换次数为(n−1)n2
    所以总的时间复杂度约为 O(n2)
  2. 空间复杂度:
    O(1) 就不多废话了
  3. 稳定性：
    直接插入排序是稳定的。逐个元素依次插入，相等元素的前后顺序是不会改变的，所以显然是稳定的。
  1. void insert_sort( int arr[], int sz ){
  2.     int i , j , val;
  4.     for( i = 1; i < sz; ++i ){
  5.         val = arr[ i ];
  6.         j = i - 1;
  7.         while( j >= 0 && arr[j] > val ){
  8.             arr[ j + 1 ] = arr[ j ];
  9.             --j;
  10.         }
  11.         arr[ j + 1 ] = val;
  12.     }
  13. }

折半插入排序

很明显可以看到，，直接插入排序慢的要死（在一般情况下）。
故有人对它进行优化。。（其实并没有什么卵用）
直接插入排序中我们在确定插入位置的时候是逐个数进行比较。
这里就进行了一点优化，用二分进行快速(O(logn2))定位
（如果你还不会写二分那你可以去撞墙了）。

  1. 时间复杂度：
    无奈在元素的交换还是耗费了大量时间，平均的时间复杂度显然还是 O(n2)
    事实上，因为二分的缘故，，，最优情况退化为O(nlogn2)
  2. 空间复杂度：
    O(1) ，也不多废话了
  3. 稳定性：
    直接插入排序是稳定的，，那显然折半插入也是稳定的，，不要问我为什么。。
  1. void b_insert_sort( int arr[], int sz ){
  2.     int i, j, val, low, high, mid;
  4.     for( i = 1; i < sz; ++i ){
  5.         low = 0, high = i - 1;
  6.         val = arr[ i ];
  7.         while( low <= high ){
  8.             mid = ( low + high ) >> 1; 
  9.             if( val > arr[ mid ] ){
  10.                 low = mid + 1;
  11.             }else {
  12.                 high = mid - 1;
  13.             }
  14.         }
  15.         for( j = i; j > low; --j ){
  16.             arr[ j ] = arr[ j - 1 ];
  17.         }
  18.         arr[ low ] = val;
  19.     }
  20. }

二-路插入排序

我引用网络上好多博客都写的一句话：

2-路插入排序是在折半插入排序的基础上再改进之

好一个在折半插入排序的基础上再改进。。也不知道是那些博主抄来抄去还是怎么回事。
写个烂代码根本就没有折半插入，，，还强行说自己在写“2-路插入排序”，文不对题也是NB，更猛的是下面还一群人评论，写得好，，，哪里写得好了？明显误人子弟。。要么就写清楚自己的代码是基于折半插入排序的2路插入排序还是基于直接插入排序的2路插入排序。
强行加一句文不对题的话是真的理解还是？？？

看了这篇 博客 写得好，起码还有点复杂度分析，，其他那些代码是不是抄来的都不知道，复杂度分析估计博主压根不会。

2-路插入排序需要一个辅助数组，并且这个数组是一个环状数组（循环数组）

  1. 时间复杂度：
    虽然用了二分可以将比较的时间降为 (O(logn2))
    但是我们计算数据交换的次数为 n28,所以时间复杂度还是 O(n2)
    具体计算，有 12 的数据不需要交换位置。
    剩下12 的数据每次移动交换 n2\*n2
    如果从最坏情况考虑。。还是会退化到 O(n2)
  2. 空间复杂度：
    O(n) ，需要有一个辅助数组用来存放数据
  3. 稳定性：
    稳定的。
  4. 关于取模：
    有人说这个算法的精髓在于取模，，我说如果取模都没有这个算法还搞个P，其实取模操作的耗时也是很长的，，这点在搞数论的时候深有体会。
  1. //基于折半插入排序的2路插入排序
  2. void tp_insert_sort( int arr[], int sz ){
  3.     int* d = new int[ sz ];
  4.     d[ 0 ] = arr[ 0 ];
  5.     int final, first, val, i, j;
  6.     final = first = val = 0;
  8.     for( i = 1; i < sz; ++i ){
  9.         val = arr[i];
  10.         if( val < d[ first ] ){
  11.             first = ( first - 1 + sz ) % sz;
  12.             d[ first ] = val;
  13.         } else if( val > d[ final ] ){
  14.             final = ( final + 1 + sz ) % sz;
  15.             d[ final ] = val;
  16.         } else{
  17.             int low = 0, high = ( final - first + sz ) % sz;
  18.             int end = high;
  19.             while( low <= high ){
  20.                 int mid = ( low + high ) >> 1;
  21.                 if( val < d[ ( mid + first ) % sz ] ){
  22.                     high = mid - 1; 
  23.                 }else{
  24.                     low = mid + 1;
  25.                 } 
  26.             }
  27.             for( j = end; j >= high + 1; --j ){
  28.                 d[ ( j + first + 1 ) % sz ] = d[ ( j + first ) % sz ];
  29.             }
  30.             d[ ( high + first + 1 ) % sz ] = val;
  31.             final = ( final + 1 + sz ) % sz;
  32.         }
  33.     }
  35.     for( i = 0; i < sz; ++i ){
  36.         arr[i] = d[ ( i + first ) % sz ];
  37.     }
  38.     delete [] d;
  39. }
  42. //直接插入排序的2路插入排序
  43. void t_insert_sort( int arr[], int sz ){
  44.     int* d = new int[ sz ];
  45.     d[ 0 ] = arr[ 0 ];
  46.     int final, first, val, i, j;
  47.     final = first = val = 0;
  49.     for( i = 1; i < sz; ++i ){
  50.         val = arr[i];
  51.         if( val < d[ first ] ){
  52.             first = ( first - 1 + sz ) % sz;
  53.             d[ first ] = val;
  54.         } else if( val > d[ final ] ){
  55.             final = ( final + 1 + sz ) % sz;
  56.             d[ final ] = val;
  57.         } else{
  58.             int pos = ( final + 1 + sz ) % sz;
  59.             while(  val < d[ ( pos - 1 + sz ) % sz ] ){
  60.                 d[ ( pos + sz ) % sz ] = d[ ( pos - 1 + sz) % sz ];
  61.                 pos = ( pos - 1 + sz ) % sz;
  62.             }
  63.             d[ ( pos + sz ) % sz ] = val;
  64.             final = ( final + 1 + sz ) % sz;
  65.         }
  66.     }
  68.     for( i = 0; i < sz; ++i ){
  69.         arr[i] = d[ ( i + first ) % sz ];
  70.     }
  71.     delete [] d;
  72. }

表插入排序

这东西没什么用，，就不说了。其实是我不会。。。。

  1. #define SIZE 100
  2. #define MAX 0x7fffffff
  3. typedef struct{
  4.     int val;
  5.     int next;
  6. }SLNode,*PSLNode; 
  7. typedef struct{
  8.     SLNode num[ SIZE ];
  9.     int len;
  10. }SLinkList, *PSLinkList;
  12. int init_link( PSLinkList Slist, int arr[], int sz ){
  13.     if( sz >= SIZE ){
  14.         return 0;
  15.     }
  16.     Slist->num[0].val = MAX;
  17.     Slist->num[0].next = 1;
  18.     for( int i = 1; i <= sz; ++i ){
  20.         Slist->num[i].val = arr[ i - 1 ];
  21.         Slist->num[i].next = 0;
  22.     }
  23.     Slist->len = sz + 1;
  24.     return 1;
  25. }
  27. int table_sort( PSLinkList Slist ){
  28.     int len = Slist->len;
  29.     for( int i = 2; i < len; ++i ){
  30.         int idx = 0;
  31.         int pos = Slist->num[0].next;
  32.         while( Slist->num[i].val > Slist->num[pos].val ){
  33.             idx = pos;
  34.             pos = Slist->num[pos].next;
  35.         }
  36.         Slist->num[i].next = pos;
  37.         Slist->num[idx].next = i;
  38.     }
  39.     return 1;
  40. }
  42. int arrange( PSLinkList Slist ){
  43.     int i, idx, pos;
  44.     pos = Slist->num[0].next;
  45.     for( i = 1; i < Slist->len; ++i ){
  46.         while( pos < i ){
  47.             pos = Slist->num[pos].next;
  48.         }
  49.         idx = Slist->num[pos].next;
  50.         if( pos != i ){
  51.             std::swap( Slist->num[pos], Slist->num[i] );
  52.             Slist->num[i].next = pos;
  53.         }
  54.         pos = idx;
  55.     }
  56. }

希尔排序

其实shell排序很简单，就是将原数组分成若干个子序列，
对每个子序列分别使用直接插入排序。
最后再对全体元素进行一次直接插入排序。
实际上这里就是有一个叫做 步长 的东西。

  1. 时间复杂度：
    时间是和所取“增量”序列的函数密切相关，通常取的步长可以是原数组的一半，
    然后不断减小直到1为止。
    平均情况下为 O(nlogn2) ---- 注意这里我选择的步长是不断除以2
    其实我不会计算 shellsort 的时间复杂度，原谅我，我太笨了
  2. 空间复杂度：
    O(1)
  3. 稳定性：
    不稳定。为什么不稳定？可以这样考虑，因为对数组进行了“分组”，存在相等元素位置发生改变的情况。
  1. void shell_sort( int arr[], int sz ){
  2.     int i, j, d, val;   
  4.     d = sz >> 1;
  5.     while( d >= 1 ){
  6.         for( i = d; i < sz; ++i ){
  7.             j = i - d;
  8.             val = arr[i];
  9.             while( j >= 0 && arr[j] > val ){
  10.                 arr[ j + d ] = arr[ j ];
  11.                 j -= d;
  12.             }
  13.             if( j != i - d ){
  14.                 arr[ j + d ] = val;
  15.             }
  16.         }   
  17.         d >>= 1;    
  18.     }
  19. }

基本选择排序

  1. 时间复杂度：
    这个东西真的很慢，最近一次写这个排序估计要追溯到大一了。。
    算法总共会进行 (n−1) 次扫描，每次扫描会进行 (n−2) 次比较
    那么时间复杂度自然是 (n−1)\*(n−2)=O(n2)
  2. 空间复杂度：
    O(1)
  3. 稳定性：
    不稳定，可能导致相等元素相对位置发生改变。
  1. void select_sort( int arr[], int sz ){
  2.     int i, j, pos;
  4.     for( i = 0; i < sz - 1; ++i ){
  5.         pos = i;
  6.         for( j = i + 1; j < sz; ++j ){
  7.             if( arr[pos] > arr[j] ){
  8.                 pos = j;
  9.             }
  10.         }
  11.         if( pos != i ) {
  12.             std::swap( arr[pos], arr[i] );  
  13.         }
  14.     }
  15. }

树形选择排序

这玩意又叫做“锦标赛排序”，确实很像，就是淘汰赛咯。
我们可以将数组看成是一颗满二叉树的叶子节点（不能够成满二叉树就补全）。
具体算法执行步骤我简要写一下吧，如果看不懂不要打我就是了。

  1. 建树，用数组实现的话，树根为0号单元，建树的时候从尾往前建树
  2. 取得最小值，然后将最小值对应的叶子节点标记为MAXX，向上更新直到树根，得到次小值
  3. 取得次小值，然后将最小值对应的叶子节点标记为MAXX，向上更新直到树根，得到次次小值
  4. 如此反复知道排序完毕

如果你不知道我再说什么我找了一个 PPT

  1. 时间复杂度：
    由数组构造树需要O(n+n)
    选择最小关键字耗时O(1)，以后每次选择一个次小关键字需要消耗O(logn2)
    总的时间复杂度 O(2n+1+(n−1)logn2) = O(nlogn2)
  2. 空间复杂度：
    O(2n) 辅助空间比较多，且需要进行对此多余的比较
  3. 稳定性：
    它是稳定的，如果不能理解可以举一些特例，最后会发现它并不会改变相等元素的相对位置。
  1. #define MAXX 0x7fffffff;    //int max
  3. void tree_select_sort( int arr[], int sz ){
  5.     int len, i, j, idx, cnt, minn;
  6.     len = ( sz << 1 ) - 1;
  7.     int* tree = new int[ len ];
  9.     //精髓所在，由后往前填充，且后面的处理也是从后往前，并且是-2    
  10.     //如果是构造数据结构的话，需要进行节点补充。 
  11.     for( i = sz - 1, j = 0; i >= 0; --i, ++j ){
  12.         tree[ len - 1 - j ] = arr[ i ];
  13.     }
  15.     for( i = len - 1; i > 0; i -= 2 ){
  16.         int pos = ( i - 1 ) >> 1;
  17.         if( tree[ i - 1 ] < tree[ i ] ){
  18.             tree[ pos ] = tree[ i - 1 ];    
  19.         }else{
  20.             tree[ pos ] = tree[ i ];    
  21.         }
  22.     }
  23.     cnt = 0;
  24.     while( cnt < sz ){
  25.         minn = tree[ 0 ];
  26.         arr[ cnt++ ] = minn;
  27.         idx = len - 1;
  28.         while( tree[ idx ] != minn ){
  29.             --idx;
  30.         }
  31.         tree[ idx ] = MAXX;
  32.         while( idx > 0 ){
  33.             if( idx & 1 ){
  34.                 tree[ idx >> 1 ] = tree[ idx ] < tree[ idx + 1 ] ? tree[ idx ] : tree[ idx + 1 ];
  35.                 idx = idx >> 1;
  36.             }else{
  37.                 tree[ ( idx - 1 ) >> 1 ] = tree[ idx - 1 ] < tree[ idx ] ? tree[ idx - 1 ] : tree[ idx ];
  38.                 idx = ( idx - 1 ) >> 1;
  39.             }
  40.         } 
  41.     }
  42.     delete [] tree;
  43. }

堆排序

这里的堆值的是二叉堆，他其实是遵循一定规律的数组。
最大堆：所有节点的子节点比其自身小的堆。
最小堆：所有节点的子节点比其自身大的堆。

  1. 时间复杂度：
    由数组构建堆的时间复杂度其实并不是 O(nlogn2)
    更精确的应该是线性的(2n−2−logn2)=O(n)
    排序过程中，每次重新调整最大堆需要logn2的时间，总共有n个元素，需要调整n−1次，耗时 O((n−1)logn2)
    总耗时 2n−2−logn2+(n−1)logn2=O(nlogn2)
    具体的证明看 《算法导论》 或者 这个 blog
  2. 空间复杂度：
    O(1)
  3. 稳定性：
    不稳定
  2. void max_heapify( int arr[], int i, int sz ){
  3.     int lt = ( i << 1 ) + 1, rt = ( i << 1 ) + 2;
  4.     int lar = 0;
  6.     if( lt < sz && arr[ lt ] > arr[ i ] ){
  7.         lar = lt;
  8.     }else{
  9.         lar = i;
  10.     }
  11.     if( rt < sz && arr[ rt ] > arr[ lar ] ){
  12.         lar = rt;
  13.     }
  14.     if( lar != i ){
  15.         std::swap( arr[ i ], arr[ lar ] );
  16.         max_heapify( arr, lar, sz );
  17.     }
  18. } 
  19. void build_maxheap( int arr[], int sz ){
  20.     for( int i = sz >> 1; i >= 0; --i ){
  21.         max_heapify( arr, i, sz );
  22.     }
  23. }
  25. void heap_sort( int arr[], int sz ){
  26.     build_maxheap( arr, sz );
  27.     int len = sz - 1;
  28.     while( len >= 1 ){
  29.         std::swap( arr[ 0 ], arr[ len ] );
  30.         --len;
  31.         max_heapify( arr, 0, len );
  32.     }
  33. }

冒泡排序

冒泡排序没什么说的，基本没用。。

  1. 时间复杂度：
    最原始的冒泡排序的时间复杂度是O(n2),最好情况也是O(n2)
    改进之后（加入了flag标记），最优情况可以优化为O(n)
    总之，平局情况算法的时间复杂度为O(n2)，一般情况也不会用冒泡排序。。。
  2. 空间复杂度：
    O(1)
  3. 稳定性：
    临位交换必然是稳定排序。
  1. void bubble_sort2( int arr[], int sz ){
  2.     int i, j, flag;
  3.     for( i = 0; i < sz; ++i ){
  4.         flag = 0;
  5.         for( j = 1; j < sz - i; ++j ){
  6.             if( arr[ j - 1 ] > arr[ j ] ){
  7.                 std::swap( arr[ j ], arr[ j - 1 ] ); 
  8.                 flag = 1;
  9.             } 
  10.         }
  11.         if( flag == 0 ){
  12.             break;
  13.         }
  14.     }
  15. }
  17. void bubble_sort( int arr[], int sz ){
  18.     for( int i = 0; i < sz - 1; ++i ){
  19.         for( int j = sz - 1; j > i; --j ){
  20.             if( arr[ j - 1 ] > arr[ j] ){
  21.                 std::swap( arr[ j ], arr[ j - 1 ] ); 
  22.             }
  23.         }
  24.     }
  25. }

快速排序

快速排序是对冒泡排序的一种改进，运用的是递归的思想
具体步骤如下：
1. 定基准：从数列中跳出一个元素，作为基准"pivot"（这个基准其实还是很重要的，可直接规定，也可以使用随机化）
2. 分区操作：对数列进行重新排序，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
3. 自顶向下递归调用

  1. 时间复杂度：
    我只记得原来看算法导论的时候书上写了好几页，用来分析时间复杂度的，，，简单理解的话就是，总共会有logn2次递归，每次进行 n的比较，大概来说是 O(nlogn2)
    最坏情况下时间复杂度会退化为O(n2)，但是在一般情况下，快速排序是相当优秀的，不然怎么能叫做快速排序呢？
    详细严谨的证明最理想的就是回去翻算法导论了。我就不BB了
  2. 空间复杂度：
    平均情况需要O(logn2)的栈空间,
    最坏情况下会退化到O(n)的栈空间,
  3. 稳定性：
    不稳定

霍尔快排

我原来学快排的时候在想为什么叫做霍尔快排。。
当然这是废话，因为快排这个鬼东西是霍尔发明的。
霍尔快排取数列中的第一个数为基准，
从尾向头扫描，遇到比基准小的数则将其和low位置交换（尽量让它往左边交换）
从尾向头扫描，遇到比基准大的数则将其和high位置交换（尽量让它往右边交换）
最后将基准放到中间去，这样就完成了将比基准小的数放在它左边，将比基准的的数放在它右边的操作了。

  1. int partition( int arr[], int lt, int rt ){
  2.     int low = lt, high = rt;
  3.     int val = arr[ lt ];
  4.     while( low < high ){
  5.         while( low < high && arr[ high ] >= val ){
  6.             --high;
  7.         }
  8.         arr[ low ] = arr[ high ];
  9.         while( low < high && arr[ low ] <= val ){
  10.             ++low;
  11.         }
  12.         arr[ high ] = arr[ low ];
  13.     } 
  14.     arr[ low ] = val;
  15.     return low;
  16. }
  18. void quick_sort( int arr[], int lt, int rt ){
  19.     if( lt < rt ){
  20.         int pivot = partition( arr, lt, rt );
  21.         quick_sort( arr, lt, pivot - 1 );
  22.         quick_sort( arr, pivot + 1, rt );
  23.     }
  24. }

算法导论上的快排

我原来一开始用的是这个快排。
当然现在变成XX了，都不会写了。

  1. int partition( int arr[], int lt, int rt ){
  2.     int val = arr[ rt ];
  3.     int i = lt - 1, j;
  5.     for( j = lt; j <= rt - 1; ++j ){
  6.         if( arr[j] <= val ){
  7.             ++i;
  8.             std::swap( arr[ i ], arr[j] );
  9.         }
  10.     }
  11.     std::swap( arr[ i + 1 ], arr[ rt ] );
  12.     return i + 1;   
  13. }
  15. void quick_sort( int arr[], int lt, int rt ){
  16.     if( lt < rt ){
  17.         int pivot = partition( arr, lt, rt );
  18.         quick_sort( arr, lt, pivot - 1 );
  19.         quick_sort( arr, pivot + 1, rt );
  20.     }
  21. }

随机化快排

随机化其实就是加了一个随即选择基准，代码什么的基本一样的。

我曾经用的快排

最初这个写法是在上海交大的某个模板上学来的。
当时觉得好短好强悍！而且这个代码很好理解！！

  1. void quick_sort( int arr[], int beg, int end ){
  2.     int i = beg, j = end, x= arr[ ( beg + end ) / 2 ];
  3.     do{
  4.         while( arr[ i ] < x ) ++i;
  5.         while( arr[ j ] > x ) --j;
  6.         if( i <= j ) std::swap( arr[ i++ ], arr[ j-- ] ); 
  7.     }while( i < j );
  8.     if( i < end ) quick_sort( arr, i, end );
  9.     if( j > beg ) quick_sort( arr, beg, j );    
  10. }

快排的优化

快排的优化相当多，，很多我不会。。就不误人子弟乱写了。
好像有什么三平均分区法，并行快排什么的，，不懂。

归并排序

自顶向下的归并排序

这种归并排序是用递归实现的，也是我们最常写的归并排序。
但是显然递归会增加额外的开销，但是迭代能省下这些开销而且迭代的效率要高一些。

递归过程，将待排序的数组一分为二，
将子数组一分为二。
将子数组一分为二。。。
直到待排序的子数组只剩下一个元素为止，然后不断合并两个子数组。

  1. 时间复杂度：
    最原始的冒泡排序的时间复杂度是O(nlogn2)
  2. 空间复杂度：
    简单理解为O(n)
    实际上归并排序的空间复杂度应该是O(logn2+n)，所以还是O(n)
  3. 稳定性：
    必须稳定啊。
  1. void merge_arr( int arr[], int lt, int mi, int rt, int d[] ){
  2.     int i = lt, j = mi + 1, k = 0;;
  3.     while( i <= mi && j <= rt ){
  4.         if( arr[i] <= arr[j] ){
  5.             d[ k++ ] = arr[ i++ ];
  6.         }else{
  7.             d[ k++ ] = arr[ j++ ];
  8.         }
  9.     }
  10.     while( i <= mi ){
  11.         d[ k++ ] = arr[ i++ ];
  12.     }
  13.     while( j <= rt ){
  14.         d[ k++ ] = arr[ j++ ];
  15.     }
  16.     for( i = 0; i < k; ++i ){
  17.         arr[ lt + i ] = d[ i ];
  18.     }
  19. }
  21. void merge( int arr[], int lt, int rt, int d[] ){
  23.     if( lt < rt ){
  24.         int mid = ( lt + rt ) >> 1;
  25.         merge( arr, lt, mid, d );
  26.         merge( arr, mid + 1, rt, d );
  27.         merge_arr( arr, lt, mid, rt, d );
  28.     }   
  29. }
  31. int merge_sort( int arr[], int sz ){
  32.     int *d = new int[ sz ];
  34.     if( d == NULL ){
  35.         return 0;
  36.     }
  37.     merge( arr, 0, sz - 1, d );
  38.     delete []d;
  39.     return 1;
  40. }

自底向上的归并排序

这种排序实际上就把递归改为迭代。
但是明显迭代是优越的。
这个迭代我在大三之前只写过一次。。惭愧。
迭代的思想：
将数组中相邻元素两两配对，将它们变为有序。
这样会构成 n/2 组长度为 2 的已排序子数组段。
然后再将相邻的长度为2的子数组段两两配对，
排序之后变为 n/4组长度为 4 的已排序子数组段。
如此反复（其实就是不断增大步长）
直到整个数组有序即可。

  1. 原数组（排序前）：112 2 44 33 13 44 42 0 0 444 555 235253 0 228 92 300 8 235 2
  2. 第一次（步长1） ：2 112 33 44 13 44 0 42 0 444 555 235253 0 228 92 300 8 235 2
  3. 第二次（步长2） ：2 33 44 112 0 13 42 44 0 444 555 235253 0 92 228 300 2 8 235
  4. 第二次（步长4） ：0 2 13 33 42 44 44 112 0 0 92 228 300 444 555 235253 2 8 235
  5. 第二次（步长8） ：0 0 0 2 13 33 42 44 44 92 112 228 300 444 555 235253 2 8 235
  6. 第二次（步长16）：0 0 0 2 2 8 13 33 42 44 44 92 112 228 235 300 444 555 235253
  1. int it_merge_sort( int arr[], int sz ){
  2.     int i, lt_min, rt_min, lt_max, rt_max, next;
  3.     int *d = new int[ sz ];
  4.     if( d == NULL ){
  5.         return 0;
  6.     }
  7.     for( i = 1; i < sz; i *= 2 ){
  8.         for( lt_min = 0; lt_min < sz - i; lt_min = rt_max ){
  9.             rt_min = lt_max = lt_min + i;
  10.             rt_max = lt_max + i;
  11.             if( rt_max > sz ){
  12.                 rt_max = sz;
  13.             }
  14.             next = 0;
  15.             while( lt_min < lt_max && rt_min < rt_max ){
  16.                 d[ next++ ] = arr[ lt_min ] < arr[ rt_min ] ? arr[ lt_min++ ] : arr[ rt_min++ ];
  17.             }
  18.             while( lt_min < lt_max ){
  19.                 arr[ --rt_min ] = arr[ --lt_max ];
  20.             }
  21.             while( next > 0 ){
  22.                 arr[ --rt_min ] = d[ --next ];
  23.             }
  24.         }
  25.     }
  26.     delete []d;
  27. }

写在后面

如果你能看到这里，，真的很感谢你，我写得这么烂的这篇博客我自己都目不忍视了。
另外，想说明几点。
要找资料，推荐去wiki，不要上百度，，百度百科里面的东西都是老掉牙的，几乎都是从wiki搬过来的。
而且wiki的更新比较快，特别是英文版的页面。
wiki的末尾还会提供非常多的论文和参考文献，非常好
所以想详细了解最好去wiki。
还有就是去阅读一些专业的参考书籍（例如算法导论之类的）。
一般的数据结构书写得太简单，太草率，证明什么的更是完全没有。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注