排序的基本概念和分类

• 排序的稳定性
  

  举例说明，如下图所示，令狐冲和张无忌总分相同，稳定排序指排序之后，令狐冲仍然在张无忌前面；不稳定排序指令狐冲到张无忌后面了

• 内排序与外排序
  内排序是在排序的整个过程中，待排序的所有记录全部被放置在内存中
  外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行

• 排序用到的结构与函数
  排序最常用到的操作是数组两元素的交换，我们将它写成函数，在之后讲解中会大量用到

// 交换数组中下标为 i 和 j 的值
void swap(int array[], int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

主函数，想测试下列函数可以用此测试节省时间

#include<iostream>
#include<vector>
using namespace std;

int main(){
    // int array[10] = {5, 1, -3, 8, 99, -6};
    // int length = 6;
    
    int array[10] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int length = 9;
    // 此处 xxx 为待测排序函数的名称
    xxx(array, length);
    for(int i=0; i < length; i++){
        cout<<array[i]<<" ";
    }
    cout<<endl;
}

冒泡排序

冒泡排序 (Bubble Sort) 一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

• 最简单的排序实现

// 冒泡排序初级版
void Bubble(int array[], int length){
    for(int i=0; i < length-1; i++){
        for(int j=i+1; j < length; j++){
            if(array[i] > array[j]){
                swap(array, i, j);
            }
        }
    }
}

这段代码严格意义上说，不算是标准的冒泡排序算法，因为它不满足 "两两比较相邻记录" 的冒泡排序思想，它更应该是最最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。如下图所示，假设我们待排序的关键字序列是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，当 i=1 时，9 与 1 交换，在第一位置的 1 与后面的关键字比较都小，因此它就是最小值。当 i=2 时，第二位置先后由 9 换为 5，换为 3，换为 2，完成了第二小的数字交换。后面的数字交换类似，不再介绍。

这应该是最最容易写出的排序代码了，不过这个简单易懂的代码，却是有缺陷的。观察后发现，在排序好 1 和 2 的位置后，对其余关键字的排序没有什么帮助 (数字 3 反而还被换到了最后一位)。也就是说这个算法的效率时非常低的。

• 冒泡排序算法
  1，把小的逐步冒泡到数组前面

// 正宗的冒泡排序
void Bubble(int array[], int length){
    for(int i=0; i < length-1; i++){
        // 注意 j 是从后往前循环
        for(int j=length-2; j >= i; j--){
            // 若前者大于后者就交换两者值
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
            }
        }
    }
}

依然假设我们待排序的关键字序列是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，当 i=1 时，变量 j 由 8 反向循环到 1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第 1 的位置。如下图所示，当 i=1,j=8 时，我们发现 6>2，因此交换了它们的位置，j=7 时，4>2，所以交换 .... 直到 j=2 时，因为 1 < 2 ，所以不交换。j=1 时，9>1，交换，最终得到最小值 1 放置第一位置。事实上，在不断循环的过程中，除了将关键字 1 放到第一位置上，我们还将关键字 2 从第九位置提到了第三位置，显然这一算法比前面的要有进步，在上十万条数据的排序过程中，这种差异会体现出来。图中较小的数字如同气泡般慢慢浮到上面，因此将此算法命名为冒泡排序.

当 i=2 时，变量 j 由 8 反向循环到 2，逐个比较，在将关键字 2 交换到第二位置的同时，也将关键字 4 和 3 有所提升 后面数字交换很简单，在这里不再详述

2，把大数逐步冒泡到数组后面

// 正宗的冒泡排序
void Bubble(int array[], int length){
    for(int i=1; i < length; i++){
        // 注意 j 是从前往后循环
        for(int j=0; j < length-i; j++){
            // 若前者大于后者就交换两者值
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
            }
        }
    }
}

• 冒泡排序优化
  

  上述正宗冒泡排序算法是否还可以优化呢？ 答案是肯定的。试想一下，如果我们待排序的序列是 {2, 1, 3, 4, 5, 6, 7, 8, 9} ，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序了。当 i=1 时，交换了 2 和 1，此时序列已经有序，但是算法仍然不依不饶地将 i=2 到 9 以及每个循环中的 j 循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了，如下图所示
  当 i=2 时，我们已经对 9 与 8，8 与 7，.....，3 与 2 作了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循环判断工作了。为了实现这个想法，我们需要改进一下代码，增加一个标记变量 flag 来实现这一算法的改进

// 优化之后的冒泡排序
void Bubble(int array[], int length){
    bool flag = true;
    for(int i=0; i < length-1 && flag; i++){
        flag = false;
        for(int j=length-2; j >= i; j--){
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
                flag = true;
            }
        }
    }
}

代码改动的关键就是在 i 变量的 for 循环中，增加了对 flag 是否为 true 的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断

