数据结构第九、十讲排序

本文主要是介绍数据结构第九、十讲排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数据结构第九、十讲排序

一、前提

统一格式

void X_Sort(ElementType A[],int N);

1.大多情况下，为简单起见，讨论从小到大的整数排序
2.N是正整数
3.只讨论基于比较的排序（>,=,<有定义）
4.只讨论内部排序
5.稳定性：任意两个相等的数据，排序前后的相对位置不发生改变
6.没有一种排序是任何情况下都表现最好的

二、冒泡排序

最好情况：T = O（N）
最坏情况：T = O（N^2）
稳定性强

void Bubble_Sort(ElementType A[],int N)
{
	for(int i=N-1;i>=0;i--) //一趟冒泡 
	{
		int flag=0;//交换标记 
		for(int j=0;j<i;j++)
		{
			if(A[j]>A[j+1])
			{
				swap(A[j],A[j+1]);
				flag = 1;//发生了交换 
			}
		}
		if(flag==0) break;//全程无交换，证明有序化 
	}
}

练习

在这里插入图片描述

三、插入排序

void InsertionSort( ElementType A[], int N )
{ /* 插入排序 */
     int P, i;
     ElementType Tmp;
     
     for ( P=1; P<N; P++ ) {
         Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
         for ( i=P; i>0 && A[i-1]>Tmp; i-- )
             A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/
         A[i] = Tmp; /* 放进合适的位置 */
     }
}

练习

在这里插入图片描述

时间复杂度下界

逆序对：对于下标i<j，如果A[i]>A[j]，则称（i,j）是一对逆序对

在这里插入图片描述
交换2个相邻的元素正好消去1个逆序对
插入排序：T（N，I）= O（N+I）
如果序列基本有序，则插入排序简单且有效

定理：任意N个不同元素组成的序列平均具有N*（N-1）/4个逆序对
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ω（N^2）

这意味着：要提高算法效率，必须
每次消去不止1个逆序对！
每次交换相隔较远的2个元素

四、希尔排序

在这里插入图片描述

void ShellSort( ElementType A[], int N )
{ /* 希尔排序 - 用Sedgewick增量序列 */
     int Si, D, P, i;
     ElementType Tmp;
     /* 这里只列出一小部分增量 */
     int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
     
     for ( Si=0; Sedgewick[Si]>=N; Si++ ) 
         ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

     for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
         for ( P=D; P<N; P++ ) { /* 插入排序*/
             Tmp = A[P];
             for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
                 A[i] = A[i-D];
             A[i] = Tmp;
         }
}

在这里插入图片描述

五、堆排序

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 );
     }
}

在这里插入图片描述

六、归并排序

核心：有序子列的归并
任何情况下时间复杂度都是O（NlogN）
稳定的算法
需要额外的O（N）空间，基本不被用于做内排序
在这里插入图片描述

递归算法

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

/* 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( "空间不足" );
}

ACwing代码

#include<iostream>
using namespace std;
const int M=100005;
int n,tmp[M],a[M];
void merge_sort(int a[],int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)/2;
    merge_sort(a,l,mid),merge_sort(a,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    }
    while(i<=mid) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    merge_sort(a,0,n-1);
    for(int i=0;i<n;i++)
    printf("%d ",a[i]);
    return 0;

}

作者：第一万零一次AC
链接：https://www.acwing.com/activity/content/code/content/1075529/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

非递归算法

在这里插入图片描述

/* 归并排序 - 循环实现 */
/* 这里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( "空间不足" );
}

七、快速排序

最好T（N）= O（NlogN）
最坏T（N）= O（N^2）
不稳定
在这里插入图片描述
每次正好中分==>T（N）= O（NlogN）

主元的选择

在这里插入图片描述

子集划分

在这里插入图片描述

小规模数据处理——排序算法的选择

在这里插入图片描述

课堂代码

/* 快速排序 */

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 ); /* 元素太少，用简单排序 */ 
}

void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
     Qsort( A, 0, N-1 );
}

Acwing代码

#include<iostream>
using namespace std;
const int N=100005;
void qsort(int a[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=r+1,x=a[(l+r)/2];
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    qsort(a,l,j);
    qsort(a,j+1,r);
}
int main()
{
    int n;
    int a[N];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    qsort(a,0,n-1);
    for(int i=0;i<n;i++)
    printf("%d ",a[i]);
    return 0;
}

作者：第一万零一次AC
链接：https://www.acwing.com/activity/content/code/content/1067803/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

八、表排序

间接排序：定义一个指针数组作为“表”（Table）

在这里插入图片描述

九、桶排序

在这里插入图片描述

十、基数排序

在这里插入图片描述
先按个位数排序，排序后放到一个链表里，再按十位数排序，放到一个链表里，再按百位数排序。

多关键字的排序

在这里插入图片描述

思考：次位排序（LSD）任何时候都比主位排序（MSD）快吗？
如果主位的基数比次位大的时候（即主位更能把元素分散开），MSD比LSD更快。反之，LSD比MSD快。

代码示例

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

/* 假设元素最多有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);
     } 
}

十一、排序算法的比较

在这里插入图片描述

课后练习

在这里插入图片描述

某名企的面试题有一道是这样的：
从1000个数字中找出最大的10个数字，最快的算法是——
A. 归并排序
B. 快速排序
C. 堆排序
D. 选择排序

答案是C。但是这个答案真的对吗？
①归并排序要全部排好后才能得出结果，肯定不算最优。

②快排也要等到全部排好后才有结果，同样不是最优。

③堆排序：可以设置一个容量为10的最小堆，每次遍历元素比堆顶元素大就将堆顶元素替换，一轮遍历下来即得到前十大的数字，但针对每个元素的操作比较麻烦，设最坏情况每个新元素都比堆中所有元素更大，则单个元素替换堆顶元素并下滤一层的过程可能要7次操作甚至更多，总操作次数可能为 1000log107=21000。

④选择排序：遍历十次即出结果，关键是对每个元素的操作简单，只需要与max比较和给max赋值2次操作，最坏情况下操作次数为 1000102=20000。

因此，可能选择排序还更快一些。

原因就在于选择排序虽然是O(N^2)的时间复杂度，但其常数项很小（仅为2），对于小规模问题效率很高（如题中取前10大数字）。

而堆排序尽管是O(NlogN)的时间复杂度，但其常数项很大（大于7），更适合解决大规模的问题（比如1000个数字全部排序）。

这篇关于数据结构第九、十讲排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！