基于C语言的排序算法汇编

排序算法

内部排序：数据在内存

外部排序：数据在外存

串行排序：单处理器单个进行

并行排序： 多处理器同时进行

比较排序： 用比较的方法：插入，交换，选择，归并排序等皆属此类。

基数排序： 不需要排序，仅仅依靠元素本身的取值确定其有序位置

原地排序：辅助空间量为O(1),所占辅助存储空间与参加排序的数据量大小无关。

非原地排序：辅助空间和参加排序的数据量大小有关。

稳定排序：能够使任何数值相等的元素，排序以后相对次序不变（需参照例子理解）

非稳定性排序：不是稳定排序的方法

自然排序：输入数据越有序，排序的速度就越快

非自然排序：不是自然排序

#define MAXSIZE 20
typedef int KeyType;
Typedef struct//定义每个记录（数据元素）的结构
{
    KeyType key;
    InfoType otherinfo;
}RedType;// Record Type

Typedef struct//定义顺序表的结构
{
    RedType r[MAXSIZE + 1];// 存储顺序表的向量
    int length;//顺序表的长度
}SqList;//顺序表

插入排序

基本思想：每一步将一个待排序的对象，按期关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

直接插入排序

void InsertSort(SqList &L)
{
    int i,j;
    for(i = 2; i <= L.length; i++)
    {
        if(L.r[i].key < L.r[i - 1].key)
        {
            L.r[0] = L.r[i];//哨兵记录了需要交换的元素
            for(j = i -1 ; L.r[0].key < L.r[j].key; --j)
            {
                L.r[j + 1] = L.r[j]//为需要交换的元素腾出空间
            }
        }
    }
}

直接插入排序反思：原始数据越接近有序，排序速度越快，最坏情况下，输入数据是逆有序的，平均情况下，耗时差不多是最坏情况的一半。只有减少元素的比较次数和移动次数才能提高排序速度。

二分插入排序

void BinsertSort(SqList &L)
{
    for(int i = 2; i <= L.Length; i++)
    {
        L.r[0] = L.r[i];
        low = 1; high = i - 1;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if( L.r[0].key < L.r[mid].key) 
                high = mid - 1;
            else
                low  = mid + 1;
        }//while high+1为插入位置
        for(j = i - 1; j >= high + 1; --j)//把位置腾出来
            L.r[high + 1] = L.r[0];
    }
}//BinsertSort

折半排序算法分析

当n较大时，总关键码比较次数必直接插入排序要好的多，但比其最好情况要差（即对象的初始排列接近有序）。折半查找不管初始排列如何总是会以相同的方式排列完所有的对象。

折半插入排序减少了比较次数，但是没有减少移动次数。平均性能优于直接插入排序。

希尔排序

基本思想：先将整个待排序对象，分割成若干子序列，在子序列当中进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

talk is cheap ,show me code

1.定义增量序列Dk,M ≤ k ≤ 1

2.对每个Dk进行“Dk-间隔”插入排序

特点：

一次移动较大步幅，跳跃式接近排序后的最总位置
最后进行直接插入排序时只需要少量移动
增量序列必须是递减的，即步幅必须是递减的
最后一次排序必须是直接插入排序，即步幅为1
增量序列应该是互为质数

void ShellSort(Sqlist& L, int dlta[], int t)//t规定了循环的次数
{
    for(int k = 0; k < t; k++)//一个共要循环t次
    {
        ShellInsert(L, dlta[k]);// dlta 存储了步长因子
    }
}//ShellSort

void ShellInsert(SqList & L, int dk)// L 为待排序对象， dk为步长因子
{
    for(int i = dk + 1; i <= L.Length; i++)//dk + 1是为了确定步长后的元素下标
    {
        if(r[i].key < r[i -dk].key)//如果较小的元素放在了后面
        {
            r[0] = r[i];//哨兵节点记录需要交换的元素，较小的元素
            for(int j = i - dk; j > 0 && (r[0].key < r[j].key); j = j - dk)//疑问：这个语句会循环多少次？？？
                r[j + dk] = r[j];//把较大的元素放在后面
            r[j + dk] = r[0];//把较小的元素放在前面
        }//if
    }//for，至此完成了一个步长因子，还剩下其它几个步长因子
}//ShellInsert

希尔排序算法分析

Hibbard增量序列：Dk的取值为2的k次方减1,比如：1,3,7,15……

Sedgewick增量序列：{1,5,19,41,109……00}

希尔排序算法是一种不稳定的排序算法，当序列中出现了相同的元素，则会改变元素的相对位置，因此我们说希尔排序是一种不稳定的排序

如何选择最佳增量序列目前尚未解决

最后增量序列的最后一个值必须为1,无除了1之外的公因子

此算法不宜在链式存储结构上使用，因为链式存储结构不能够方便的实现步长的跨越。

交换排序

冒泡排序

void bubble_sort(SqList &L)
{
    int m,i,j;
    int flag = 1;
    RedType x;//record type x, 临时存储
    for(m = 1; m <= n - 1 && flag == 1; m++)//若有n个元素，则只需要比较n-1次
    {   flag = 0;//若本次为发生排序，则证明此序列已经有序，因此直接结束排序算法
        for(j = 1;j <= n - m;j++ )
        {
            if(L.r[j].key > L.r[j + 1].key)
            {
                x = L.r[j].key;
                L.r[j] = L.r[j + 1];
                L.r[j + 1] = x;
                flag = 1;
            }// if
        }//for
    }//for
}//bubble_sort

冒泡排序是稳定的

快速排序（改进的交换排序）