• 冒泡排序复杂度分析
  最好情况：也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是 n-1 次的比较，没有数据交换，时间复杂度为 O(n)
  最坏情况：即待排序表时逆序的情况，此时需要比较 = 1+2+3+...+(n-1) = 次，并作等数量级的记录激动。因此总的时间复杂度为 O(n²)

简单选择排序

选择排序的基本思想是每一趟在 n-i+1(i=1, 2, ..., n-1) 个记录中选取关键字最小的记录作为有序序列的第 i 个记录

• 简单选择排序算法

// 选择排序
void Select(int array[], int length){
    int min;
    for(int i=0; i < length-1; i++){ 
        min = i;                          // 将当前下标定义为最小值下标
        for(int j=i+1; j < length; j++){  // 从 i+1 开始向后循环
            // 如果有小于当前最小值的关键字，则将此关键字赋值给 min
            if(array[min] > array[j]){    
                min = j;
            }
        }
        if(min != i){  // 若 min 不等于 i ,说明在后面找到最小值，交换 
            swap(array, min, i);
        }
    }
}

• 简单选择排序复杂度分析
  从简单选择排序过程来看，它最大的特点就是交换移动次数相当少，这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差情况，其比较次数都是一样多，第 i 躺排序需要进行 n-i 次关键字的比较，此时需要比较 = n-1 + n-2 + ... + 1 = 次，而对于交换次数而言：
  最好情况：交换为 0 次
  最差情况：也就是初始降序时，交换次数为 n-1 次，基于最终的排序时间时比较与交换次数总和，因此，总的时间复杂度依然为 O(n²)
  应该说，尽管与冒泡排序同为 O(n²)，但简单选择排序的性能上还是要略优于冒泡排序

直接插入排序

