1.插入排序

算法基本思想
将待排序的记录插入到已排序的子文件中去,使得插入之后得到的子文件仍然是有序子文件。插入一个记录,首先要对有序子文件进行查找,以确定这个记录的插入位置。按查找方式的不同,插入排序又可以分为线性插入排序和折半插入排序,前者使用顺序查找,后者使用折半查找。

1.1 简单插入排序

插入排序:设待排序的文件为:(r[1],r[2],…,r[n])
关键字为:(r[1].key,r[2].key,…,r[n].key)
首先,将初始文件中的记录r[1]看作有序子文件;
第1遍:将r[2]插入有序子文件中,若:
r[2].key<r[1].key,
则r[2]插在r[1]之前;否则,插在r[1]的后面。
第2遍:将记录r[3]插入前面已有2个记录的有序子文件中,得到3个记录的有序子文件。
以此类推,依次插入r[4],…,r[n],最后得到n个记录的递增有序文件。

就是找到最好的插入位置

void InsertSort(RecType r[],int n)
// 对数组r[1..n]中的n个记录作插入排序
{ int i,j;
for (i=2;i<=n;i++){
r[0]=r[i]; //待插记录r[i]存入监视哨中
j=i-1; //以排序的范围1-i-1
//从r[i-1]开始向左扫描
while(r[0].key<r[j].key)
{
r[j+1]=r[j]; //记录后移
j–; //继续向左扫描
}
r[j+1]=r[0]; //插入记录r[0],即原r[i]
}
}

(1)最好情况,原n个记录递增有序:比较关键字n-1次,移动记录2(n-1)次,(将数据复制到r[0]后又复制回来)
(2)最坏情况:$O(n^2)$

1.2.折半插入排序(二分插入排序)

(a)由于插入排序的基本思想是在一个有序序列中插入一个新的记录,因此可以利用“折半查找”查询插入位置,由此得到的插入排序算法为“折半插入排序”,又被称为二分法插入排序。
(b)直接插入排序的算法简单易行,对长度(n)很大的记录序列宜采用性能更好的插入排序算法。
(c)折半插入排序过程中的折半查找的目的是查询插入点,因此不论是否存在和给定值相同的关键字,结束查找过程的条件都是high<low,并且插入位置为low指示的地方。

实例:插入到low处,low>high处停下
void BInsertSort (SqList &L)  {  
// 对顺序表L作折半插入排序 
    for ( i=2; i<=L.length; ++i )  
    { 				//假定第一个记录有序  
        L.r[0] = L.r[i];		// 将L.r[i]暂存到L.r[0]  
        low = 1; high = i-1;  
        while (low<=high)   
        {   // 在r[low..high]中折半查找有序插入的位置   
            m = (low+high)/2; 		// 折半   
            if (L.r[0].key < L.r[m].key)) 		
                high = m-1;		// 插入点在低半区   
            else
 		low = m+1; 		// 插入点在高半区
      } // while  
       for ( j=i-1; j>=low; - -j ) L.r[j+1] = L.r[j]; // 记录后移   L.r[high+1] = L.r[0];		// 插入 
    } //for
} // BInsertSort
1.3.希尔(shell)排序 (缩小增量排序)

(a)是插入排序中效率最高的一种排序方法。又称“缩小增量排序”,是由D.L.Shell在1959年提出来的。
(b)基本思想是,先对待排序列进行“宏观调整”,待序列中的记录“基本有序”时再进行直接插入排序。 注:所谓“ 基本有序” 是指,在序列中的各个关键字之前,只存在少量关键字比它大的记录。
(c)做法是:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序;然后,到第二个增量d2<d1重复上述分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

例如·:3 2 1

1 4 5 3 2 6
3:三类:14 25 36
1 2 5 3 4 6
2:2类:135 246
1 2 4 3 5 6
1:一类:123456
1 2 3 4 5 6

2 交换排序

2.1 冒泡排序

基本思想: 设待排序的文件为r[1..n]
第1趟(遍):从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key,则交换记录r[i]和r[i+1]的位置;否则,不交换。(i=1,2,…n-1)
第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。
第2趟:从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key,则交换记录r[i]和r[i+1]的位置;否则,不交换。(i=1,2,…n-2)
第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位置上。
……
作完n-1趟,或者不需再交换记录时为止。

    void  bubble1(int a[],int n)
  
    { int i,j,temp;
  
    for(i=0;i<n-1;i++)     //作n-1趟排序
         
for(j=0;j<n-1-i;j++)       
       
              if (a[j]>a[j+1])            
          
                  { temp=a[j];      //交换记录 
      
                    a[j]=a[j+1];           
     
                    a[j+1]=temp;           
  
                  }       
      
    for(i=0;i<n;i++)
   printf("%d",a[i]);  //输出排序后的元素 
   
      }

