• 时间复杂度：也就是算法的时间量度，记住：T(n)=O(f(n))。表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同（即 一个数量级）。
• 空间复杂度：指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间的大小。

插入排序

直接插入排序

注意：第一张牌已经握在手中了，从第二张开始。（第一张牌不需要比较，也没得比较，直接抓在手中，所以从第二张开始）

• 基本思想：
  可以将L(2)~L(n)依次插入到前面已排好序的子序列中，初始假定L[1]是一个已经排好序的子序列。
  1. 将待排元素L(i)放入哨兵L(0)中。
  2. 查找出L(i)在L[1…i-1]中的插入位置k。
  3. 将L[k…i-1]中的所有元素全部后移一个位置。
  4. 将L(i)复制到L(k)。
• 具体操作：
  简单来说，直接插入排序就是将待排的序列中每个元素依次插入到已排好的序列中，最后得到有序的结果。（可以类比抓牌，第一张牌握在手中，从第二张牌开始，每次比较都是最后抓的一张牌向前面抓的牌比较，从后往前比较，放入该放的位置，再继续抓牌，直到所有牌被抓在手中，有序。）
• 具体实现：

void InsertSort(ElemType A[], int n) {
    int i, j;
    for(i = 2; i <= n; i++) {       //依次将A[2]~A[n]插入到前面已排序序列
        if(A[i].data < A[i-1].data) {   //若A[i]的关键码小于有序序列的最后一个元素（有序序列中的最大值）（即其前驱），需将A[i]插入有序表；大于有序序列的最后一个元素，则不用从头插入，并入有序序列（本来就排在有序序列之后），成为有序序列新的最大值（最后一个）
            A[0] = A[i];        //复制为哨兵，A[0]不存放元素
            for(j = i - 1; A[0].data < A[j].data; --j) {    //从后往前查找待插入位置
                A[j+1] = A[j];      //向后挪位
            }
            A[j+1] = A[0];      //复制到插入位置
        }
    }
}

• 性能分析：
  • 空间效率：O(1)
    仅使用了常数个辅助单元。
  • 时间效率：O(\(n^2\))
    在排序过程中，向有序子表中逐个插入元素的操作进行了n-1趟，每趟操作都分比较关键字和移动元素，而比较次数和移动元素取决于待排序表的初始状态。
    • 最好情况：O(n) (顺序)
    • 最坏情况：O(\(n^2\)) (逆序)
    • 平均情况：O(\(n^2\))
  • 稳定性：稳定
    由于每次插入元素时，总是从后向前先比较在移动，所以不会出现相同元素相对位置发生变化的情况。
  • 适用性：
    适用于顺序存储和链式存储的线性表。
    适用于基本有序的排序表和数据量不大的排序表。
    为链式存储时，可以从前往后查找指定元素的位置。

    大部分排序算法都仅适用于顺序存储的线性表。

折半插入排序

• 基本思想：
  将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。
• 具体操作：
  基本思想与直接插入排序类似，区别在于寻找插入位置的方法不同，基本条件是原序列已经有序，在已经有序的序列中插入一个新的元素，相对于直接插入排序将更快
• 具体实现：

void InsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for(i = 2; i <= n; i++) {       //依次将A[2]~A[n]插入前面的已知排序序列
        A[0] = A[i];        //将A[i]暂存到A[0]
        low = 1;            //设置折半查找的范围
        high = i-1;         
        while(low <= high) {    //折半查找（默认递增有序）
            mid = (low + high) / 2;     //取中间点
            if(A[mid].data > A[0].data) {   //查找左半边
                high = mid - 1;
            }else {         //查找右半边
                low = mid + 1;
            }
            //查找结束后，high<low，k在high和high+1之间，所以顶替high+1位置，把high+1后面的元素后移
            for(j=i-1; j>=high+1; --j) {
                A[j+1] = A[j];      //统一后移元素，空出插入位置
            }
            A[high+1] = A[0];       //插入
        }
    }
}

