一、排序的分类

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

二、排序结构设计

1、顺序表结构

//1.排序算法数据结构设计
//用于要排序数组个数最大值，可根据需要修改
#define MAXSIZE 10000
typedef struct
{
    //用于存储要排序数组，r[0]用作哨兵或临时变量
    int r[MAXSIZE+1];
    //用于记录顺序表的长度
    int length;
}SqList;

2、数据交换函数

//2.排序常用交换函数实现
//交换L中数组r的下标为i和j的值
void swap(SqList *L,int i,int j)
{
    int temp=L->r[I];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

3、数据打印

//3.数组打印
void print(SqList L)
{
    int I;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[I]);
    printf("%d",L.r[I]);
    printf("\n");
}

三、几种常见的排序

1、冒泡排序

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

/*把最小的位置留给最小元素。下次循环的时候就可以少遍历一个数。

通过不断交换，把较小的数往前挪。
过程:
从头开始遍历，结束遍历的时候，首位就是最小的元素。
下一个最小的元素只需要从2到n中确定，一直到n-1到n中确定。
当前元素 > 后一个元素，则交换两个元素位置，最小元素就前移了。
也就是说，每次遍历较小的数字一定会逐渐前移。*/
void BullleSort(SqList *L)
{
    for (int i = 1;i<L->length;i++)
        for (int j=i+1; j<=L->length; j++) {
           
            if (L->r[i]>L->r[j])
            {
                swap(L, i, j);
            }
        }
}

也可以反过来，每次都把最大的值放到末尾。

void BullleSort(SqList *L)
{
    for (int i = 1;i<L->length-1;i++)
        for (int j=1; j<L->length-i-1; j++) {
           
            if (L->r[j]>L->r[j+1])
            {
                swap(L, j, j+1);
            }
        }
}

冒泡排序的优化

void BullleSort(SqList *L)
{
    Status flag = TRUE; //用作标记本次是否有交换
    for (int i = 1;i<L->length-1 && flag;i++)
    {
        flag = FALSE;
        for (int j=1; j<L->length-i-1; j++) {

            
            if (L->r[j]>L->r[j+1])
            {
                flag = TRUE;
                swap(L, j, j+1);
            }
        }
        
    }
        
}

2、选择排序

简单排序算法(Simple Selection Sort) 就是通过n-i次关键词比较,从n-i+1个记录中找出关键 字最小的记录,并和第i(1<=i<=n) 个记录进行交换.
总结一句话就是(划重点)：从第一个位置开始比较，找出最小的，和第一个位置互换，开始下一轮。

void SelectSort(SqList *L){
    
    int i,j,min;

    for (i = 1; i < L->length; i++) {
        //① 将当前下标假设为最小值的下标
        min = I;
        //② 循环比较i之后的所有数据
        for (j = i+1; j <= L->length; j++) {
            //③ 如果有小于当前最小值的关键字,将此关键字的下标赋值给min
            if (L->r[min] > L->r[j]) {
                min = j;
            }
        }
        
        //④ 如果min不等于i,说明找到了最小值,则交换2个位置下的关键字
        if(i!=min)
            swap(L, i, min);
    }
}

那么好，是时候来总结下他们的区别了（划重点）。

（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；

（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；

（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；

冒泡排序优缺点：优点:比较简单，空间复杂度较低，是稳定的；
缺点:时间复杂度太高，效率慢；

选择排序优缺点：优点：一轮比较只需要换一次位置；
缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。

3、直接插入排序

直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表 中,从而得到一个新的,记录数增1的有序表;
步骤1、将数据插入到有序表中与前一个比较，如果大于则不改变位置
2、如果插入数据小于前一个数据，则前面大的数据依次往后移动，然后找到合适位置插入该数据。

void insertSort(int *a,int n)
{
    int temp,i,j;
    for( i =0;i < n-1;i++)
    {
        //如果前面的值大
        if (a[i] > a[i+1])
        {
            temp = a[i+1];
            //把temp插入到合适的位置，前面的往后移动
            for(j=i;j>=0&&a[j]>temp;j--)
            {
                 a[j+1] = a[j];
                
            }
            a[++j] = temp;
            
        }
    }
   
}

空间复杂度: O(1) 解读:在直接插⼊入排序中只使⽤用了了i,j,temp这三个辅助元素，与问题规模⽆无关，空间复杂度为O(1)
时间复杂度: O(n2)

4、希尔排序