pivot:轴心，中心点;任取一个元素作为中心，所有比它小的一律放前面，比它大的一律放后面。形成两个子表，再对子表进行出重复的操作。应用递归的思想，递归的结束条件是每个子表中均只剩下一个元素。

每一趟的子表的形成都是采用从两头向中间交替式逼近法从后面挑小的，从前面挑大的

void QSort(SqList &L, int low, int high)
{
    if(low < high)
    {
        pivotloc = Partition(L, low, high);//找出中心点，partition:划分，分割，名词动词兼有
        QSort(L, low, pivotloc - 1);//对小端进行排序
        QSort(L, pivotloc + 1, high);//对大端进行排序
    }//if
}//QSort

int Partition(SqList&L, int low, int high)
{
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;// 这是一种常见取中点的方法，遇到输入序列本身接近有序的情况还需作出调整。
    while(low < high)//整体序列的两个子序列，结束条件是low == high
    {
        while(low < high && L.r[high].key >= pivotkey) high--;//把小的都搬到左边（相较pivotkey）
        L.r[low] = L.r[high];//low不动，指向最小端
        while(low < high && L.r[low].key <= pivotkey) low++;//把大的都搬到右边（相较pivotkey）
        L.r[high] = L.r[low];//high不动，指向最大端
    }//while
    L.r[low] = L.r[high] = L.r[0];
    return low//返回中心点
} //Partition

QSort(L,1,L.length);

快速排序的性能分析

当快速排序应用于基本有序的时候，会导致中心点划分不均衡，这回导致快速排序退化为没有改进的冒泡排序，即每次只能处理一个元素。针对快速排序，输入数据次序越乱越好，所选划分元素的随机性越好，排序速度就越快，快速排序不是自然排序，同时也不是稳定排序。

选择排序

打擂台思想

void SelectSort(SqList& L)
{   
    for(int i = 1; i < L.Length; i++)
    {
        int k = i;
        for(int j = i+1;j < L.Length; j++)
        {
            if(L.r[j] < L.r[k])
            {
                k = j;
            }//if
        }//for
        if(k != i) 
            swap(&L.r[i],&L.r[k]);
    }//for
}//SelectSort

堆排序

堆实质上是一棵完全二叉树，并且它的任一非叶子节点均小于或大于它的孩子节点。

小根堆：根节点小于两个叶子节点。
大根堆：根节点大于两个叶子节点。
如果一棵二叉树中有任何一个根节点不满足以上任一一个的要求，则它不是堆。

如何在输出堆顶元素之和调整剩余元素使之成为一个新的堆。

void HeapAdjust(elem R[], int s,int m)//取出一个元素后仍然是堆的调整算法
{
    //R中记录的关键字符合堆的定义，本函数调整R中的关键字，使之成为一个大根堆。R[s……m]
    rc = R[s];// rc 初始化为首元素
    for(int j = 2*s; j < m; j *= 2)//
    {
        if(j < m && R[j] < R[j+1]) j++;// j 为key值较大的记录的下标
        if(rc >= R[j]) break;//如果根节点已经大于字节点则直接结束循环。
        R[s] = R[j];// 把key值较大的记录移动到根节点
        s = j;// s指向R[j]原来的位置
    }//for
    R[s] = rc;// 把首元素放到原先较大记录的位置，即有更大的元素出现，那它就必须让位给更大的元素，而子集则充当其儿子。
}//HeapAdjust

如何由一个无序的序列建造一个堆？

单节点的二叉树是堆,即只有一个节点

在完全二叉树中所有以叶子节点（序号i> n/2）为根的子树是堆。这样，我们只需以此将以序号为n/2,n/2-1,……1的节点为根的子树调整为堆即可。
堆实质上是一个线性表，可以采用顺序存储结构
二叉树的叶子节点的序号总是满足i > n/2,即所有的叶子节点都是堆。
叶子节点不用管，只用管非叶子节点，用非叶子节点和它的两个孩子进行比较，发现大的或小的（取决于大根堆还是小根堆）就交换。

for(int i = n/2; i >= 1; i--)//从第一个非叶子节点开始操作
    HeadAdjust(R,i,n);//建立大/小根堆算法（取决于HeadAdjust的写法）

堆排序性能分析

实质上，堆排序就是利用了完全二叉树中父节点与孩子节点之间的内在关系来排序的。

void HeapSort(elem R[])
{
    int i;
    for(i = n/2; i >= 1; i--)
    {
        HeapAdjust(R, i ,n);// 由非叶子节点建堆
    }//for
    for( i = n; i > 1; i--)// 进行n-1次排序
    {
        Swap(R[1], R[i]);// 根与最后一个元素交换，实际上输出堆头
        HeapAdjust(R, 1,i - 1);
    }//for
}//HeapSort

Time:2022.9.24

计划：把查找与排序的笔记上传到csdn，然后统一整理实现。

算法分析需要额外的学习

归并排序

把两个及以上的有序序列归并为一个有序序列

归并排序可以看成是一棵倒着的树，树的高度，也就是需要排序的次数，是以2为底n的对数，n为元素个数

视频课程未提供代码实现

基数排序（桶排序）

龙归沧海，鸟入青山
视频未提供代码
要求数字是有范围的，要根据元素的个数来分配容器。

各种排序方法的比较

悟：如果自己分析算法的时间复杂度和空间复杂度就不能综合分析各个算法的优劣，因此单单掌握算法的思想和编码还不够，还需要能够分析算法，这样才能在应用场景中选择合适的算法，到此学到的东西才能落地。

稳定排序的一个应用场景：总的数值一样，但是实际情况的要求是必须分出先后，这时候我们怎么决定？