排序

  • 前提:void X_Sort(ElementType A[],int N)
  • 大多数情况下,为简单期间,讨论排序的情况默认是从小到大的整数排序(任何一种数据结构,只要可以比较都可以采用排序算法)
  • N是正整数
  • 只讨论基于比较的排序(>,=,<的情况均有定义)
  • 只讨论内部排序(内存空间足够大,所有数据都可以一次性导入内存中,排序在内存中一次性完成)
  • 稳定性:任意两个相等的数据,排序前后的相对位置不发生改变
  • 没有一种排序是在任何情况下都表现最好的

冒泡排序

冒泡排序伪代码描述

void Bubble_Sort(ElementType A[],int N)
{
    for(P=N-1;P>=0;P--){
        flag=0;
        for(i=0;i<P;i++){               //一趟冒泡
            if(A[i]>A[i+1]){  
                Swap(A[i],A[i+1]);
                flag=1;                 //标识发生了交换
            }
        }
        if(flag==0)break;               //冒泡全程无交换,表示排序已结束
    }
}

冒泡排序:

  • 好比比较相邻的两个泡泡,因为大的泡泡总是飞在小泡泡的上面,所以排序时就按照这种方法将相邻的两数据之间进行交换排序
  • 每一趟冒泡确定序列中最大/最小的元素位置
  • 稳定性:稳定
  • 最好情况:顺序T=O(N)T=O(N) (将数据扫描一遍即可)
  • 最坏情况:逆序T=O(N2)T=O(N^2)
    此外,冒泡排序有一个好处是这种算法的比较和交换都是单向且相邻的,因此对于单向链表的存储结构而言这种方法比较合适

插入排序

插入排序伪代码描述

void Insertion_Sort(lementType A[],int N)
{
    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;                       //新增牌位(放进合适的位置)
    }
}

插入排序:

  • 可以类比打牌的时候一张张摸牌的同时进行排序,将新摸到的牌放到合适的位置
  • 稳定性:稳定
  • 最好情况:顺序T=O(N)T=O(N)
  • 最坏情况:逆序T=O(N2)T=O(N^2)
  • 插入排序相对于冒泡排序(交换)的优点在于每次比较后不需要直接移动元素到空位,而是继续往前找直到找到位置后再一次性插入

例:给定初始序列{34,8,64,51,32,21},冒泡排序和插入排序分别需要多少次元素交换才能完成?

  • 冒泡排序需9次交换
    • 第一趟冒泡:34,8,64,51,32,21——>8,34,51,32,21,64
      • 4次交换
    • 第二趟冒泡:8,34,51,32,21,64——>8,34,32,21,51,64
      • 2次交换
    • 第三趟冒泡:8,34,32,21,51,64——>8,32,21,34,51,64
      • 2次交换
    • 第四趟冒泡:8,32,21,34,51,64——>8,21,32,34,51,64
      • 1次交换
  • 插入排序需9次交换
    • 第一张牌:34,8——>8,34
      • 1次交换
    • 第二张牌:8,34,64——>8,34,64
      • 无交换
    • 第三张牌:8,34,64,51——>8,34,51,64
      • 1次交换
    • 第四张牌:8,34,64,51,32——>8,32,34,51,64
      • 3次交换
    • 第五张牌:8,34,64,51,32,21——>8,21,32,34,51,64
      • 4次交换
  • 交换次数的实质:逆序对个数

冒泡排序和插入排序的时间复杂度分析

  • 对于下标i<j,如果A[i]>A[j],则称(i,j)是一对逆序对(inversion)
  • 问题:序列[34,8,64,51,32,21][34,8,64,51,32,21]中有多少逆序对?
    • (34,8),(34,32),(34,21),(64,51),(64,32),(64,21),(51,32),(51,21),(32,21)(34,8),(34,32),(34,21),(64,51),(64,32),(64,21),(51,32),(51,21),(32,21)
  • 交换相邻的两个元素:最多只能消去一个逆序对
  • 插入排序:插入排序的时间复杂度不仅跟序列的元素个数有关,还跟逆序对有关
    • 设逆序对个数为I,则T(N,I)=O(N+I)T(N,I)=O(N+I)
    • 如果序列基本有序,则插入排序简单且高效(如果I和N是同一数量级,则插入排序的复杂度是线性的)
  • 定理:任意N个不同元素组成的序列平均具有N(N14\frac{N(N-1}{4}个逆序对(N(N1)2\frac{N(N-1)}{2}个对子)
  • 定理:任何仅以交换相邻两元素来排序的算法,其最坏情况平均时间复杂度下界为Ω(N2)Ω(N^2)
    • 这意味着:要提高算法效率,必须
      • 每次消去不止一个逆序对
      • 每次交换相隔较远的2个元素

选择排序

选择排序:依次找到序列中剩余的最小元
选择排序伪代码描述:

void Selection_Sort(ElementType A[],int N)
{
    for(i=0;i<N;i++){
        MinPosition=ScanForMin(A,i,N-1);    //从A[i]到A[N-1]中找最小元,并将其位置赋给MinPosition
        Swap(A[i],A[MinPosition]);          //将未排序部分的最小元换到有序部分的最后位置
    }
}

无论如何:T=Θ(N2)T=Θ(N^2)
算法优化的关键:对于交换元素来说稳定O(N)O(N),关键在于怎样找到最小元