希尔排序思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插⼊排序算法排 序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个序列恰被分成 一组，算法便终止.
其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。
希尔排序通过增量进行了分组(分治)，比较的是L->r[j-increment]和L->[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。
也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。

//希尔排序
void shellSort(SqList *L){
    int i,j;
    int increment = L->length;
    
    //0,9,1,5,8,3,7,4,6,2
    //① 当increment 为1时,表示希尔排序结束
    do{
        //② 增量序列
        increment = increment/3+1;
        //③ i的待插入序列数据 [increment+1 , length]
        for (i = increment+1; i <= L->length; i++) {
            //④ 如果r[i] 小于它的序列组元素则进行插入排序,例如3和9. 3比9小,所以需要将3与9的位置交换
            if (L->r[i] < L->r[i-increment]) {
                //⑤ 将需要插入的L->r[i]暂时存储在L->r[0].和插入排序的temp 是一个概念;
                L->r[0] = L->r[I];
                
                //⑥ 记录后移
                for (j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment) {
                    L->r[j+increment] = L->r[j];
                }
                
                //⑦ 将L->r[0]插入到L->r[j+increment]的位置上;
                L->r[j+increment] = L->r[0];
            }
        }
    }while (increment > 1);
}

需要注意的是：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

5、堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为nlogn，它也是不稳定排序。

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。

或者

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图1为大顶堆：

下图为小顶堆：

我们用简单的公式来描述一下堆的定义就是：

大顶堆： arr[i] >= arr[2i] && arr[i] >= arr[2i+1]

小顶堆： arr[i] <= arr[2i] && arr[i] <= arr[2i+1]

堆排序的基本思想是：

1、用待排序序列构造一个大顶堆。
2、将其与末尾元素进行交换，此时末尾就为最大值。
3、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
4、如此反复执行，便能得到一个有序序列了。
我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：
利用堆结构特性，不断选出最大值，放到最后。

//大顶堆调整函数;
/*
 条件: 在L.r[s...m] 记录中除了下标s对应的关键字L.r[s]不符合大顶堆定义,其他均满足;
 结果: 调整L.r[s]的关键字,使得L->r[s...m]这个范围内符合大顶堆定义.
 */
void HeapAjust(SqList *L,int s,int m){
    
    int temp,j;
    //① 将L->r[s] 存储到temp ,方便后面的交换过程;
    temp = L->r[s];
    
    //② j 为什么从2*s 开始进行循环,以及它的递增条件为什么是j*2
    //因为这是颗完全二叉树,而s也是非叶子根结点. 所以它的左孩子一定是2*s,而右孩子则是2s+1;(二叉树性质5)
    for (j = 2 * s; j <=m; j*=2) {
        
        //③ 判断j是否是最后一个结点, 并且找到左右孩子中最大的结点;
        //如果左孩子小于右孩子,那么j++; 否则不自增1. 因为它本身就比右孩子大;
        if(j < m && L->r[j] < L->r[j+1])
            ++j;
        
        //④ 比较当前的temp 是不是比较左右孩子大; 如果大则表示我们已经构建成大顶堆了;
        if(temp >= L->r[j])
            break;
        
        //⑤ 将L->[j] 的值赋值给非叶子根结点
        L->r[s] = L->r[j];
        //⑥ 将s指向j; 因为此时L.r[4] = 60, L.r[8]=60. 那我们需要记录这8的索引信息.等退出循环时,能够把temp值30 覆盖到L.r[8] = 30. 这样才实现了30与60的交换;
        s = j;
    }
    
    //⑦ 将L->r[s] = temp. 其实就是把L.r[8] = L.r[4] 进行交换;
    L->r[s] = temp;
}


//10.堆排序--对顺序表进行堆排序
void HeapSort(SqList *L){
    int I;
   
    //1.将现在待排序的序列构建成一个大顶堆;
    //将L构建成一个大顶堆;
    //i为什么是从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
    for(i=L->length/2; i>0;i--){
        HeapAjust(L, i, L->length);
    }
    
    
    //2.逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
    for(i = L->length; i > 1; i--){
        
        //① 将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
        swap(L, 1, i);
        //② 将L->r[1...i-1]重新调整成大顶堆;
        HeapAjust(L, 1, i-1);
    }
}

6、归并排序

归并排序(Merging Sort) 就是利利⽤用归并的思想实现排序⽅方法. 它的原理理是假设初始序 列列含有n个记录,则可以看成n个有序的⼦子序列列. 每个⼦子序列列的⻓长度为1,然后两两合并.得 到[n/2]个⻓长度为2或1的有序⼦子序列列, 再两两归并. ......如此重复,直到得到⼀一个⻓长度为n 的有序序列列为此. 这种排序⽅方法称为2路路归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。
将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起。

进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。

6.1递归写法

//6归并排序

void MergeCombine(int SR[],int TR[],int low,int m,int hight)
{
    int i,j,k;
    for(i = low,j=m+1,k=low;i<=m&&j<=hight;k++)
    {
        if (SR[i]<SR[j])
        {
            TR[k] = SR[i++];
        }
        else
        {
            TR[k] = SR[j++];
        }
    }
    if (i <= m)
    {
        for(int l =0;l<m-i;l++)
        {
            TR[k+l] = SR[i+l];
        }
    }
    if (j <= hight)
    {
        for(int l =0;l<hight-i;l++)
        {
            TR[k+l] = SR[j+l];
        }
    }
}


void MergeSortNew(int SR[],int TR[],int low,int hight)
{
    int TR2[MAXSIZE+1];
    if(low < hight)
    {
        TR[low] = SR[low];
    }
    else
    {
        //分
        int mid = (low+hight)/2;
        MergeSortNew(SR, TR2, low, mid);
        MergeSortNew(SR, TR2, mid+1, hight);
        //合
        MergeCombine(TR2, TR, low, mid, hight);
        
    }
}

6.2循环写法

//6.2.归并排序(非递归)-->对顺序表L进行非递归排序
//对SR数组中相邻长度为s的子序列进行两两归并到TR[]数组中;
void MergePass(int SR[],int TR[],int s,int length){
  
    int i = 1;
    int j;
    
    //①合并数组
    //s=1 循环结束位置:8 (9-2*1+1=8)
    //s=2 循环结束位置:6 (9-2*2+1=6)
    //s=4 循环结束位置:2 (9-2*4+1=2)
    //s=8 循环结束位置:-6(9-2*8+1=-6) s = 8时,不会进入到循环;
    while (i<= length-2*s+1) {
        //两两归并(合并相邻的2段数据)
        Merge(SR, TR, i, i+s-1, i+2*s-1);
        i = i+2*s;
        
        /*
         s = 1,i = 1,Merge(SR,TR,1,1,2);
         s = 1,i = 3,Merge(SR,TR,3,3,4);
         s = 1,i = 5,Merge(SR,TR,5,5,6);
         s = 1,i = 7,Merge(SR,TR,7,7,8);
         s = 1,i = 9,退出循环;
         */
        
        /*
         s = 2,i = 1,Merge(SR,TR,1,2,4);
         s = 2,i = 5,Merge(SR,TR,5,6,8);
         s = 2,i = 9,退出循环;
         */
        
        /*
         s = 4,i = 1,Merge(SR,TR,1,4,8);
         s = 4,i = 9,退出循环;
         */
    }
    
    //②如果i<length-s+1,表示有2个长度不等的子序列. 其中一个长度为length,另一个小于length
    // 1 < (9-8+1)(2)
    //s = 8时, 1 < (9-8+1)
    if(i < length-s+1){
        //Merge(SR,TR,1,8,9)
        Merge(SR, TR, i, i+s-1, length);
    }else{
        //③只剩下一个子序列;
        for (j = i; j <=length; j++) {
            TR[j] = SR[j];
        }
    }
}

void MergeSort2(SqList *L){
    int *TR = (int *)malloc(sizeof(int) * L->length);
    int k = 1;
    //k的拆分变换是 1,2,4,8;
    while (k < L->length) {
        //将SR数组按照s=2的长度进行拆分合并,结果存储到TR数组中;
        //注意:此时经过第一轮的归并排序的结果是存储到TR数组了;
        MergePass(L->r, TR, k, L->length);
        k = 2*k;
        //将刚刚归并排序后的TR数组,按照s = 2k的长度进行拆分合并. 结果存储到L->r数组中;
        //注意:因为上一轮的排序的结果是存储到TR数组,所以这次排序的数据应该是再次对TR数组排序;
        MergePass(TR, L->r, k, L->length);
        k = 2*k;
        
    }
}

时间复杂度: ⼀一趟归并需要将 SR[1]~SR[n]中相邻⻓长度为h 的有序序列列的进⾏行行两两⽐比较. 并 将结果存储在TR1[1]- TR2[n]. 这需要将待排序的所有记录扫描⼀一遍. 因此耗费 O(n) 时间. ⽽而由于完全⼆二叉树的深度可知, 整个归并排序需要进⾏行行 log2n 次. 因此总的时间复杂度为 O(nlogn). ⽽而归并排序,最好,最坏,平均时间复杂度的性能;

空间复杂度: 由于递归排序在递归的过程中需要与原始记录序列列同样数量量的存储归并结 果以及递归时深度为log2n 的栈空间; 因此空间复杂度为 O(n+log2n);

7、快速排序

快速排序(Quick Sort)的基本思想: 通过一趟排序将待排序记录分割成独立的两 部分; 其中一部分记录的关键字均为另一部分记录的关键字小,则可分别对两部分记 录继续进行排序,以达到整个排序有序的目的.

排序过程：

首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

7.1递归写法

//7.1快速排序-对顺序表L进行快速排序
//③交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置
//此时在它之前(后)的记录均不大(小)于它
int Partition(SqList *L,int low,int high){
    int pivotkey;
    //pivokey 保存子表中第1个记录作为枢轴记录;
    pivotkey = L->r[low];
    //① 从表的两端交替地向中间扫描;
    while (low < high) {
        
        //② 比较,从高位开始,找到比pivokey更小的值的下标位置;
        while (low < high &&  L->r[high] >= pivotkey)
            high--;
        //③ 将比枢轴值小的记录交换到低端;
        swap(L, low, high);
        //④ 比较,从低位开始,找到比pivokey更大的值的下标位置;
        while (low < high && L->r[low] <= pivotkey)
            low++;
        //⑤ 将比枢轴值大的记录交换到高端;
        swap(L, low, high);
        
    }
    
    //返回枢轴pivokey 所在位置;
    return low;
}

//② 对顺序表L的子序列L->r[low,high]做快速排序;
void QSort(SqList *L,int low,int high){
    int pivot;
    
    if(low < high){
        //将L->r[low,high]一分为二,算出中枢轴值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //对低子表递归排序;
        QSort(L, low, pivot-1);
        //对高子表递归排序
        QSort(L, pivot+1, high);
    }
    
}