1 #include <stdio.h>      2 #include <string.h>  3 #include <ctype.h>        4 #include <stdlib.h>     5 #include <io.h>    6 #include <math.h>    7 #include <time.h>  8   9 #define OK        1 10 #define ERROR    0 11 #define TRUE    1 12 #define FALSE    0 13  14 #define MAX_LENGTH_INSERT_SORT 7 /* 用于快速排序时判断是否选用插入排序阙值 */ 15  16 typedef int Status;  17  18 #define MAXSIZE 10000  /* 用于要排序数组个数最大值，可根据需要修改 */ 19 typedef struct 20 { 21     int r[MAXSIZE+1];    /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */ 22     int length;            /* 用于记录顺序表的长度 */ 23 }SqList; 24  25 /* 交换L中数组r的下标为i和j的值 */ 26 void swap(SqList *L,int i,int j)  27 {  28     int temp=L->r[i];  29     L->r[i]=L->r[j];  30     L->r[j]=temp;  31 } 32  33 void print(SqList L) 34 { 35     int i; 36     for(i=1;i<L.length;i++) 37         printf("%d,",L.r[i]); 38  39     printf("%d",L.r[i]); 40     printf("\n"); 41 } 42  43 /* 对顺序表L作交换排序（冒泡排序初级版） */ 44 void BubbleSort0(SqList *L) 45 {  46     for( int i=1; i<L->length; i++) 47     { 48         for( int j=i+1; j<=L->length; j++) 49         { 50             if(L->r[i]>L->r[j]) 51             { 52                  swap(L,i,j);        /* 交换L->r[i]与L->r[j]的值 */ 53             } 54         } 55     } 56 } 57  58 /* 对顺序表L作冒泡排序 */ 59 void BubbleSort(SqList *L) 60 {  61     for(int i=1;i<L->length;i++) 62     { 63         for(int j=L->length-1;j>=i;j--) /* 注意j是从后往前循环 */ 64         { 65             if(L->r[j]>L->r[j+1])        /* 若前者大于后者（注意这里与上一算法的差异）*/ 66             { 67                  swap(L,j,j+1);            /* 交换L->r[j]与L->r[j+1]的值 */ 68             } 69         } 70     } 71 } 72  73 /* 对顺序表L作改进冒泡算法 */ 74 void BubbleSort2(SqList *L) 75 {  76     Status flag = TRUE;            /* flag用来作为标记 */ 77     for( int i=1; i<L->length && flag; i++) /* 若flag为true说明有过数据交换，否则停止循环 */ 78     { 79         flag = FALSE;                /* 初始为False */ 80         for(int j=L->length-1; j>=i; j--) 81         { 82             if(L->r[j] > L->r[j+1]) 83             { 84                  swap(L, j, j+1);    /* 交换L->r[j]与L->r[j+1]的值 */ 85                  flag = TRUE;        /* 如果有数据交换，则flag为true */ 86             } 87         } 88     } 89 } 90  91 // 双向冒泡法 92 void Bubble_2 ( int r[], int n) 93 {   94     int low = 0;    95     int high = n-1; //设置变量的初始值   96     int tmp,j; 97  98     while (low < high)  99     {  100         for (j = low; j< high; ++j)    // 正向冒泡,找到最大者  101             if (r[j] > r[j+1]) 102             {  103                 tmp = r[j]; r[j] = r[j+1]; r[j+1] = tmp;  104             }   105         --high;            // 修改high值, 前移一位  106         for ( j = high; j > low; --j)    // 反向冒泡,找到最小者  107             if (r[j] < r[j-1]) 108             {  109                 tmp = r[j]; r[j] = r[j-1]; r[j-1] = tmp;  110             }  111         ++low;            // 修改low值,后移一位  112     }   113 } 114 115 /*116 多关键码排序方法：117 118 多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：119 120 最高位优先(Most Significant Digit first)法，简称MSD法：121     1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。122     2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。123     3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。124 125 最低位优先(Least Significant Digit first)法，简称LSD法：126     1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。127     2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。128 129 原理：130         按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。131     有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。132     最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。133     基数排序基于分别排序，分别收集，所以是稳定的。134 @param:135     r: 原始数组136     137     // 原理版本138 void RadixSort(int r[], int length, int maxradix )  139 {  140     int k, lsp;  141     k = 1; 142     int n = 0;    // 基数内 序号143     int m = 1;  // 个位、十位144 145     int temp[10][length-1];  146     Empty( temp );    // 清空临时空间  147 148     while( k < maxradix )    // 遍历所有关键字  149     {  150         for(int i=0; i<length; i++) //分配过程  151         {  152             if(r[i] < m)  153                 temp[0][n] = r[i];  154             else  155                 lsp = (r[i]/m) % 10; //确定关键字  156 157             temp[lsp][n] = r[i];  158             n++;  159         } 160 161         CollectElement(r, temp); // 收集  162         n = 0;  163         m = m*10;  164         k++;  165     }  166 } 167  */168     // 得到最大位数169 int maxbit(int data[], int n)170 {171     int nBit = 1;172     for(int i=0; i<n; i++)173     {174         int tempC = 1;175         int p = data[i];176         while( p/10 )177         {178             p = p/10;179             tempC++;180         }181         if( tempC > nBit )182             nBit = tempC;183     }184     return nBit;185 }186 187 void RadixSort(int data[], int n)188 {  189     int* tmp = new int[n];190     int count[10];    // 每一桶中的个数191     int nBit = maxbit(data,n);192     int r=1;193 194     for(int i=0; i<nBit; i++)195     {196             // 装桶之前要先清桶197         for(int i=0;i<10;i++)198             count[i]=0;199 200         for(i=0;i<n;i++)    // 记录每个桶的个数201         {202             int k=data[i]/r;203             int q=k%10;204             count[q]++;205         }206         for(i=1; i<10; i++)    // 计算位置207         {208             count[i] += count[i-1];209         }210         for(int j=n-1; j>=0; j--)211         {212             int p = data[j]/r;213             int s = p%10;214             tmp[count[s]-1] = data[j];215             count[s]--;                216         }217         for(i=0; i<n; i++)218         {219             data[i] = tmp[i];        220         }            221         r = r*10;    // 更高一位222 223     }224 225 }226 227 228 // 计数排序229 void CountSort(int* pData, int n)230 {231     int* pCout = NULL;            // 记数的指针232     int* pSort = NULL;            // 暂存排序结果的指针233     pCout = (int*)malloc(sizeof(int) * n);    // 申请空间234     pSort = (int*)malloc(sizeof(int) * n);   235 236 237         // 初始化记数为0238     for (int i = 0; i < n; ++i)239     {240         pCout[i] = 0;241     }242         // 统计相同元素的个数243     for (int i = 0; i < n; ++i)244     {245         ++pCout[pData[i]];       246     }247         // pCout[i]中是 <= i 的元素个数248     for (int i = 1; i < n; ++i)249     {250         pCout[i] += pCout[i-1];    251     }252     for (int i = 0; i < n; ++i)253     {254         pSort[pCout[pData[i]]] = pData[i];    // 把每一个元素放在数组中相应的位置；因为pCout[pData[i]]的值就是不比他大数据的个数；      255         pCout[pData[i]]--;                    // 如果有相同数据的元素先减1256     }257         // 排序结束，复制到原来数组中258     for (int i = 0; i < n; ++i)259     {260         pData[i] = pSort[i];261     }262         // 释放申请的空间263     free(pCout);264     free(pSort);265 }266 267 /* 对顺序表L作简单选择排序 */268 void SelectSort(SqList *L)269 {270     int min;271     for( int i=1; i<L->length; i++)272     { 273         min = i;                        /* 将当前下标定义为最小值下标 */274         for ( int j = i+1;j<=L->length;j++)/* 循环之后的数据 */275         {276             if (L->r[min] > L->r[j])    /* 如果有小于当前最小值的关键字 */277                 min = j;                /* 将此关键字的下标赋值给min */278         }279         if(i != min)                    /* 若min不等于i，说明找到最小值，交换 */280             swap(L, i, min);            /* 交换L->r[i]与L->r[min]的值 */281     }282 }283 284 // 简单选择排序的改进   二元选择排序285 void SelectSort(int r[],int n) 286 {  287     int i, j, min, max, tmp;  288     for (i = 1; i <= n/2; i++) 289     {    290             // 做不超过n/2趟选择排序   291         min = i; max = i ;    // 分别记录最大和最小关键字记录位置  292         for (j = i+1; j <= n-i; j++) 293         {  294             if (r[j] > r[max]) 295             {   296                 max = j; 297                 continue;   298             }    299             if (r[j] < r[min]) 300             {   301                 min = j;   302             }     303         }    304 305         tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  // swap(a, min, i-1);306         tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;  // swap(a, max, n-i)307     }   308 } 309 310 /* 对顺序表L作直接插入排序 311 312 插入排序（insert sorting)思想：313 当插入第i个元素时，前面的v[0],v[1],v[2]......v[i-1],已经排好序了.314 这时用v[i]的插入码与 v[i-1],v[i-2],......排序码进行比较，315 找到插入的位置即插入v[i],原来位置上的元素从后向前依次后移。316 317 时间复杂度:  平均比较次数O(n2),平均移动次数 O(n2).318 直接插入排序是一种稳定的排序。元素大部分有序时 效率会更高，这时比较次数和移动次数都会减少。319 320 */321 void InsertSort(SqList *L)322 { 323     int j;324     for( int i=2; i<=L->length; i++)325     {326         if (L->r[i] < L->r[i-1])        /* 需将L->r[i]插入有序子表 */327         {328             L->r[0] = L->r[i];            /* 设置哨兵 */329             for( j=i-1; L->r[j] > L->r[0]; j--)330                 L->r[j+1] = L->r[j];    /* 记录后移 */331 332             L->r[j+1] = L->r[0];        /* 插入到正确位置 */333         }334     }335 }336 337 /* 对顺序表L作希尔排序 338 339 希尔排序（Shell sort）基本思想: 改进的直接插入算法。340 设待排序的元素序列有n个元素，首先取一整数gap（<n）作为间隔，将全部元素分为gap个子序列，341 所有距离为gap的元素 放在同一序列中，在每个子序列中分别进行直接插入排序。342 然后缩小gap，例如gap = gap/2,重复上述的子序列划分与排序工作。343 开始由于gap取值大，每个子序列元素少，排序速度快，待排序后期，344 gap值逐渐变小，子序列元素变多，但由于前面的工作基础，大多数元素已经有序，所以排序速度快。345 346 347 希尔排序是一种不稳定的排序348 */349 void ShellSort(SqList *L)350 {351     int j, k = 0;352     int d = L->length;353     do354     {355         d = d/3 + 1;                /* 增量序列 */356         for(int i=d+1; i<=L->length; i++)357         {358             if (L->r[i] < L->r[i-d])    /*  需将L->r[i]插入有序增量子表 */ 359             { 360                 L->r[0] = L->r[i];        /*  暂存在L->r[0] */361                 for( j = i-d; j>0 && L->r[0]<L->r[j]; j -= d)362                     L->r[j+d]=L->r[j];    /*  记录后移，查找插入位置 */363 364                 L->r[j+d]=L->r[0];        /*  插入 */365             }366         }367         printf("第%d趟排序结果: ",++k);368         print(*L);369     }370     while( d > 1 );371 372 }373 374 375 /*  376 大根堆排序的基本思想： 377 1) 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区; 378 2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，379     由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key; 380 3) 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。 381     然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，382     由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。383 */384 385 /*386  @brief:387      已知L->r[s..len]中记录的关键字除L->r[s]之外均满足堆的定义,388      本函数调整L->r[s]的关键字,使L->r[s..len]成为一个大顶堆389  @param:390     cur: 当前位置 s391     len: 当前状态的最大值392 393 m:当前堆的大小394  */395 void HeapAdjust(SqList *L, int cur, int len)396 { 397     int temp = L->r[cur];398     for(int j = 2*cur; j <= len; j *= 2)// 沿关键字较大的孩子结点向下筛选(大根堆)399     {400         if(j < len && L->r[j] < L->r[j+1])401             ++j;                        // j为关键字中较大的记录的下标402         if(temp >= L->r[j])403             break;                        /* 应插入在位置 cur 上 */404 405         L->r[cur] = L->r[j];406         cur = j;407     }408     L->r[cur] = temp;                    /* 插入 */409 }410 411 /*  对顺序表L进行堆排序 */412 void HeapSort( SqList* L )413 {414     for( int i = L->length/2; i>0; i--)    /*  把L中的r构建成一个大根堆 */415          HeapAdjust(L, i, L->length);416 417     for( int i = L->length; i>1; i--)418     { 419          swap(L, 1, i);                /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */420          HeapAdjust(L, 1, i-1);        /* 将L->r[1..i-1]重新调整为大根堆 */421     }422 }423 424 425 #if 0426 427 428 #include <iostream>429 #include <algorithm>430 431 using std::cout;432 using std::cin;433 using std::endl;434 435 template<class T>436 class Out437 {438 public:439     void operator()(T o)440     {441         cout<<o<<‘\t‘;442     }443 };444 template<class T>445 void Swap(T& a,T&b)446 {447     if(a == b)448         return;449     T t=a;450     a=b;451     b=t;452 }453 inline int Rt(int idx)454 {455     return (idx<<1)+2;456 }457 inline int Lt(int idx)458 {459     return (idx<<1)+1;460 }461 462 template<class T>463 void HeapBuild(T* A,int idx,int size)464 {465     int child;466     for(; idx<=size/2; idx=child)467     {468         child=Lt(idx);469         if (child<size&&A[child]>A[idx])470         {471             Swap(A[idx],A[child]);472         }473         child=Rt(idx);474         if (child<size&&A[child]>A[idx])475         {476             Swap(A[idx],A[child]);477         }478     }479 }480 template<class T>481 void HeapSort(T* A, int size)482 {483     if(size == 1)484         return;485 486     for (int i=size/2; i>=0; i--)487     {488         HeapBuild(A,i,size);489     }490     int i=size-1;491     cout<<"swap max number:"<<A[0]<<","<<A[i]<<endl;492     Swap(A[0],A[i]);493     //现在得到了一个最大值，对前size-1个递归调用HeapSort494     HeapSort(A, i);495 }496 497 int main()498 {499     int size=0;500     cout<<"enter elements count num:"<<endl;501     cin>>size;502     //    size = 10;503     int* elems = new int[size];504     //    int elems[] = {1, 8, 4, 5, 6, 7, 11, 2, 3, 45};505     cout<<"Input all elements to be sorted:"<<endl;506     for(int i=0; i<size; cin>>elems[i++]);507 508     HeapSort(elems,size);509     std::for_each(elems,elems+size,Out<int>());510     delete []elems;511 512     system("pause");513     return 0;514 515 }516 517 #endif518 519 #pragma region MergeSort520 /*  521 归并算法思想:522     分而治之(divide - conquer);每个递归过程涉及三个步骤523     1) 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.524     2) 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作525     3) 合并: 合并两个排好序的子序列,生成排序结果. 526 */527 528 /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */529 void Merge(int SR[],int TR[], int start, int mid, int end)530 {531     int j,k,l;532     for(j=mid+1,k=start; start<=mid && j<=end; k++)    /* 将SR中记录由小到大地并入TR */533     {534         if (SR[start] < SR[j])535             TR[k] = SR[start++];536         else537             TR[k] = SR[j++];538     }539     if(start<=mid)540     {541         for(l=0; l<=mid-start; l++)542             TR[k+l] = SR[start+l];        /* 将剩余的SR[i..m]复制到TR */543     }544     if(j<=end)545     {546         for(l=0; l<=end-j; l++)547             TR[k+l] = SR[j+l];            /* 将剩余的SR[j..n]复制到TR */548     }549 }550 551 /* 递归法 */552 /* 将SR[s..t]归并排序为TR1[s..t] */553 void MSort(int SR[],int TR1[], int start, int end)554 {555     int mid;556     int TR2[MAXSIZE+1];557 558     if(start == end)559     {560         TR1[start] = SR[start];561     }562     else563     {564         mid = (start + end)/2;        /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */565         MSort(SR,TR2, start, mid);    /* 递归地将SR[s..m]归并为有序的TR2[s..m] */566         MSort(SR,TR2, mid+1, end);    /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */567 568         Merge(TR2,TR1, start, mid, end);    /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */569     }570 }571 572 /* 对顺序表L作归并排序 */573 void MergeSort(SqList *L)574 { 575     MSort(L->r, L->r, 1, L->length);576 }577 578 579 /* 非递归法 */580 /* 581 @brief:582     将SR[]中相邻长度为s的子序列两两归并到TR[] 583 @param:584     size: 归并相邻字段的大小585      len: 原始数据的总长度586 */587 void MergePass(int SR[],int TR[], int size,int len)588 {589     int i = 1;590 591     while(i <= len-2*size+1)592     {            593         Merge(SR,TR, i, i+size-1, i+2*size-1);    // 两两归并（归并长度为 size 的两个相邻子序列）594         i += 2*size;        595     }596 597     if(i < len-size+1)                // 归并最后两个序列(尚有两个子序列，其中后一个长度小于len)598     {599         Merge(SR,TR, i, i+size-1, len);600     }601     else                            // 若最后只剩下单个子序列602     {603         for( int j = i; j <= len; j++)604             TR[j] = SR[j];605     }606 }607 608 /* 对顺序表L作归并非递归排序 */609 void MergeSort2(SqList *L)610 {611     int* TR = (int*)malloc( L->length * sizeof(int) );    /* 申请额外空间 */612 613     int _size = 1;614     while( _size < L->length )615     {616         MergePass(L->r, TR, _size, L->length);617         _size *= 2;        /* 子序列长度加倍 */618 619         MergePass(TR, L->r, _size, L->length);620         _size *= 2;        /* 子序列长度加倍 */621     }622 }623 624 /*625 (归并)算法分析626 627 1、稳定性628     归并排序是一种稳定的排序。629 630 2、存储结构要求631     可用顺序存储结构,也易于在链表上实现。632 633 3、时间复杂度634     对长度为n的文件，需进行log(n)趟二路归并,每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。635 636 4、空间复杂度637     需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。638 */639 640 #pragma endregion MergeSort641 642 #pragma region QuickSort643 /* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */644 /* 此时在它之前(后)的记录均不大(小)于它。 */645 int Partition(SqList *L,int low,int high)646 { 647     int pivotkey;648 649     pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */650     while(low < high)          /* 从表的两端交替地向中间扫描 */651     { 652         while(low<high && L->r[high]>=pivotkey)653             high--;654         swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */655         while(low<high && L->r[low]<=pivotkey)656             low++;657         swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */658     }659     return low; /* 返回枢轴所在位置 */660 }661 662 /* 对顺序表L中的子序列L->r[low..high]作快速排序 */663 void QSort(SqList *L,int low,int high)664 { 665     int pivot;666     if(low < high)667     {668         pivot = Partition(L,low,high);    /*  将L->r[low..high]一分为二，算出枢轴值pivot */669         QSort(L, low, pivot-1);            /*  对低子表递归排序 */670         QSort(L, pivot+1, high);        /*  对高子表递归排序 */671     }672 }673 674 /* 对顺序表L作快速排序 */675 void QuickSort(SqList *L)676 { 677     QSort(L, 1, L->length);678 }679 680 681 /* 改进后快速排序******************************** */682 683 /* 快速排序优化算法 */684 int Partition1(SqList *L,int low,int high)685 { 686     int pivotkey;687 688     int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */  689     if (L->r[low]>L->r[high])            690         swap(L,low,high);    /* 交换左端与右端数据，保证左端较小 */691     if (L->r[m]>L->r[high])692         swap(L,high,m);        /* 交换中间与右端数据，保证中间较小 */693     if (L->r[m]>L->r[low])694         swap(L,m,low);        /* 交换中间与左端数据，保证左端较小 */695 696     pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */697     L->r[0]  = pivotkey;    /* 将枢轴关键字备份到L->r[0] */698     while(low<high) /*  从表的两端交替地向中间扫描 */699     { 700         while(low<high&&L->r[high]>=pivotkey)701             high--;702         L->r[low]=L->r[high];703         while(low<high&&L->r[low]<=pivotkey)704             low++;705         L->r[high]=L->r[low];706     }707     L->r[low]=L->r[0];708     return low;        /* 返回枢轴所在位置 */709 }710 711 void QSort1(SqList *L,int low,int high)712 { 713     int pivot;714     if( (high-low) > MAX_LENGTH_INSERT_SORT )715     {716         while(low < high)717         {718             pivot = Partition1(L, low, high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */719             QSort1(L,low,pivot-1);        /*  对低子表递归排序 */720             QSort1(L,pivot+1,high);        /*  对高子表递归排序 */721             low=pivot+1;    /* 尾递归 */722         }723     }724     else725         InsertSort(L);726 }727 728 /* 对顺序表L作快速排序 */729 void QuickSort1(SqList *L)730 { 731     QSort1(L, 1, L->length);732 }733 734 #pragma endregion QuickSort735 736 737 738 #define N 9739 int main()740 {741    int i;742    743    /* int d[N]={9,1,5,8,3,7,4,6,2}; */744    int d[N]={50,10,90,30,70,40,80,60,20};745    /* int d[N]={9,8,7,6,5,4,3,2,1}; */746 747    SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;748    749    for(i=0;i<N;i++)750      l0.r[i+1] = d[i];751    l0.length = N;752 753    l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;754 755    printf("排序前:\n");756    print(l0);757 758    printf("初级冒泡排序:\n");759    BubbleSort0(&l0);760    print(l0);761    762    printf("冒泡排序:\n");763    BubbleSort(&l1);764    print(l1);765    766    printf("改进冒泡排序:\n");767    BubbleSort2(&l2);768    print(l2);769    770    printf("选择排序:\n");771    SelectSort(&l3);772    print(l3);773    774    printf("直接插入排序:\n");775    InsertSort(&l4);776    print(l4);777 778    printf("希尔排序:\n");779    ShellSort(&l5);780    print(l5);781     782    printf("堆排序:\n");783    HeapSort(&l6);784    print(l6);785 786    printf("归并排序（递归）:\n");787    MergeSort(&l7);788    print(l7);789 790    printf("归并排序（非递归）:\n");791    MergeSort2(&l8);792    print(l8);793 794    printf("快速排序:\n");795    QuickSort(&l9);796    print(l9);797 798    printf("改进快速排序:\n");799    QuickSort1(&l10);800    print(l10);801 802 803 /*大数据排序*/804 /* 805     srand(time(0));  806     int Max=10000;807     int d[10000];808     int i;809     SqList l0;810     for(i=0;i<Max;i++)811         d[i]=rand()%Max+1;812     for(i=0;i<Max;i++)813         l0.r[i+1]=d[i];814     l0.length=Max;815     MergeSort(l0);816     print(l0);817 */818 819     system("pause");820     return 0;821 }