• 性能分析：
  • 空间效率：O(1)
    仅使用了常数个辅助单元。
  • 时间效率：O(\(n^2\))
    仅减少了比较元素的次数，约为O(\(nlog_2n\))，该比较次数与待排序表的初始状态无关，仅取决于表中元素的个数n；而元素移动次数并未改变，它依赖于待排序表的初始状态。
    • 最好情况：O(\(nlog_2n\)) (顺序)
    • 最坏情况：O(\(n^2\)) (逆序)
    • 平均情况：O(\(n^2\))
  • 稳定性：稳定
  • 适用性：
    适用于顺序存储的线性表
    适用于基本有序的排序表和数据量不大的排序表。

希尔排序

交换效率（次数）取决于序列中逆序对的个数；
直接插入排序每次交换相邻两个元素，只能消除一个逆序对；
所以要想提高排序效率，就得每次交换相隔较远的两个逆序对，一次可以消去更多的逆序对，所以创造了希尔排序。

PS：而相隔较远的大范围交换，则会影响它的稳定性。

• 基本思想：（其实就相当于把直接插入排序的间隔由1变为了d）
  先将待排序表分割成若干形如L[i, i+d, i+2d, …, i+kd]的“特殊”子表，分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
• 具体操作：
  简单描述就是将待排序列进行分组，例如每隔d-1个数就是一组，然后在组内进行直接插入排序，然后不断缩小分组增量，例如将上面已经在组内排序好的重新编组，例如每隔d-3个数一组，不断缩小，直到所有序列都为一组，再进行最后一次直接插入排序，就得到有序的序列。
• 具体实现：

//对顺序表做希尔插入排序，本算法和直接插入排序相比，做了以下修改：
//1. 前后记录的位置增量是dk，不是1
//2. A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
void ShellSort(ElemType A[], int n) {
    for(dk=n/2; dk>=1; dk=dk/2) {       //步长变化
        for(i=dk+1; i<=n; ++i) {    //因为插入排序第一个(即 A[1])已经握在手中了
            if(A[i].data < A[i-dk].data) {      //需将A[i]插入有序增量子表
                A[0] = A[i];        //暂存在A[0]
                for(j=i-dk; j>0 && A[0].data<A[j].data; j-=dk) {
                    A[j+dk] = A[j];     //记录后移，寻找插入的位置
                }
                A[j+dk] = A[0];     //插入
            }
        }
    }
}

• 性能分析：
  • 空间效率：O(1)
    仅使用了常数个辅助单元
  • 时间效率：
    由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。
    • 最好情况：O(\(n^{1.3}\)) (当n在某个特定范围时)
    • 最坏情况：O(\(n^2\))
    • 平均情况：NA
  • 稳定性：不稳定
    当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。
  • 适用性：仅适用于线性表为顺序存储的情况。

交换排序

冒泡排序

• 基本思想：
  假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1] > A[i]），则交换它们，知道序列比较完。称之为一趟冒泡，即将最小的元素交换到待排序列的第一个位置（关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”）。下一趟冒泡时，前一趟确定的最小元素不在参与比较，待排序列减少一个元素。这样最多做n-1趟冒泡就能把所有元素排好序。
• 具体操作：
  第一个元素和第二个元素比较，如果第一个大，两者交换，然后第二个和第三个比较，以此类推直到最后一个，最后大的记录会“沉底”，小的记录会“上浮”，这就是冒泡排序的名字由来
• 具体实现：

//用冒泡排序法将序列A中的元素按从小到大排列
void BubbleSort(ElemType A[], int n) {
    for(i=0; i<n-1; i++) {  //趟数
        flag = false;       //表示本趟冒泡是否发生交换的标志
        for(j=n-1; j>i; j--) {      //一趟冒泡过程
            if(A[j-1].data > A[j].data) {   //若为逆序
                swap(A[j-1], A[j]);     //交换
                flag = true;
            }
        }
        if(flag == false) {     //本趟遍历后没有发生交换（前面一个元素均小于后面一个），说明表已经有序
            return;
        }
    }
}