直接插入排序 (Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表

• 直接插入排序算法

void InsertSort(int array[], int length){
    // 从下标为 1 的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
    for(int i=1; i < length; i++){
        int temp = array[i];         // 设置哨兵
        int j = i;
        //从已经排序的序列的最右边开始向左进行比较
        while(j > 0 && temp < array[j-1]){
            array[j] = array[j-1];   // 记录后移
            j = j - 1;
        }
        array[j] = temp;       // 插入到正确位置，如果前面都比它小，则还在原位置
    }
}

• 直接插入排序复杂度分析
  从空间上看：它只需要一个记录的辅助空间，因此关键是看它的时间复杂度
  最好情况：也就是要排序的表本身就是有序的，比如拿到数列为 {2, 3, 4, 5, 6}，其实就是代码 array[i] 与 array[i-1] 比较，共比较 n-1 次，由于每次都是 array[i] > array[i-1] ，因此没有移动的记录，时间复杂度为 O(n)
  最坏情况：时间复杂度为 O(n²)
  直接插入排序比冒泡排序和简单选择排序的性能要好一些

希尔排序 (Shell Sort)

• 希尔排序原理
  希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
  希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
• 希尔排序算法

void ShellSort(int array[], int length){
    
    // gap为步长，每次减为原来的一半
    for(int gap = length/2; gap > 0; gap /= 2){
        
         // 共 gap 个组，对每一组执行插入排序
        for(int i=0; i < gap; i++){
            for(int j=i+gap; j < length; j += gap){
                int temp = array[j];  //记录要插入的数据
                int k = j;
                // 从已经排序的序列的最右边开始比较，找到比其小的数字
                while(k >= gap && temp < array[k-gap]){
                    array[k] = array[k-gap];
                    k = k - gap;
                }
                array[k] = temp;
            }
        }
    }
}

• 希尔排序复杂度分析

堆排序

参考１ 参考２
堆排序 (Heap Sort) 就是利用堆(假设利用大顶堆) 进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走 (其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩下的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次小值。如此反复执行，便能得到一个有序序列了。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2

• 堆排序算法

void adjustHeap(int array[], int i, int length){
    int temp = array[i];
    for(int k = 2*i + 1; k < length; k = 2*k + 1){
        // 让 k 指向子节点中最大的节点
        if(k+1 < length && array[k] < array[k+1]){
            k++;
        }
        // 因此此是建立大顶堆，所以若子孩子比双亲节点大，则交换
        if(array[k] > temp){
            swap(array, i, k);
            i = k;
        }
        else{
            break; // 若双亲节点比两个子孩子都大，则不用调整直接退出循环
        }
    }
}

void HeapSort(int array[], int length){
    
    // 使用堆调整的方式来建堆，调整为最大堆
    // 按照完全二叉树的特点，从最后一个非叶子节点(数组下标为length/2-1)开始，
    //      对于整棵树进行最大堆的调整
    // 也就是说，是按照自下而上，每一层都是自右向左来进行调整的
    for(int i = length/2-1; i >= 0; i--){
        adjustHeap(array, i, length);
    }
    
    // 开始堆排序
    for(int i=length-1; i > 0; i--){
        // 说是交换，其实质就是把大顶堆的根元素，放到数组的最后
        // 换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
        // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
        // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，
        // 这也是为什么此方法放在循环里的原因
        // 而这里，实质上是自上而下，自左向右进行调整的
        swap(array, 0, i);
        adjustHeap(array, 0, i); // 将下标为 0 ~ i-1 元素重新调整为大顶堆 
    }
}

从代码中可以看出，整个排序过程分为两个 for 循环。第一个循环要完成的就是将现在的待排序序列构建成一个大顶堆。第二个 for 循环要完成的就是逐步将每个最大值的根节点与末尾元素交换，并且再调整其称为大顶堆

• 堆排序复杂度分析
  • 堆排序的运行时间最要是消耗在初始构建堆和在重建堆时的反复筛选上
  • 在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端节点开始构建，将它与其孩子进行比较和若有必要的交换，对于每个非终端节点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为 O(n)
  • 在正式排序时，第 i 次取堆顶记录重建堆需要用时 O（logi）的时间，并且需要取 n-1 次堆顶记录，因此，重建堆的时间复杂度为 O(nlogn)
    所以总体来说，堆排序的时间复杂度为 O(nlogn) 。由于堆排序对原始记录的堆排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为 O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的 O(n²) 的时间复杂度了
  • 空间复杂度上，它只有一个用来交换的暂存单元，也非常不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法
    另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况

归并排序

归并一词在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表

• 归并排序算法

#include<iostream>
#include<vector>
using namespace std;

// 交换数组中下标为 i 和 j 的值
void swap(int array[], int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

// 合并两个有序数组
void MergeArray(int data[], int first, int mid, int last, int copy[]){
    int i = first, m = mid;
    int j = mid+1, n = last;
    int k = 0;

    while(i <= m && j <= n){
        if(data[i] <= data[j]){
            copy[k++] = data[i++];
        }
        else{
            copy[k++] = data[j++];
        }
    }

    while(i <= m){
        copy[k++] = data[i++];
    }

    while(j <= n){
        copy[k++] = data[j++];
    }

    for(i = 0; i < k; i++){
        data[first + i] = copy[i];
    }
}

// 归并排序
void MergeSort(int array[], int first, int last, int copy[]){
    if(first < last){
        int mid = (first + last) >> 1;
        MergeSort(array, first, mid, copy);        // 左边有序
        MergeSort(array, mid+1, last,  copy);      // 右边有序
        MergeArray(array, first, mid, last, copy); // 再将两个有序数列合并
    } 
}

int main(){
    int array[10] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int copy[10];
    int length = 9;
   
    MergeSort(array, 0, length-1, copy);
    for(int i=0; i < length; i++){
        cout<<array[i]<<" ";
    }
    cout<<endl;
}

• 归并排序复杂度分析
  最好、最坏、平均的时间性能，时间复杂度为 O(nlogn)
  归并排序是一种比较占用内存，但却效率高且稳定的算法
• 非递归实现归并排序

快速排序

• 快速排序算法

#include<iostream>
#include<vector>
using namespace std;

// 交换数组中下标为 i 和 j 的值
void swap(int array[], int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

int QuickSortCore(int data[], int first, int last){
    int pivot = data[first];
    while(first < last){
        while(first < last && data[last] >= pivot){
            last --;
        }
        data[first] = data[last];

        while(first < last && data[first] <= pivot){
            first ++;
        }
        data[last] = data[first];
    }
    data[first] = pivot;
    return first;
}

// 快速排序
void QuickSort(int array[], int first, int last){
    
    if(first < last){
        int pivot = QuickSortCore(array, first, last);
        QuickSort(array, first, pivot-1);      
        QuickSort(array, pivot+1, last);    
    } 
}

int main(){
    int array[10] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int length = 9;
   
    QuickSort(array, 0, length-1);
    for(int i=0; i < length; i++){
        cout<<array[i]<<" ";
    }
    cout<<endl;
}

• 快速排序复杂度分析
  最好情况：时间复杂度为 O(nlogn)
  最坏情况：时间复杂度为 O(n²)
  平均情况：时间复杂度为 O(nlogn)
  就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为 log₂n ，其空间复杂度也就为 O(logn)。最坏情况，需要进行 n-1 递归调用，其空间复杂度为 O(n)。平均情况，空间复杂度为 O(logn)
• 快速排序优化
  优化选取枢轴
  优化不必要交换

总结回顾

希尔排序相当于直接插入排序的升级，它们同属于插入排序类
堆排序相当于简单选择排序的升级，它们同属于选择排序类
快速排序相当于冒泡排序的升级，它们同属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数

• 7 种算法各项指标对比

• 桶排序