排序（插入排序、快排、归并、基数排序）

这篇文章是我在学习数据结构时作笔记的用途，这篇文章会纪录下我学习的几种排序算法，以及在学习的时候会加上配图说明！

相关的定义和基础

如果某组信息在内存空间中存储，则称为表(list)。如果存储于外存中则称为文件(file)。把信息中的对象称为记录，每个记录的信息划分为更小的单元，称为域。
  顺序查找对关键字域没有任何限制，而折半查找需要关键字有序的排列。其中折半查找可以使用二叉查找树来描述。

⚠️二叉查找树的特征
其左子树不大于根节点值，右子树不小于根节点值。而且各个子树还是一棵二叉查找树。

内部排序是指在表的规模足够小，能够全部放在内存中排序的方法。外部排序指数据规模太大，不能全部放在内存中时。这篇文章中我主要纪录的是内部排序算法，其中包含了：插入排序、快速排序、堆排序、归并排序、基数排序。

插入排序

插入排序类似于玩纸牌时，每次拿一张牌，将这张牌放在合适的位置，使手中所有纸牌按顺序排列。

void insertion_sort(ele list[], int n){
    /// 最坏情况时间复杂度：O(n*n)
    int i,j;
    ele next;
    for (i = 1; i < n; i++) {
        next = list[i];
        for (j = i - 1; j >= 0 && next.key < list[j].key; j--) {/// 说明不是按照升序排列
            list[j+1] = list[j];
        }
        list[j+1] = next;
    }
}

最坏情况的时间复杂度为：O(n*n)，还可以通过检查输入表的相对无序性来估计插入排序的计算时间。为了计算相对无序性，需要测量每个记录是左无序(LOO)的区域长度。
如果为左无序记录的个数，则插入排序的计算时间为O((k+1)n)。

⚠️插入排序适用范围：
当只有少数纪录是LOO纪录时，插入排序的运行效果很好。

快速排序

快速排序是平均时间性能非常好的排序方法。在学习快速排序时借鉴了阮一峰的解读、坐在马桶上学算法和排序算法动画演示。

• 1.找一个基准点（一般是第一个元素），把小于该基准点的放在左边称为S1，大于基准点的放在右边称为S2。将S1中找一个基准点，然后做和上面类似的，左边称为S1-1，然后一直递归下去S1-1-...1。右边称为S1-2。同理递归操作集合中其他的元素。

• 2.在上一条中提到的基准点，我说一般是第一个元素，这里说一下时间复杂度为O(n*n)的情况，如果在排序之前该组数据已经是有序排列（升序和降序）的情况。那么怎么选择基准点呢？一般是找最右边和最左边和中间数字找一个中位数。

图解分析

测试一组数据：26,5,37,1,61,11,59,14,48,19,55;下图中提到的i,j在图中可能看得不清楚，所以我说明一下：i 用于纪录在一次移动过程中小于基准点数据的下标。j 则相反，它是纪录大于基准点数据的下标。

• 1）、第一次以26为基准点的元素移动情况：

自此以第一个为基准点的元素移动完成，需要注意的是：先由i移动，当i移动停止时，移动j。在i和j的移动完成之后，需要i<j才能进行位置交换。

• 2）、上一步得到的最后序列中操作26左边部分的的元素：11、5、19、1、14。
  

  

• 3）、同样来操作26左边部分的的元素：59、61、48、37、55。

• 4）、通过上诉三步得到如下结果，然后使用递归的方式分别对基准点11、59的左右元素进行相同的排序操作。

最后结果如下：

最后结果

编码实现

C语言实现

void quick_sort(int list[], int left, int right);
void quicksort(int list[], int n){
    quick_sort(list, 0, n - 1);
}

void swap(int *lhs,int *rhs){
    int temp = *lhs;
    *lhs = *rhs;
    *rhs = temp;
}
#define AfterMove 1
void quick_sort(int list[], int left, int right){
    
    if (left >= right) {
        return;
    }
    int pivot = list[left];/// 这里我就简单的取最左边为基准点
#if AfterMove
    /// 哨兵i,j
    int i = left + 1;
    int j = right;
    while (i < j) {
        /// 先移动i
        while (list[i] < pivot) {
            i++;
        }///找出当前不满足条件的元素所在的位置
        /// 再移动j
        while (list[j] > pivot) {
            j--;
        }
        if (i < j) {/// 进行元素位置互换
            swap((list + i), (list + j));
        }
    }
    if (*(list + left) > *(list + j)) {
        swap((list + left), (list + j));
    }
#else
    /// 哨兵i,j
    int i = left;
    int j = right + 1;
    do {
        /// 先移动i
        while (list[++i] < pivot) {}///找出当前不满足条件的元素所在的位置
        /// 再移动j
        while (list[--j] > pivot) {}
        if (i < j) {/// 进行元素位置互换
            swap((list + i), (list + j));
        }
    } while (i < j);
    /// 交换基准点和j位置元素
    swap((list + left), (list + j));
#endif
    /// 递归处理当前基准点左右两边元素
    quick_sort(list, left, j-1);/// 左边
    quick_sort(list, j+1, right);/// 右边
}