//下面是笔者常用的写法，把趟数从1开始，方便区分趟数
void BubbleSort(ElemType A[], int n) {
    for(i=1; i<n; i++) {    //趟数从1开始，第一趟...
        flag = false;   //表示本趟冒泡是否发生交换的标志
        for(j=0; j<n-i; j++) {  //一趟冒泡过程，从0到n-1都往后比较一个
            if(A[j].data > A[j+1].data) {
                swap(A[j],A[j+1]);
                flag = true;
            }
        }
        if(flag == false) {//本趟遍历后没有发生交换（前面一个元素均小于后面一个），说明表已经有序
            return;
        }
    }
}

• 性能分析：
  • 空间效率：O(1)
    仅使用了常数个辅助单元
  • 时间效率：O(\(n^2\))
    当初始序列有序时，显然第一趟冒泡后没有元素交换（前均小于后），从而直接跳出循环，比较次数为n-1，移动次数为0。
    • 最好情况：O(n) (顺序)
    • 最坏情况：O(\(n^2\)) (逆序)
    • 平均情况：O(\(n^2\))
  • 稳定性：稳定
    i>j且A[i].data==A[j].data时，不会交换两个元素
  • 适用性：
    适用于线性表（顺序表和链表）（每一趟都是顺着来的，所以满足链表）
    适用于基本有序的排序表。

快速排序

冒泡排序每次交换相邻两个元素，只能消除一个逆序对；
所以要想提高排序效率，就得每次交换相隔较远的两个逆序对，一次可以消去更多的逆序对，所以创造了快速排序。

PS：而相隔较远的大范围交换，则会影响它的稳定性。

• 基本思想：
  基于分治法，在待排序表L[1…n]中任取一个元素pivot(枢纽)作为基准，通过一趟排序将待排表划分为两个独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中所有元素小于pivot，L[k+1…n]中的所有元素大于等于pivot，则pivot放在了其排序后的最终位置L(k)上，这个称为一趟快速排序。而后分别递归地对两个子表重复上述过程，直至每个部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
• 具体操作：
  序列两端设置一个i和j指向第一个元素和最后一个元素，以第一个数作为参照数，从j开始移动（因为要把枢纽（第一个元素）交换掉，不能让它一直呆在原位不动，否则无法将它划分左小右大的排序（因为左边一定包含了他自己）），若j所指的数小于参照数则与i交换（赋值到i即可，不用交换），此时j停止移动，i开始移动，若i所指的数大于参照数，则将i与j进行交换，此时i停止移动，j开始移动，循环往复，直到i与j相遇，则停止这一轮排序，接着就对i和j相遇（即 i左边的都比pivot小，j右边的都比pivot大，所以相遇位置，就是pivot的最终位置）这个位置分成的两段分别再进行快速排序，直到序列有序为止。
• 操作过程：
  28,16,32,12,60,2,5,72
  使用挖坑法：将基准挖出来，其他数不断移动，直到空出一个左小右大的坑，再把基准填进去。
  
• 当每次的枢轴都把表等长为相近的两个子表时，速度是最快的。
• 快排的阶段性排序结果的特点是：第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。
• 具体实现：

//划分算法（一趟排序过程）
int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];    //将当前表中第一个元素设为枢轴值，对表进行划分
    while(low < high) {     
        while(low<high && A[high]>=pivot) {     //当high中的值已经比pivot大，则不移动
            --high;
        }
        //循环结束时，high中的元素比pivot小
        A[low] = A[high];       //将小值移动到左端
        while(low<high && A[low]<=pivot) {      //当low中的值已经比pivot小，则不移动
            ++low;
        }
        //循环结束时，low中的元素比pivot大
        A[high] = A[low];       //将大值移动到右端
    }
    //循环结束时，low==high，已经是pivot的最终位置
    A[low] = pivot;     //放入最终位置
    return low;     //返回存放枢轴的最终位置
}

