数据结构与算法-排序

排序对于任何一个程序员来说，可能都不会陌生。接下来，我来详细讲一讲经典的排序算法。
选择排序、插入排序和冒泡排序的时间复杂度相同，都是 O(n2)
我们首先来了解一个新的概念，原地排序（Sorted in place）

原地排序（Sorted in place）

原地排序算法，就是特指空间复杂度是 O(1) 的排序算法
仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性
我通过一个例子来解释一下。比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。

这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

一、冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

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


//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.数组打印
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");
}

//4. 冒泡排序-对顺序表L进行交换排序(冒泡排序初级版本)
void BubbleSort0(SqList *L){
   
    int i,j;
    for (i = 1; i < L->length; i++) {
        for (j = i+1; j <= L->length; j++) {
            if(L->r[i] > L->r[j])
                swap(L, i, j);
        }
    }
    
}


//2.冒泡排序-对顺序表L作冒泡排序(正宗冒泡排序算法)
void BubbleSort(SqList *L){
    int i,j;
    for (i = 1; i < L->length; i++) {
        //注意:j是从后面往前循环
        for (j = L->length-1; j>=i; j--) {
            
            //若前者大于后者(注意与上一个算法区别所在)
            if(L->r[j]>L->r[j+1])
                //交换L->r[j]与L->r[j+1]的值;
                swap(L, j, j+1);
        }
    }
}

//3.冒泡排序-对顺序表L冒泡排序进行优化
void BubbleSort2(SqList *L){
    int i,j;
    //flag用作标记
    Status flag = TRUE;
    
    //i从[1,L->length) 遍历;
    //如果flag为False退出循环. 表示已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态;
    for (i = 1; i < L->length && flag; i++) {
        
        //flag 每次都初始化为FALSE
        flag = FALSE;
        
        for (j = L->length-1; j>=i; j--) {
            
            if(L->r[j] > L->r[j+1]){
            //交换L->r[j]和L->r[j+1]值;
            swap(L, j, j+1);
            //如果有任何数据的交换动作,则将flag改为true;
            flag=TRUE;
            }
        }
    }
}

二、插入排序

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

//直接插入排序算法--对顺序表L进行直接插入排序
void InsertSort(SqList *L){
    int i,j;
    //L->r[0] 哨兵 可以把temp改为L->r[0]
    int temp=0;
    
    //假设排序的序列集是{0,5,4,3,6,2};
    //i从2开始的意思是我们假设5已经放好了. 后面的牌(4,3,6,2)是插入到它的左侧或者右侧
    for(i=2;i<=L->length;i++)
    {
        //需将L->r[i]插入有序子表
        if (L->r[i]<L->r[i-1])
        {
            //设置哨兵 可以把temp改为L->r[0]
            temp = L->r[i];
            for(j=i-1;L->r[j]>temp;j--)
                    //记录后移
                    L->r[j+1]=L->r[j];
            
            //插入到正确位置 可以把temp改为L->r[0]
            L->r[j+1]=temp;
        }
    }
}

三、选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾或者开头。

//选择排序--对顺序表L进行简单选择排序
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);
    }
}

四、希尔排序

//希尔排序-对顺序表L希尔排序
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);
}

五、堆排序

//大顶堆调整函数;
/*
 条件: 在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);
    }
}