调用，以及最后的结果打印：

int list[11] = {26,5,37,1,61,11,59,14,48,19,55};
quicksort(list, 11);
for (int i = 0; i < 11; i++) {
  printf("Quick Sort Result is :%d\n",list[i]);
}
Quick Sort Result is :1
Quick Sort Result is :5
Quick Sort Result is :11
Quick Sort Result is :14
Quick Sort Result is :19
Quick Sort Result is :26
Quick Sort Result is :37
Quick Sort Result is :48
Quick Sort Result is :55
Quick Sort Result is :59
Quick Sort Result is :61

Swift实现

swift -v
Apple Swift version 3.1 (swiftlang-802.0.53 clang-802.0.42)

var list:Array<Int> =  [19,30,1,5,13,37,15,29,40,5]

func QuicSort(list:inout Array<Int>){
    __quick_sort(list: &list, left: 0, right: list.count - 1)
}

func __swap(_ lhs:inout Int,_ rhs:inout Int){
    let tmp = lhs
    lhs = rhs
    rhs = tmp
}

func __quick_sort(list:inout Array<Int> ,left:Int ,right:Int) -> Void{
    if left >= right {
        return
    }
    var pivot:Int = list[left]
    /**
    var i:Int = left + 1
    var j:Int = right
    while i < j {
        while list[i] < pivot {
            i = i + 1
        }
        while list[j] > pivot {
            j = j - 1
        }

        if i < j {
            __swap(&list[i], &list[j])
        }
    }
    if list[left] > list[j] {
        __swap(&list[left], &list[j])
    }
    */
    var i:Int = left
    var j:Int = right+1
    
    while i < j{
        repeat{
            i = i + 1
        }while list[i] < pivot
        
        repeat{
            j = j - 1
        }while list[j] > pivot
        
        if i < j {
            __swap(&list[i], &list[j])
        }
    }
    __swap(&list[left], &list[j])
 
    __quick_sort(list: &list, left: left, right:j - 1)/// 左边
    __quick_sort(list: &list, left: j + 1, right: right)/// 右边
}

QuicSort(list: &list)
print(list)/// [1, 5, 5, 13, 15, 19, 29, 30, 37, 40]

归并排序

归并排序：也是递归（迭代）、合并排序。主要是经过两步，将一组元素分解成多个子序列，然后使用递归或者迭代的方式合并成一个整体序列，在合并的过程对每个子序列进行排序。

将一组无序的序列分解成多个子序列

/// 将一个数组分割成length为1的n个子序列（n为原数组长度），第一步分割子序列
void __merge_sort(int list[], int n){
    int length = 1;
    int tmp_list[n];
    /// 做分割序列，并对每个子序列进行合并
    while (length < n) {
        __merge_pass(list, tmp_list, length, n);
        length *= 2;
        __merge_pass(tmp_list, list, length, n);
        length *= 2;
    }
}

将子序列合并

void __merge_pass(int list[], int tmp[], int length, int n){
    /// 将子序列两两进行merge
    int i;
    for (i = 0; i < n - 2*length; i += 2*length) {
        __merge(list, tmp, i, i + length, i + 2*length - 1);
    }
    
    if (i + length < n) {/// 说明当前这个子序列，后面还跟了一个子序列（<n）。所以需要merge最后两个子序列
        __merge(list, tmp, i, i + length, n - 1);
    }else{/// 当前只有一个子序列，直接放入即可
        for (int j = i; j < n; j++) {
            tmp[j] = list[j];
        }
    }
}

在合并子序列时候进行排序

/// ls := left_start
/// rs := right_start
/// re := right_end
void __merge(int list[], int tmp[],int ls,int rs,int re){
    int i,j;
    i = ls;
    j = rs;
    int k = i;/// tmp的下标标量
    while (i < rs && j <= re) {
        tmp[k++] = list[i] <= list[j] ? list[i++] : list[j++];
    }
    while (i < rs) {
        tmp[k++] = list[i++];
    }
    while (j <= re) {
        tmp[k++] = list[j++];
    }
}

调用

int merge_list[10] = {26,5,77,1,61,11,59,15,48,19};
__merge_sort(merge_list, 10);
for (int i = 0; i < 10; i++) {
  printf("merge_list Sort Result is :%d\n",merge_list[i]);
}

归并排序存在的最大问题就是需要一个额外的空间来进行排序！

堆排序

堆排序放在最大堆一节做说明！

基数排序