void QuickSort(ElemType A[], int low, int high) {
    if(low >= high) {   //不能划分了，递归出口
        return;
    }
    int pivotpos = Partition(A, low, high);     //划分
    QuickSort(A, low, pivotpos-1);      //依次对两个子表进行递归排序划分
    QuickSort(A, pivotpos+1, high);
}

• 性能分析：
  • 空间效率：O(\(log_2n\))
    递归需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。
    • 最好情况：⌈\(log_2(n+1)\)⌉
    • 最坏情况：O(n)
    • 平均情况：O(\(log_2n\))
  • 时间效率：O(\(nlog_2n\))
    递推方程：T[n] = 2T[n/2] + O(n) ，故时间复杂度为O(nlogn)
    快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。
    • 最好情况：O(\(nlog_2n\)) (对称，即大于、小于枢轴的个数相等)
    • 最坏情况：O(\(n^2\)) (基本有序或基本逆序)
    • 平均情况：O(\(nlog_2n\))
      

      推导过程：
      T[2^k]=2T[2^{k-1}]+O(n)
      S(k)=2S(k-1)+O(2^k)
      S(k-1)=2S(k-2)+O(2^{k-1})
      …
      S(1)=2S(0)+O(2^1)
      ∴S(k)=2^{k-1}S(0)+[O(2^k)+2O(2^{k-1})+…+2^{k-1}O(2)]
      ∴S(k)=2^{k-1}S(0)+kO(2^k)
      ∴T[2^k]=S(k)=2^{k-1}S(0)+kO(2^k)
      ∴T[n]=kn=nlogn

  • 稳定性：不稳定
    在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左区间后，它们的相对位置会发生变化。
  • 适用性：
    适用于顺序存储的线性表。
    适用于数据量较大的排序表。

选择排序

简单选择排序

• 基本思想：
  假设排序表为L[1…n]，第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。
• 具体操作：
  非常好理解的排序算法，就是从无序的序列中，找到一个最小的，放在新序列中，然后从剩下的序列中再找到最小的，放在新序列第一个后面，以此类推，直到所有原序列所有元素全部选择完毕即可
• 具体实现：

//对表A做简单选择排序，A[]从0开始存放元素
void SelectSort(ElemType A[], int n) {
    for(i=0; i<n-1; i++) {      //一共进行n-1趟
        min = i;                //记录最小元素的位置
        for(j=i+1; j<n; j++) {  //在A[i...n-1]中选择最小的元素
            if(A[j] < A[min]) { //更新最小元素位置
                min = j;
            }
            if(min != i) {      //与第i个位置交换
                swap(A[i], A[min]);
            }
        }
    }
}

• 性能分析：
  • 空间效率：O(1)
    仅使用常数个辅助单元
  • 时间效率：O(\(n^2\))
    元素间比较次数与序列的初始状态无关，始终是n(n-1)/2次。
    • 最好情况：O(\(n^2\))
    • 最坏情况：O(\(n^2\))
    • 平均情况：O(\(n^2\))
  • 稳定性：不稳定
    在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。
  • 适用性：
    适用于顺序存储的线性表。
    适用于数据量较小的排序表和记录本身信息量较大的排序表。
    PS：当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

堆排序

简单选择排序每次选择一个最小元素放在前面，想要提高排序速度，就要快速找到最小元，所以引入了堆，更快速地找到最小元。
堆排序是一种树形选择排序方法，其特点是：在排序过程中，将L[1…n]视为一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点的内在关系，在当前无序区中选择关键字最大（或最小）的元素。经常被用来实现优先级队列。

注意：从根结点到任意结点路径上的结点序列具有有序性。
堆排序因为是一种排序，所以它是在原有序列（顺序存储的完全二叉树）上进行调整，而不是一个一个插入。