可以加一个swap变量,如果一次排序没换过元素,那就是

● 最好情况: 待排序的文件已是有序文件,只需要进行1趟
排序,共计比较关键字的次数为 n-1 不交换记录。
● 最坏情况: 要经过n-1趟排序,所需总的比较关键字的次数为
(n-1)+(n-2)+…+1=n(n-1)/2
交换记录的次数最多为
(n-1)+(n-2)+…+1=n(n-1)/2
移动记录次数最多为
3n(n-1)/2 。
● 只需要少量中间变量作为辅助空间。 O(1)
● 算法是稳定的。

2.2 快速排序

基本思想:首先在r[1..n]中,确定一个r[i],经过比较和移动,将r[i]放到”中间”某个位置上,使得r[i]左边所有记录的关键字小于等于r[i].key,r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。
用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。

设置两个指针:一个大区域,一个小区域

void quksort(RecType r[],int low,int high)
{  RecType x;int i,j;
 
  if (low<high)                       //有两个以上记录
   
   { i=low;j=high;x=r[i];          //保存记录到变量x中
     
     do {                             //此时i指示位置可用
        while (i<j && r[j].key>=x.key)
     
        j--;     //j从右向左端扫描通过key不小于x.key的元素

           if (i<j)                        //i,j未相遇
           {   r[i]=r[j]; i++;            //此时j指示位置可用
               while(i<j && r[i].key<=x.key)
               i++;   //i从左向右端扫描通过key不大于x.key的元素
               if (i<j)
             
               { r[j]=r[i];j--;}
          
           }
 
       } while (i!=j);                 //i,j未相遇
   
 }

在上一级的函数就分治即可

找到左边第一个比20大的,右边第一个比20小的,交换位置

就平均速度而言,快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为$O(nlog_2n)$。
但是,在最坏情况下(基本有序时),快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为$O(n^2)$。
快速排序需要一个栈空间来实现递归。若每次划分均能将文件均匀分割为两部分,则栈的最大深度为$|log_2n|+1$,所需栈空间为$O(log_2n)$,即空间复杂度 $S(n)= O (log2n)$
快速排序是不稳定的。

ElementType Median3( ElementType A[], int Left, int Right )
{ 
    int Center = (Left+Right) / 2;
    if ( A[Left] > A[Center] )
        Swap( &A[Left], &A[Center] );
    if ( A[Left] > A[Right] )
        Swap( &A[Left], &A[Right] );
    if ( A[Center] > A[Right] )
        Swap( &A[Center], &A[Right] );
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return  A[Right-1];  /* 返回基准Pivot */
}

void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */ 
     int Pivot, Cutoff, Low, High;
      
     if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多,进入快排 */
          Pivot = Median3( A, Left, Right ); /* 选基准 */ 
          Low = Left; High = Right-1;
          while (1) { /*将序列中比基准小的移到基准左边,大的移到右边*/
               while ( A[++Low] < Pivot ) ;
               while ( A[--High] > Pivot ) ;
               if ( Low < High ) Swap( &A[Low], &A[High] );
               else break;
          }
          Swap( &A[Low], &A[Right-1] );   /* 将基准换到正确的位置 */ 
          Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
          Qsort( A, Low+1, Right );   /* 递归解决右边 */  
     }
     else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少,用简单排序 */ 
}

(52, 49, 80, 36, 14, 75, 58, 97, 23, 61)
经第1趟快速排序之后为: (23, 49, 14, 36) 52 (75, 58, 97, 80, 61)
经第2趟快速排序之后为: (14) 23 (49, 36) 52 (61, 58) 75 (80, 97)
经第3趟快速排序之后为: (14, 23, 36, 49, 52, 58, 61, 75, 80, 97)
注:为避免出现枢轴记录关键字为”最大”或”最小”的情况,通常进行的快速排序采用”三者取中”的改进方案,即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换,一次划分的算法仍不变。

3 选择排序

3.1 简单选择

算法思想:设待排序的文件为(r[1],r[2],…,r[n]),关键字为(r[1].key,r[2].key,…,r[n].key),
第1趟(遍):在(r[1],r[2],…,r[n])中,选出关键字最小的记录r[min].key,若min≠1,则交换r[1]和r[min];
需要进行n-1次比较。
  第2趟(遍):在n-1个记录(r[2],…,r[n])中,选出关键字最小的记录r[min].key,若min≠2,则交换r[2]和r[min];
  需要进行n-2次比较。
  第n-1趟(遍):在最后的2个记录记录(r[n-1],r[n])中,选出关键字最小的记录r[min].key,若min≠n-1,则交换r[n-1]和r[min];需要进行1次比较。

