排序

插入类排序

直接插入排序：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上

排序过程
元数据： 49 38 65 97 76 13 27 49
第一次排序：49 38 65 97 76 13 27 49
第二次排序：38 49 65 97 76 13 27 49
第三次排序：38 49 65 97 76 13 27 49
第四次排序：38 49 65 76 97 13 27 49
第五次排序：13 38 49 65 97 76 27 49
第六次排序：13 38 49 65 76 97 27 49
第七次排序：13 38 27 49 65 97 76 49
第八次排序：13 38 27 49 49 65 97 76

代码实现

void insertSort(int R[],int n){
    int i,j;
    int temp;
    for (i=1; i<n; i++) {
        temp = R[i];
        j = i-1;
        while (j>=0&&temp<R[j]) {
            R[j+1] = R[j];
            j--;
        }
        R[j+1] = temp;
    }
}

折半插入排序： 折半插入排序的算法和直接插入排序的算法思想类似，区别是查找插入位置的方法不同，折半插入排序是采用折半查找法来查找插入位置

元数据：13 38 49 65 76 97(有序部分)，代插入的数据：27 49
27插入流程：
low=0,high=5,m=[(0+5)/2],下标为2的关键字是49，所以应该插入到49的低半区；high=m-1,low=0
low=0,high=1,m=[(0+1)/2]=0,下标为0的关键字是13,所以应该插入到13的高半区；low=m+1,high=1
low=1,high=1,m=[(1+1)/2]=1,下标为0的关键字是38,所以应该插入到38的低半区，改变high=mid-1=0,high<low,折半查找结束，27放到high之后，即13之后，此时的序列为：
13 27 38 49 65 76 97
依照此方法插入剩余结点

希尔排序：又叫做缩小增量排序，其本质还是插入排序，只不过是将待排序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序

元数据：49 38 65 97 76 13 27 49 55 04
1)以5为增量分割序列，得到以下几个子序列
                49                        13
                      38                       27
                           65                       49
                                 97                      55
                                       76                      04
分别对5个子序列进行直接插入排序
                13                        49
                      27                      38
                           49                       65
                                 55                      97
                                       04                      76
一趟希尔排序结束，结果为：
                 13 27 49 55 04 49 38 65 97 76
2)再对上面的结果以增量3分割，得到以下几个子序列
                 13             55            38            76
                      27             04             65
                            49             49             97
分别对三个子序列进行直接插入排序
                 13             38            55            76
                      04             27             65
                            49             49             97
第二趟希尔排序结束，结果为:
                 13 04 49 38 27 49 55 65 97 76
3)最后以增量为1进行分割，即对以上结果全体的关键字进行一趟直接插入排序，结果为：
                 04 13 27 38 49 49 55 65 76 97

交换类排序

冒泡排序：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

原始序列: 49 38 65 97 76 13 27 49
一趟冒泡排序: 38 49 65 76 12 27 49 97
将最大的元素97移到了最后，之后对前n-1位进行排序:
两趟冒泡排序: 38 49 65 12 27 49 76 97
之后依次类推知道得到有序序列
三趟冒泡排序: 38 49 12 27 49 65 76 97
四趟冒泡排序: 38 12 27 49 49 65 76 97
五趟冒泡排序: 12 24 38 49 49 65 76 97

代码实现

void bubbleSort(int R[],int n){
    bool flag = false;
    int i,j;
    for (i=n-1; i>=1; i--) {
        flag = false;
        for (j = 1; j<=i; j++) {
            if (R[j-1]>R[j]) {
                int temp = R[j-1];
                R[j-1] = R[j];
                R[j] = temp;
                flag = true;
            }
        }
        if (!flag) {
            return;
        }
    }
}

快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

timg-2.jpeg
代码实现

void quickSort(int R[],int low,int high){
    int temp;
    int i = low,j=high;
    if (i<j) {
        temp=R[low];
        while (i!=j) {
            while (j>i && R[j]>temp) {
                --j;
            }
            if (i<j) {
                R[i] = R[j];
                ++i;
            }
            
            while (j>i && R[i]<temp) {
                ++i;
            }
            if (i<j) {
                R[j] = R[i];
                --j;
            }
        }
        R[i] = temp;
        quickSort(R, low, i-1);
        quickSort(R, i+1, high);
    }
}

选择类排序

简单选择排序：从头至尾顺序扫描序列，找到最小的一个关键字和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序

image.png
代码实现

void selectSort(int R[],int n){
    int i,j,k;
    for (i=0; i<n; i++) {
        k = i;
        for (j=i+1; j<n; j++) {
            if (R[j]>R[k]) {
                k = j;
            }
        }
        int temp = R[i];
        R[i] = R[k];
        R[k] = temp;
    }
}

堆排序：是指利用堆的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆可以分为大顶堆和小顶堆，若父亲大孩子小则叫做大顶堆，否则叫做小顶堆
堆的构造

image.png

插入节点

需要在插入节点后保持堆的性质，需要先将插入的结点x放到最底层的右边，满足完全二叉树的特点，然后把x依次向上调整到合适的位置以满足堆的性质

删除结点

删除结点时，原来的位置就会出现一个孔，将最底层最右面的叶子值赋值给该孔并下调到合适的位置，最后把叶子删除

排序

以上调整已经建立的一个大顶堆，对应的序列为：97 76 65 49 49 13 27 38，将97和38交换，将97移除放入有序序列中，此时把除97外的序列进行排序

image.png

依次类推，知道全部都排好序

归并类排序

二路归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
排序过程

原始数据：49 38 65 97 76 13 27

1）将原始序列看成7个只含有一个关键字的子序列，显然这些子序列都是有序的
2）两两归并，形成若干有序元组，即49 38 归并成{38 49},第一趟归并结束后为
{38 49} {65 97} {13 76} {27}
3）继续两两归并形成四元组
{38 49 65 97} {13 27 76}
4）再进行一次归并
13 27 38 49 65 76 97

基数类排序

属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，基数排序的思想是“多关键字排序”，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
排序过程

原数据：278 109 063 930 589 184 505 269 008 083

image.png

以上为九种排序算法的介绍，接下来总结下算法的时间复杂度，空间复杂度，稳定性以及使用场景

排序	时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
折半插入排序	O(n^2)	O(nlog2(n))	O(n^2)	O(1)	稳定
希尔排序	O(n^1.3)	O(n)	O(n^2)	O(1)	不稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
堆排序	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(1)	不稳定
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
快速排序	nlog2(n))	nlog2(n))	O(n^2)	O(log2(n))	不稳定
归并排序	nlog2(n))	nlog2(n))	nlog2(n))	O(n)	稳定
基数排序	O(d(n+r))[d:关键字位数;n:序列中的关键字数;r:关键字的取值范围]	O(d(n+r))	O(d(n+r))	O(r)	不稳定