数据结构——排序-EW帮帮网

待排序记录的存储方式

#define MAXSIZE 20//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整型
typedef struct
{
    KeyType key;//关键字项
    InfoType otherinfo;//其他数据项
}RedType;//记录类型
typedef struct
{
    RedType r[MAXSIZE+1];//r[0]闲置或作为哨兵
    int length;//顺序表长度
}SqList;//顺序表类型

内部排序

待排序的记录都在计算机内存中**（稳定：相同的数排序前后相对次序不变）**

插入排序

直接插入排序(稳定)

最简单的排序方法，将一条记录插入已经排序好的表，从而得到一个记录数量加1的有序表，若初始数据基本有序则选它

/*
	算法步骤：
	1. 设排序的记录存放在数组r[1..n]中，r[1]为一个有序序列
	2. 循环n-1次，每次使用顺序查找法，查找r[i](i=2...n)在已经排好序的序列r[1...i-1]中的插入位置（与序列r的最后一个数比较，若大于则不用插入；若小于则将序列r最后一个元素往后挪，比较元素放在哨兵处；从后往前不断比较每一个元素，若大于则不挪且插在其后面；若小于则往后挪后继续比较直至i=1放在i=1的位置）
*/

void InsertSort(SqList &L)
{
    for(int i = 2; i <= L.length; i++)//循环n-1次
    {
        if(L.r[i].key<L.r[i-1].key)//若小于有序表最后一个则需要插入排序
        {
            L.r[0] = L.r[i];//将比较记录放到哨兵位置
            L.r[i] = L.r[i-1];//r[i-1]后移
            for(int j = i - 2; L.r[0].key < L.r[j].key; j--)
                L.r[j+1] = L.r[j];//从后往前找到插入位置
            L.r[j+1] = L.r[0];//插入
		}
	}
}

折半插入排序(稳定)

/*
	算法步骤：
	1. 设排序的记录存放在数组r[1..n]中，r[1]为一个有序序列
	2. 循环n-1次，每次使用折半查找法，查找r[i](i=2...n)在已经排好序的序列r[1...i-1]中的插入位置（用折半查找的方法找插入位，将插入位后每一个元素往后挪动后插入）
*/

void BInsertSort(SqList &L)
{
    for(int i = 2; i < L.length; i++)//从2开始找才有挪动的位置
    {
        L.r[0] = L.r[i];
        int low = 1, high = L.length;
        while(low <= high)//查找插入位
        {
            int mid = (low + high) / 2;
            if(L.r[0].key < L.r[mid].key) high = mid -1;
            else low = mid + 1;
		}
        for(int j = i - 1; j > high + 1; j--) L.r[j+1] = L.r[j];//往后移动，用high是因为查找插入为最后，high所指后一位即插入位
        L.r[hjgh+1] = L.r[0]; //插入
	}
}

希尔排序(不稳定)

视频： https://www.bilibili.com/video/BV1bm42137UZ/?share_source=copy_web&vd_source=e873369df9d4ed0537d52369f51b2add

void ShellInsert(SqList &L, int dk)
{
    for(int i = dk + 1; i < L.length; i++)//比较dk后的每一个数，进行排序，视频是一组全比较完，因为这个在代码内难以实现，故把每一个单独操作
        if(L.r[i].key < L.r[dk].key) 
        {
            L.r[0] = L.r[i];//哨兵存放比较的数
            for(int j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j-=dk)//寻找插入位
                L.r[j+dk] = L.r[j];
            L.r[j+dk] = L.r[0];//插入
        }
}

void ShellSort(SqList &L, int dt[], int t)
{
    for(int k = 0; k < t; k++)//循环增量数组
        ShellInsert(L, dt[k]);
}

交换排序

冒泡排序(稳定)

视频：https://www.bilibili.com/video/BV181421876R/?share_source=copy_web&vd_source=e873369df9d4ed0537d52369f51b2add

void BubbleSort(SqList &L)
{
    int m = L.length - 1, flag = 1;//这里m注意最后一个数不需要往后比较，所以直接等于倒数第二个
    while(m > 0 && flag == 1)
    {
        flag = 0;//初始化位0，代表没有交换，已有序
        for(int j = 1; j <= m; j++)//这里如果m为表长则不加等号
            if(L.r[j].key > L.r[j+1].key)
            {
                flag = 1;
                //交换
                RedType t = L.r[j];
                L.r[j] = L.r[j+1];
                L.r[j+1] = t;
            }
	}
}

快速排序(不稳定)

不适应于原始数据有序或基本有序

视频： https://www.bilibili.com/video/BV1y4421Z7hK/?share_source=copy_web&vd_source=e873369df9d4ed0537d52369f51b2add