• 基本思想：
  堆排序的关键是构造初始堆，对初始序列建堆，是一个反复筛选的过程。
  n个结点的完全二叉树，最后一个结点是第⌊n/2⌋个结点的孩子（即⌊n/2⌋是最后一个分支结点，即最后一个非叶子结点）。

  原因：由完全二叉树的性质，最后一个结点为第n个结点，那么它的父亲（即 最后一个分支结点）肯定是⌊n/2⌋。如 i结点的左孩子2i，右孩子2i+1。

  1. 建堆
     对第⌊n/2⌋个结点为根的子树筛选（对于大根堆，若根节点的关键字小于左右孩子中的较大者，则交换，即让最大的当根节点），使该子树称为堆。之后向前依次对各节点（⌊n/2⌋-1 ~ 1）为根的子树（不止是本身与左右孩子，还有下面延伸的所有结点）进行筛选，取自己与左右孩子之间的较大值为根，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根节点。
  2. 堆排序（注意：堆可以看成一棵完全二叉树，所以其顺序存储时从下标为1开始存，所以用0暂存）
     首先将存放在L[1…n]中的n个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根节点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此反复，知道堆中仅剩下一个元素为止。
• 具体操作：
  堆可以看成是一棵完全二叉树，特点是父亲大孩子小，或者父亲小孩子大，前者称为大顶堆，后者称为小顶堆
  这里简单描述一下堆排序的步骤，详情可参考教材：
  
  
  
  1. 将线性序列建立为一棵完全二叉树，依次摆放，然后根据堆的定义，调整堆的结构（向下调整）（从最后一个分支结点⌊n/2⌋开始调整），最终使得根节点为最大（或最小）
  2. 在树中删除这个根节点，将最底层中最右边的（事实上也就是线性序列中最后面那个）叶子节点放到根部（实质上就是与根节点进行交换）（即 最大元素换在末端，也就是其最终位置上了）组成新堆
  3. 新建立的堆再进行一次堆排序，以此类推，最后可得到有序序列
• 注意：
  如果使用最小堆，删除最小元素循环n次存入临时数组A[]中，最后还需要将临时数组中的元素存入原数组，那么还需要额外的数组存它，所以空间复杂度要O(n)

  如果使用最大堆，那么根结点的最大元素（排序应该放在最后一个位置）可以与最后一个元素互换，来放置到最终位置，然后调整堆，无需额外的存储空间。即 每次筛选一个最大的放在最后面。

具体实现：

• 向下调整堆：（建堆或删除堆顶元素时可用）（最小堆大的往下调，最大堆小的往下调）
  （将k结点依次向下一层一层的与左右孩子比较，进行调整，直到到达最终位置）
  （其实就是将k沿着最比它大（小）的路径向下进行调整（即 沿着这条路径中的有序结点序列进行排序），将k结点送到最终位置）
  （调整k的子树）
  （调整所有接受了调整的结点的子树）
  （不仅是左右孩子，所有下辈都算）
  （如 第一步调整了k，k与左右孩子较大值i交换了，那么接下来就调整k（此时的k与i交换了）的子树，一层一层往下调整）

//函数AdjustDown将元素k向下进行调整
void AdjustDown(ElemType A[], int k, int len) {
    A[0] = A[k];        //A[0]暂存        此时k为根节点
    for(i=2*k; i<=len; i*=2) {      //沿key较大的子结点向下筛选
    //i为2k，即i为k的左子节点
        if(i<len && A[i]<A[i+1]) {      //A[i] < A[i+1]，即左子结点小于右子结点
            i++;        //取key较大的子结点的下标
        }
        if(A[0] >= A[i]) {      //根节点大于左右孩子中的较大值，筛选结束
            break;
        }else {     //根节点小于左右孩子中的较大值
            A[k] = A[i];        //将A[i]（较大值）调整到双亲结点上，（这一步仅调整了它与左右孩子还没调整完它的子树）
            //（交换后可能会破坏下一级的堆）
            k = i;              //修改k值，取之前较大的孩子结点的位置，以便继续向下筛选出较大值并调整（即 调整k的子树）（不仅是左右孩子，所有下辈都算）
        }
    }//循环结束后，k指向了被筛选结点的最终位置
    A[k] = A[0];        //被筛选的结点值放入最终位置
}

