排序

前提：void X_Sort(ElementType A[],int N)
- 本文及后续章节希尔排序、快速排序、堆排序、归并排序、表排序、桶排序、基数排序中在介绍排序算法时，函数头都有统一的范式为X_Sort
大多数情况下，为简单期间，讨论排序的情况默认是从小到大的整数排序(任何一种数据结构，只要可以比较都可以采用排序算法)
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^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^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)$
交换相邻的两个元素：最多只能消去一个逆序对
插入排序：插入排序的时间复杂度不仅跟序列的元素个数有关，还跟逆序对有关
- 设逆序对个数为I，则 $T(N,I)=O(N+I)$
- 如果序列基本有序，则插入排序简单且高效(如果I和N是同一数量级，则插入排序的复杂度是线性的)
定理：任意N个不同元素组成的序列平均具有 $\frac{N(N-1}{4}$ 个逆序对( $\frac{N(N-1)}{2}$ 个对子)
定理：任何仅以交换相邻两元素来排序的算法，其最坏情况平均时间复杂度下界为 $Ω(N^2)$ $Ω (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=Θ(N^2)$
算法优化的关键：对于交换元素来说稳定 $O(N)$ ，关键在于怎样找到最小元