int Partition(SqList &L, int low, int high)
{
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;//去第一个为枢轴，大的放在其右边，小的放在其左边
    while(low < high)
    {//以第一个为枢轴，故从高的开始找
        while(low < high && L.r[right].key >= pivotkey) high--;//找到枢轴右边比枢轴小的元素
        L.r[low] = L.r[high];//放到左边的空
        while(low < high && L.r[right].key <= pivotkey) low++;//找到枢轴左边比枢轴大的元素
        L.r[high] = L.r[low];//放到右边的空
	}
    L.r[low] = L.r[0];//插入枢轴
    return low;  
}

void QSort(SqList &L, int low, int high)
{
    if(low < high)//递归循环每一部分
    {
        int pivotloc = Partition(L, low, high);
        QSort(L, low, pivotloc-1);
        QSort(L, pivotloc+1, high);
	}
}

void QuickSort(SqList &L)
{
    QSort(L, 1, L.length);
}

选择排序

简单选择排序（不稳定）

/*
	算法步骤：
	1. 待排序的记录存放在数组r[1……n]中。第一轮从r[1]开始，通过n-1次比较，找出关键字最小的记录，记为r[k]，交换r[1]与r[k]
	2. 第二轮从r[2]开始，通过n-2次比较，找出关键字最小的记录，记为r[k]，交换r[2]与r[k]
	3. 以此类推，第i轮从r[i]开始，通过n-i次比较，找出关键字最小的记录，记为r[k],交换r[i]与r[k]
	4. 经过n-1轮，排序结束
*/

void SelectSort(SqList &L)
{
    for(int i = 1; i < L.length; i++)//循环n-1轮
    {
        k = i;//存放最小值的地址
        for(int j = i + 1; j <= L.length; i++)
            if(L.r[j].key < L.r[k].key) k = j;//找到最小的记录
        if(k != i)//交换 
        {
            t = L.r[k];
            L.r[k] = L.r[i];
            L.r[i] = t;
        }
    }
}

树形选择排序

步骤
1. 将记录，两两比较，选出小的关键字
2. 在选出的小关键字再继续两两比较
3. 反复循环1、2直至选出最小值
如果要选出次小值则将最小值设置为最大数再进行步骤即可，如下图：

在这里插入图片描述

堆排序（不稳定）

堆是一种数据结构，它是一棵完全二叉树，根节点称为堆顶。堆分为大根堆（根节点为最大值，父母节点大于孩子节点）与小根堆（根节点为最小值，父母节点小于孩子节点）
在内存的存储方式是以层序遍历为顺序的数组，是顺序存储，排序时想象成一颗完全二叉树
按照数组的下标 i ，有以下规律：i号节点的左孩子为2i，右孩子为2i+1，父亲节点为 $\lfloor i/2 \rfloor$ (向下取整)
视频：https://www.bilibili.com/video/BV1HYtseiEQ8/?share_source=copy_web&vd_source=e873369df9d4ed0537d52369f51b2add

/*
	算法步骤：
	1. 建堆--从最后一个非叶节点(i/2)开始依次向下调整，把r[i]~r[1]为根的子树调整为堆。从r[2i]（左孩子）与r[2i+1]（右孩子）中选出关键字较大者，与r[i]（根节点）进行比较，假设r[2i]较大
        。若r[i].key >= r[2i].key，说明以r[i]为根的子树已经是堆，不必进行调整
        。若r[i].key < r[2i].key，交换r[i]和r[2i]。交换后若以r[2i]为根的子树不是堆重复上述过程，将其调整为堆，直至进行到叶节点为止
	2. 排序--每轮堆顶换到最后，向下调整新的堆顶，n-1轮
*/

//建堆
void HeapAdjust(SqList &L, int s, int m)
{
    rc = L.r[s];
    for(int j = 2 * s; j <= m; j *= 2)//沿key比较大的还在节点向下筛选，直至叶子节点或者已经是堆
    {
        if(j < m && L.r[j].key < L.r[j+1].key) j++;//比较左右孩子大小，若右孩子大则j为右的下标；否则保持不动为左孩子
        if(rc.key > L.r[j].key) break;//比较孩子中较大节点与根节点，根节点大于孩子节点则已经是堆，跳过
        L.r[s] = L.r[j];//否则交换
        s = j; //让他等于s，不然j可能会变
	}
    L.r[s] = rc;//插入 
}

void CreateHeap(SqList &L)
{
	int n = L.length;
    for(int i = n / 2; i > 0; i--)//从n/2（最后一个非叶节点）开始排序，因为叶节点一定是堆了，不需要建堆
        HeapAdjust(L, i, n);
}

//排序
void HeapSort(SqList &L)
{
    CreateHeap(L);//把无序序列建立为大根堆
    for(int i = L.length; i > 1; i--)
    {
        x = L.r[1];//将堆顶元素与最后一个互换，即把最大值排在最后
        L.r[1] = L.r[i];
        L.r[i] = x;
        HeapAdjust(L, 1, i-1);//然后把剩下的继续化为大根堆，重复上述步骤
	}
}

归并排序（稳定）