• 向上调整堆：（对堆进行插入操作时可用）
  （其实是将k沿着该结点k到根结点的路径向上进行调整，（即 沿着这条路径中的有序的结点序列进行排序，将k结点送到最终位置）
  （依次排下来堆的性质不会被破坏）

//函数AdjustUp将元素k向上进行调整
void AdjustUp(ElemType A[], int k) {
//参数k为向上调整的结点，也为堆的元素个数（因为插入时新结点先放在堆的末端）
    A[0] = A[k];    //A[0]暂存 把k当指针用
    int i = k/2;    //i为k的双亲结点
    while(i>0 && A[i]<A[0]) {   //若结点值大于双亲结点，则将双亲结点下调，并继续向上比较
        A[k] = A[i];        //双亲结点i下调到子结点k
        //（上调后不会破坏上一级的堆）因为向上调整其实是沿着该结点到根结点的路径进行排序
        k = i;              //k指向双亲结点i
        i = k/2;            //i取此时的k的双亲结点，继续向上比较
    }//循环结束后，k指向了被筛选结点的最终位置
    A[k] = A[0];            //复制到最终位置
}

• 建堆：

//建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
    for(int i=len/2; i>0; i--) {    //从i=[n/2] ~ 1，反复向下调整堆
        AdjustDown(A, i, len);
    }
}

• 堆排序：

//堆排序
void HeapSort(ElemType A[], int len) {
    BuildMaxHeap(A, len);       //建立初始大顶堆堆
    for(i=len; i>1; i--) {      //n-1趟的交换和调整过程
        Swap(A[i], A[1]);       //输出堆顶元素（并和堆底元素交换）
        AdjustDown(A, 1, i-1);  //调整，把剩余的i-1个元素调整成大顶堆
    }
}

• 性能分析：
  • 空间效率：O(1)
    仅使用了常数个辅助单元。
  • 时间效率：O(\(nlog_2n\))
    向下调整的时间与树高有关，为O(h)。建堆时间为O(n)（即 树中各结点的高度和)，之后又n-1次向下调整操作，每次调整的时间复杂度为O(h)
    • 最好情况：O(\(nlog_2n\))
    • 最坏情况：O(\(nlog_2n\))
    • 平均情况：O(\(nlog_2n\))
  • 稳定性：不稳定
    进行筛选时，有可能把后面相同关键字的元素调整到前面。
  • 适用性：
    适用于线性表
    适用于数据量较大的排序表。

归并排序

• 基本思想：
  “归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。
  假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到\(⌈n/2⌉\)个长度为2或1的有序表；再两两归并……如此重复，知道合并成一个长度为n的有序表位置，这种排序方法称为2路归并排序

  递归形式的2路归并排序算法是基于分治的。
  分解：将含有n个元素的待排序表分成各含\(n/2\)个元素的子表，采用2路归并排序算法对两个子表递归地进行排序。
  合并：合并两个已排序的子表得到排序结果。

• 具体操作：
  将原始序列分组，再两两归并到一起（即 两个有序组从头开始元素依次比较，取最小元素放入新的有序组），形成新的有序组，再进行两两归并，以此类推，最后会归并到一组。
• 具体实现：

//表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表（合并过程中排序）
ElemType *B = (ElemType *)malloc((n+1)*sizeof(ElemType));   //辅助数组B
void Merge(ElemType A[], int low, int mid, int high) {
    for(int k=low; k<=high; k++) {
        B[k] = A[k];        //将A中所有元素复制到B中
    }
    for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++) {
        if(B[i]<=B[j]) {    //比较B的左右两段中的元素
            A[k] = B[i++];  //将较小值复制到A中
        }else {
            A[k] = B[j++];
        }
    }
    while(i <= mid) {       //若有的表中还有元素尚未检测完，全部放入A中
        A[k++] = B[i++];
    }
    while(j <= high) {
        A[k++] = B[j++];
    }
}
//将A归并排序
void MergeSort(ElemType A[], int low, int high) {
    if(low >= high) {       //不能再继续分解了
        return;
    }
    int mid = (low+high)/2;     //分解：从中间划分两个子序列
    MergeSort(A, low, mid);     //对左侧子序列进行递归排序
    MergeSort(A, mid+1, high);  //对右侧子序列进行递归排序

    Merge(A, low, mid, high);   //归并（并排序）
}