对于基数排序，其中有两个重要的概念，分别是：MSD（主位优先排序）、LSD（次位优先排序）。什么会有这两种不同的排序方式呢？因为基数排序主要是针对于待排序列纪录中存在多个关键字。针对这不同的关键字，导致我们在排序时可以有主位和次位之分！
  在基数排序中，把排序关键字用基数r分解为多个数位。当r=10时，就得到十进制的分解结果。当r=2时，就得到二进制的分解结果。
  下面通过一系列十进制数排序来说明一下基数排序。在排序的一系列数字中最大为3位数:
[179、208、306、93、859、984、55、9、271、33

• 1）、 第一遍排序个位数
  将上诉的数字根据个位数的大小，分别填入对应的链表中。比如当个位数是9的数字有179，859，9三个数字，每扫描一边数字将前一个数字的link字段赋值为当前数字，在下面代码中展示的并不是直接使用ptr->link = ptr，而是用front数组来保存第一个元素，并由rear数组来更新相应的链表link字段（具体代码可看下面👇地代码实现）。
  在放入各自链表完成之后，我们需要根据现有的顺序，重新放入ptr指针中，以便进行根据十位上的数字再进行一次排序

271 -> 93 -> 33 -> 984 -> 55 -> 306 -> 208 -> 179 -> 859 -> 9

• 2）、 对十位上的数字进行排序
  经过第一排序之后得到数字序列，并对该序列上的数字根据十位上的数字同第一步一样再进心排序，得到的结果是:

306 -> 208 -> 9 -> 33 -> 55 -> 859 -> 271 ->179 ->984 -> 93

• 3）、对百位上的数字进行排序
  同样是根据上一步得到的顺序，在该序列的基础上对序列中数字百位上的数字排序，结果如下：

9 -> 33 -> 55 -> 93 -> 179 -> 208 -> 271 -> 306 -> 859 -> 984

可以看出在前面三步完成之后，能够正确将原序列经过从小到大的顺序排序。

代码实现

#undef MAX_DIGIT
#define MAX_DIGIT 3

#undef RADIX_SIZE
#define RADIX_SIZE 10

typedef struct __list_node* list_node_ptr;
typedef struct __list_node{
    int key;
    list_node_ptr link;
}list_node;

/// 排序数字中最多由三位数字组成
list_node_ptr digit_sort(list_node_ptr ptr){
    if (!ptr) {
        return NULL;
    }
    list_node_ptr front[RADIX_SIZE],rear[RADIX_SIZE];
    ///1.基数排序，使用lsd排序，需要有三个基数：从个位数，十位数，百位数
    int digit,k;
    for (int i = 0; i < MAX_DIGIT; i++) {
        for (k = 0; k < RADIX_SIZE; k++) {
            front[k] = rear[k] = NULL;
        }
        ///2.依次放入上一次顺序排列的数列
        for (; ptr; ptr = ptr -> link) {
            digit = (ptr->key/(int)pow(10, i))%10;/// 拿出该数字中第个／十／百位上的数字
            if (!front[digit]) {
                front[digit] = ptr;/// 保证该数位上有数据时，front数组对应的链表元素指向第一个
            }else{
                rear[digit]->link = ptr;/// 这一步实际上是纪录ptr->link的
            }
            rear[digit] = ptr;///rear始终只想该链表的最后一个数据
        }
        ptr = NULL;
        ///3.每一轮按照基数放在对应的数组里面之后，需要将其取出，按照在front数组中的顺序链接ptr
        for (k = RADIX_SIZE - 1; k >= 0; i--) {
            /// 这里解释一下为什么要用倒叙的方式？为了让代码简单，我们从位数上数字最大的开始，依次向前来链接链表
            rear[k]->link = ptr;
            ptr = front[k];
        }
    }
    return ptr;
}

内部排序总结

排序算法	平均时间复杂度	最坏时间复杂度	额外空间复杂度	稳定性
插入排序	O(N*N)	O(N*N)	O(1)	稳定
快速排序	O(N*log(N))	O(N*N)	O(log(N))	不稳定
归并排序	O(N*log(N))	O(N*log(N))	O(N)	稳定
堆排序	O(N*log(N))	O(N*log(N))	O(1)	不稳定
基数排序	O(P(N+B))	O(P(N+B))	O(N+B)	稳定

说明：
1、由于快速排序是递归进行的，所以额外的空间复杂度是O(log(N))；
2、归并排序由于需要一个额外的temp_list，故其空间复杂度为O(N)；
3、由于快速排序、归并排序和堆排序的时间复杂度都是O(N*log(N))，但是由于快速排序的前面系数很小。平均时间性能，快速排序是最好的；

具体的使用场景：

• 1、当输入序列部分有序时，选择插入排序；
• 2、基数排序的时间复杂度取决于关键字的规模和基数的选取；
• 3、快速排序的基准点选取也直接影响排序的时间性能；

因此在实际使用中，把插入排序、快速排序和归并排序结合使用，即在归并排序中使用快速排序来处理子序列，而在快速排序中使用插入排序处理在其递归过程中的子序列。