归并：比较两个序列，依次找出每轮中两个序列中的最小数，放到一个临时数组里，直到有一个序列取完即归并结束。

//非递归：最开始每个元素单独作为一个序列，从左到右，每轮都对相邻的两个序列进行归并（若最后只有一个序列则无需归并），直到所有序列归并为一个序列。（若遇到相同的数，优先归并左边的数）

//递归：递归到确定为有序序列，归并左右两个序列

/*
	算法步骤：设两个有序表存放在同意数组的相邻位置（R[low~mid]和R[mid+1~high]）上，每次分别从两个表中取出一个记录进行关键字比较，将较小者放入T[low~high]中。重复此过程，直至一个表为空，最后把另外一个表余下部分复制到T数组中
*/
void Merge(RedType R[], RedType T[], int low, int mid, int high)//归并排序函数
{
    int i = low, j = mid + 1, k = low;
    while(i <= mid && j <= mid)//左边归并完+右边归并完=整个序列归并完
    {
        if(R[i].key <= R[j].key) T[k++] = R[i++];//左序列元素小于右序列元素，左序列元素放到T中
        else T[k++] = R[j++];//否则右序列元素放到T中
	}
    while(i <= mid) T[k++] = R[i++];//左边剩下的就复制进去
    while(j <= hjgh) T[k++] = R[j++];//右边剩下的就复制进去
}


/*
	算法步骤：
	1. 将当前序列一分为二，求出分裂点mid=(low+high)/2（向下取整）
	2. 对左子序列递归并进行排序，结果放入S[low~mid]中
	3. 对右子序列递归并进行排序，结果放入S[mid+1~high]中
	4. 调用算法Merge，将两个有序的相邻归并为同一个有序序列
*/
void MSort(RedType R[], RedType T[], int low, int high)//归并排序函数
{//R为初始序列，T为最终序列，S为过度序列
    if(low == high) T[low] = R[low];//遍历到
    else
    {
        mid = (low + high) / 2;
        MSort(R, S, low, mid);//先遍历左边
        MSort(R, S, mid+1, high);//后遍历右边
        Merge(S, T, low, mid, high);//归并左右序列
	}
}

基数排序（稳定）

它是一种非比较的排序算法
基数：关键字的进制数，十进制为十
最高位优先法：从每个数的最高位开始排序（算法比较复杂）
最低位优先法：从每个数的最低位开始排序（算法简单，用得多）

#define MAXNUM_KEY 8//关键字项的最大值
#define RADIX 10//基数
#define MAX_SPACE 10000
typedef struct
{
    KeyType keys[MAXNUM_KEY];//关键字
    InfoType info;
    int next;
}SLCell;
typedef struct
{
    SLCell r[MAX_SPACE];//静态链表
    int keynum;//记录关键字个数
    int recnum;//静态链表当前长度
}SLList;
typedef int ArrType[RADIX];//数组类型

    
/*
	算法步骤：
	1. 第一轮分配最低位数，然后从小到大拿出来
	2. 第二轮分配次低位数，然后从小到大拿出来
	3，依次循环直到所有位数都分配完即排序完成
*/
void Distribute(SLCell &r, int i, ArrType &f, ArrType &e)//基数排序函数
{//数组f用来各分配字串的队头，数组e指向队尾
    for(int j = 0; j < RADIX; j++) f[j] = 0;//各子表初始化为0
    for(int p = r[0].next; p; p = r[p].next)
    {
        int j = ord(r[p].keys[i]);//取出每一位的相应位数的值
        if(!f[j]) f[j] = p;//若是空的直接加p进去
        else r[e[j]].next = p;//否则把子链最后一个元素的next指针指向p
        e[j] = p;//尾指针指向p
    }
}

void Collect(SLCell &r, int i, ArrType &f, ArrType &e)//导出函数，按子表从小到大的顺序提取出来，变成一条链表
{	
    for(int j = 0; !f[j]; j=succ(j));//找到子表中非空的，succ为找这个子表后面的子表位置的函数
    r[0].next = f[j];//头指针指向第一个非孔子表第一个节点
    t = e[j];//取出尾节点
    while(j < RADIX)
    {
        for(int j = succ(j); j<RADIX-1 && !f[j]; j=succ(j));//找下一个空字表
        if(f[j])
        {
            r[t].next = f[j];//上一次的尾指向下一个表的头
            t = e[j];//取出队尾
        }
    }
    r[t].next = 0;//t指向最后一个非空子表的最后节点
}

void RadixSort(SLList &L)
{
    for(int i = 0; i < L.recnum; ++i) L.r[i].next = i+1;//把L改造成静态链表，即基数0~9的对应子表
    L.r[L.recnum].next = 0;//L的最后一个表的尾指针设为空
    for(int i = 0; i < L.keynum; ++i)//按最低位
    {
        Distribute(L.r, i, f, e);//第i趟分配
        Collect(L.r, i, f, e);//第i趟收集
    }
}

其他