• 性能分析：

  • 空间效率：O(n)
    Merge()操作中，两个有序组从头开始元素依次比较，取最小元素放入新的有序组，新的有序组辅助空间刚好占用n个单元
  • 时间效率：O(\(nlog_2n\))
    每趟归并的时间复杂度为O(n)，共需进行\(⌈log_2n⌉\)趟归并
    • 最好情况：O(\(nlog_2n\))
    • 最坏情况：O(\(nlog_2n\))
    • 平均情况：O(\(nlog_2n\))
  • 稳定性：稳定
    由于Merge()操作不会改变相同关键字记录的相对次序
  • 适用性：
    适用于顺序存储的线性表。
    适用于数据量较大且要求排序稳定的排序表。

    PS:以上排序都是基于比较的排序方法，每次比较两个关键字大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(\(nlog_2n\))的时间。

对于任意序列进行基于比较的排序，求最少的比较次数，应考虑最坏情况。
对任意n个关键字排序的比较次数至少为\(⌈log_2(n!)⌉\)。
上述公式证明如下：在基于比较的排序方法中，每次比较两个关键字后，仅出现两种可能的转移（换或不换）。假设整个排序过程至少需要做t次比较，则显然会有\(2^t\)种情况。由于n个记录共有n!（\(A^n_n\)）种不同的排列，因而必须有n!种不同的比较路径，于是有\(2^t≥n!\)，即\(t≥log_2(n!)\)。考虑到t为整数，故为\(⌈log_2(n!)⌉\)。

基数排序

由每个数都分一个存储单元的桶排序(Bucket)而来。

基数排序分为最高位优先(MSD, Most Significant Dight)（即 从最高位开始向最低位排序）和最低位排序(LSD, Least Significant Dight)（即 从最低位开始向最高位排序）

• 基本思想：
  基数排序是一种很特别的排序方法，它不基于比较进行排序，而采用多关键字排序思想（即基于关键字各位的大小进行排序）。
  将每个位数排好序，由低到高(由高到低)，以r为基代表有r个桶。基数为进制的基数。
  这种排序是针对多关键字的情况，对于不同的关键字，例如数字，就分成0-9个“桶”，将每个元素放在与其对应关键字的“桶”内，然后就能得到有序的序列。可分为最低位优先和最高位优先两种方式
  最经典的例子就是麻将和扑克，例如麻将，有“万”“条”“筒”“风”“杂牌（中发白等）”，而且“万”“条”“筒”还分1-9，因此非常适合用这种排序方式，下面分别对最低位优先和最高位优先两种排序方式分别进行介绍（只讨论万筒条的情况）
  • 最高位优先就是，通过花色排序可将麻将不同花色放进这三种不同的“桶”内，然后对初步区分好的花色牌再按照数字1-9进行排序，则可将整副麻将变得有序
  • 最低位优先就是，先将麻将按照1-9放进不同的桶内，然后在根据花色将1-9桶的麻将依次放进这三种花色桶内，这样整幅麻将就变得有序
• 具体操作：
  一般基数r为10，通常我们都是使用基数为10，就是每次对%10取余，可以为其他的值嘛，比如说8，也是可以的，只是隐形的讲10进制转化为8进制而已
  每趟分为分配(把序列分到每个桶里面去)与收集(把每个桶里面的元素拿出来合成一个序列)两部分。（“桶”其实就是“竖着的队列”）
  往桶里面分配的时候，是从桶口向里面放；
  向桶外面收集的时候，是从桶底向外面拿。

  总结：上进下出