3.2 树形选择排序

树形选择排序又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法。可用一棵有n个叶子结点的完全二叉树表示。
基本思想为:
首先对n个记录的关键字进行两两比较,然后在其中n/2个较小者之间再进行两两比较,如此重复,直到选出最小关键字的记录为止(树根)。
将最小关键字输出,且将其原来位置改为极大数,与此位置相关部分重新(向树根方向)进行比较,选出次小关键字,保留结果。
如此下去,直至全部排序完成。

$19_1,1,23,27,55,19_2,84,14$

该方法比直接选择排序速度上有很大提高,其缺点有:
(1)需要另开储存空间保存排序结果;
(2)n个待排序关键字,需要额外的(n-1)个内部结点(包括根结点),增加了内存开销。
(3)将最小关键字改为极大数,再与兄弟结点比较属于多余。
故:树形选择排序一般不是用来排序而是用来证明某些问题。为了弥补以上缺点,威洛姆斯在1964年提出了另一种形式的选择排序—堆排序。

3.3 堆排序

堆的定义略
问题1:如何将序列{k1,k2,…,kn} 处理成(大顶)堆(初始化)?
问题2:如何在堆顶元素被替换后,调整剩余元素成为一个新的堆。

孩子比父亲大:最大的孩子和父亲交换,一直到没有孩子或者孩子都比父亲小
void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}
 
void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;

    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void HeapSort( ElementType A[], int N ) 
{ /* 堆排序 */
     int i;
      
     for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
         PercDown( A, i, N );
     
     for ( i=N-1; i>0; i-- ) {
         /* 删除最大堆顶 */
         Swap( &A[0], &A[i] ); /* 见代码7.1 */
         PercDown( A, 0, i );
     }
}

这个代码把问题1和问题2统一化了
时间复杂度:O(nlogn)

4 归并排序

归并的操作,就是两个指针,谁少就copy谁,最后就把剩下的元素copy过去

第一个想法:
每个子文件的长度从2,4,8一直递增

1.假如说:现在还剩下2s以上的空缺,就直接s和s互相互补即可
2.假如说:现在还剩下s-2s的空缺,就剩下的部分归并
3.假如说:现在还剩下0-s的空缺,就直接照抄

当然,还有一种写法就是找到最中间的一个元素,然后进行分化

/* 归并排序 - 递归实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */ 
     int Center;
     
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
          Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
          Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
     }
}

void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
     
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "空间不足" );
}
/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */

/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;
      
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

void Merge_Sort( ElementType A[], int N )
{ 
     int length; 
     ElementType *TmpA;
     
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( ElementType ) );
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              length *= 2;
              Merge_pass( TmpA, A, N, length );
              length *= 2;
          }
          free( TmpA );
     }
     else printf( "空间不足" );
}

5 基数排序

就是构建十个桶,按照个位,先按照各元素放入桶里.
接着再取出,按照0-9的顺序,接着是十位,接着是百位

/* 基数排序 - 次位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
    int key;
    PtrToNode next;
};

/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
 
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
    
    for (i=1; i<=D; i++) {
        d = X % Radix;
        X /= Radix;
    }
    return d;
}

void LSDRadixSort( ElementType A[], int N )
{ /* 基数排序 - 次位优先 */
     int D, Di, i;
     Bucket B;
     PtrToNode tmp, p, List = NULL; 
     
     for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
         B[i].head = B[i].tail = NULL;
     for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
         tmp = (PtrToNode)malloc(sizeof(struct Node));
         tmp->key = A[i];
         tmp->next = List;
         List = tmp;
     }
     /* 下面开始排序 */ 
     for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
         /* 下面是分配的过程 */
         p = List;
         while (p) {
             Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
             /* 从List中摘除 */
             tmp = p; p = p->next;
             /* 插入B[Di]号桶尾 */
             tmp->next = NULL;
             if (B[Di].head == NULL)
                 B[Di].head = B[Di].tail = tmp;
             else {
                 B[Di].tail->next = tmp;
                 B[Di].tail = tmp;
             }
         }
         /* 下面是收集的过程 */
         List = NULL; 
         for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */
             if (B[Di].head) { /* 如果桶不为空 */
                 /* 整桶插入List表头 */
                 B[Di].tail->next = List;
                 List = B[Di].head;
                 B[Di].head = B[Di].tail = NULL; /* 清空桶 */
             }
         }
     }
     /* 将List倒入A[]并释放空间 */
     for (i=0; i<N; i++) {
        tmp = List;
        List = List->next;
        A[i] = tmp->key;
        free(tmp);
     } 
}

6 计数排序

这个可以用于排序的数范围已知的情况,非常好写

7 排序算法的比较

最后修改日期:2020年11月19日