冒泡排序(Bubble Sort) ⼀种交换排序,它的基本思想就是: 两两⽐较相邻的记录的关键字,如果反序则交换,直到没有反序的记录为⽌
两两比较，往上移动 -> 第二层遍历是从 尾部开始的
遍历中， 没有任何数据的交换动作 -> 数据是有序的
void BubbleSort(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;
}
}
if (!flag) break;
}
}
直接插⼊排序算法(Stight Inserton Sort)的基本操作是将⼀个记录插⼊到已经排好序的有序表中,从⽽得到⼀个新的,记录数增1的有序表
从第二个元素开始，往已经排好序的数据中插入
void InsertSort(SqList *L){
int i,j;
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]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;
}
}
}
简单排序算法(Simple Selecton 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. 重新调整结构，使其满⾜堆定义，然后继续交换堆顶元素与当前末尾元素，反复执⾏调整+交换步骤，直到整个序列有序
大顶堆调整函数
条件: 在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;
}
堆排序--对顺序表进行堆排序
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);
}
}
堆排序的时间复杂度为：O(nlogn)
堆排序是就地排序，空间复杂度为常数：O(1)
归并排序
合并
//③ 将有序的SR[i..mid]和SR[mid+1..n]归并为有序的TR[i..n]
void Merge(intSR[],intTR[],inti,intm,intn)
{
int j,k,l;
//1.将SR中记录由小到大地并入TR
for(j=m+1,k=i;i<=m && j<=n;k++)
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
//2.将剩余的SR[i..mid]复制到TR
if(i<=m)
{
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l];
}
//3.将剩余的SR[j..mid]复制到TR
if(j<=n)
{
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l];
}
}
1.递归实现： 将数据 拆成长度1的子序列， 再将子序列两两进行合并且排序
先拆分，后合并
//② 将SR[s...t] 归并排序为 TR1[s...t];
void MSort(int SR[],int TR1[],int low,int hight){
int mid;
int TR2[MAXSIZE+1];
if(low == hight)
TR1[low] = SR[low];
else{
//1.将SR[low...hight] 平分成 SR[low...mid] 和 SR[mid+1,hight];
mid = (low + hight)/2;
//2. 递归将SR[low,mid]归并为有序的TR2[low,mid];
MSort(SR, TR2, low, mid);
//3. 递归将SR[mid+1,hight]归并为有序的TR2[mid+1,hight];
MSort(SR, TR2, mid+1, hight);
//4. 将TR2[low,mid] 与 TR2[mid+1,hight], 归并到TR1[low,hight]中
Merge(TR2, TR1, low, mid, hight);
}
}
//① 对顺序表L进行归并排序
void MergeSort(SqList *L){
MSort(L->r,L->r,1,L->length);
}
2.非递归实现：
边拆分，边合并
//对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
// 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;
}
}
排序总结
稳定性解释：排序后的元素相同元素的顺序依然是排序之前的顺序