• 性能分析：
  • 空间效率：O(r)
    一趟排序需要的辅助空间为r(r个队列)(桶)，但以后的排序中会重复使用这些队列
  • 时间效率：O(d(n+r))
    基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)
    d为关键字位数，n为关键字个数，r（基数，radix）为进制的取值范围（如十进制为0~9）
    • 最好情况：O(d(n+r))
    • 最坏情况：O(d(n+r))
    • 平均情况：O(d(n+r))
  • 稳定性：稳定
    对于基数排序算法而言，按位排序是必须是稳定的，所以保证了基数排序的稳定性
  • 适用性：
    适用于顺序存储的线性表
    适用于数据量很大但记录的关键字位数较少且可以分解的排序表
    适用于多关键字排序

总结

• 关于时间复杂度：
  1. 初始序列越无序，快速排序的效率越高，最高为O(nlog2n)
     初始序列越有序，快速排序的效率最低，最低为O(n^2)
  2. 堆排序和归并排序的时间复杂度与初始序列无关，都为O(nlog2n)
  3. 二路归并排序效率高，而且稳定，但是它的缺点是需要额外的存储空间
  4. 选择类排序适合数据量比较大的场合，因为它是通过大量的比较后选择明确的记录进行有目的的移动
• 不同条件下，排序方法的选择：
  1. 若n较小(如n≤50)，可采用直接插入或直接选择排序
     当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，因选择直接选择排序为宜
  2. 若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序为宜；
  3. 若n较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序
     • 快速排序是目前基于比较的内部排序中被认为是最好的方法，当排序的关键字是随机分布时，快速排序的平均时间最短
     • 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。但这两种排序都是不稳定的。
     • 若要求排序稳定，则可使用归并排序。
  4. 关键字随机分布时，任何基于“比较”的排序算法，至少需要O(nlogn)的时间
• 总结：
  • 不稳定：希尔排序、快速排序、简单选择排序、堆排序
  • 时间复杂度O(nlogn)：快速排序、堆排序、归并排序
  • 每趟排序结束后能够确定一个元素最终位置：冒泡排序、快速排序、简单选择排序、堆排序
  • 平均性能最好：快速排序
  • 总排序趟数与初始状态无关的有：（除了快速排序和优化的冒泡，其他都是）
  • 算法复杂度与初始状态无关的有：堆排序、归并排序、选择排序、基数排序。
  • 元素总比较次数与初始状态无关的有：选择排序、基数排序。
  • 元素总移动次数与初始状态无关的有：归并排序、基数排序。

表排序

要排序结构体这种信息量很大的数据，如果每次都要移动，花费很高。所以设立表指针，只用移动表指针。

• 间接排序
  定义一个指针数组作为“表”（table）
• 物理排序
  N个数字的排列由若干个独立的环组成。
• 性能分析：
  • 时间效率：
    • 最好情况：初始即有序
    • 最坏情况：有N/2个环，每个环包含2个元素，需要3N/2次元素移动T = O(mN)，m是每个A元素的复制时间。

外部排序

当所要排序的的数据量太多或者文件太大，无法直接在内存里排序，而需要依赖外部设备时，就会使用到外部排序。

多路归并排序

• 算法描述：
  假设文件需要分成k块读入，需要从小到大进行排序。
• 具体操作：
  1. 依次读入每个文件块，在内存中对当前文件块进行排序（应用恰当的内排序算法），此时，每块文件相当于一个由小到大排列的有序队列；
  2. 在内存中建立一个最小堆，读入每块文件的队列头；
  3. 弹出堆顶元素，如果元素来自第i块，则从第i块文件中补充一个元素到最小值堆。弹出的元素暂存至临时数组；
  4. 当临时数组存满时，将数组写至磁盘，并清空数组内容；
  5. 重复过程3、4，直至所有文件块读取完毕。

文章永久链接：https://tech.souyunku.com/19987