C语言——八大排序
一、冒泡排序
时间复杂度:平均情况:O(n^2) 最好情况:O(n)
空间复杂度:O(1)
稳定性:稳定
主要思路:
1.比较相邻的元素。如果第一个比第二个大,就交换它们两个。
2.对每一个相邻元素做同样的工作,从开始第一对到结尾的每一对。在这一 点,最后的元素应该会是最大的数。
3.针对多有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,知道没有任何一对数字需要比较。
图解:
文章图片
代码:
void Bubble_sort(int *arr, int len)
{
assert(arr != NULL);
int tmp = 0;
bool swap = false;
//加判断条件减少比较次数
for (int i = 0;
i < len -1;
i++)
{
for (int j = 0;
j < len - 1 - i;
j++)
{
if (arr[j] > arr[j + 1])
{
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
//交换
swap = true;
}
}
if (!swap)
{
return;
}
}
}
void Show(int *arr, int len)
{
for (int i = 0;
i < len;
i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int drr[] = {1,8,7,5,0};
int num = sizeof(drr) / sizeof(drr[0]);
Bubble_sort(drr, num);
Show(drr, num);
return 0;
}
二、选择排序
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:不稳定(相同的数值都交换了)
主要思路:
每一次从无序组的数据元素中选出最小的一个元素,存放在无序组的起始位置,无需组的元素减少,有序组的元素增加,直到全部待排序的数据元素排完。
图解:
文章图片
代码:
void select_sort(int *arr, int len)
{
assert(arr != NULL);
int i, j;
int tmp;
int min = 0;
for (i = 0;
i < len;
i++)
{
int min = i;
for (j = i + 1;
j < len;
j++)
{
if (arr[j] < arr[min])
{
tmp = arr[min];
arr[min] = arr[j];
arr[j] = tmp;
}
}
}
}
void Show(int *arr, int len)
{
for (int i = 0;
i < len;
i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int drr[] = { 1,8,7,5,0 };
int num = sizeof(drr) / sizeof(drr[0]);
select_sort(drr, num);
Show(drr, num);
return 0;
}
三、插入排序
直接插入排序:
时间复杂度:无序 O(n^2) 有序O(n)
空间复杂度:O(1)
稳定性:稳定
主要思路:
插入排序是最简单常用的方法,将数组分为两部分,排好序的数列,以及未排序的数列,将未排序的数列中的元素 与排好序的数列进行比较,然后将该元素插入到已排序列的合适位置中。
图解:
文章图片
代码:
void Insert_sort(int *arr, int len)
{
assert(arr != NULL);
int i, j;
int tmp = 0;
for (i = 1;
i < len;
i++)
{
tmp = arr[i];
for (j = i - 1;
j >= 0;
j--)
{
if (arr[j] > tmp)
{
arr[j + 1] = arr[j];
}
else
{
break;
}
}
arr[j + 1] = tmp;
}
}
四、希尔排序:(直接插入的优化)
时间复杂度:O(n^1.5-n^1.5)
空间复杂度:O(1)
稳定性:不稳定
工作原理:
把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
图解:
文章图片
代码:
void Shell(int *arr, int len,int gap)
{
assert(arr != NULL);
int tmp = 0;
int i, j;
for (i = gap;
i < len;
i += gap)
{
tmp = arr[i];
for (j = i - gap;
j >= 0;
j -= gap)
{
if (arr[j] > tmp)
{
arr[j + gap] = arr[j];
}
else
{
break;
}
}
arr[j + gap] = tmp;
}
}
void Shell_sort(int *arr, int len)
{
int drr[] = { 5,3,1 };
//分组必须是素数最后一个必须为1
int lend = sizeof(drr) / sizeof(drr[0]);
for (int i = 0;
i < lend;
i++)
{
Shell(arr, len, drr[i]);
}
}
【C语言——八大排序】五、堆排序
时间复杂度:O(nlog2n)
空间复杂度:O(1)
稳定性:不稳定
主要思路:
1.将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。
2.将其与末尾元素进行交换,此时末尾就是最大值。
3.然后将剩余n -1 个元素重新构造成一个堆,这样会得到n个元素的次小值。
4.如此反复执行,便得到一个有序序列。
图解:
文章图片
代码:
void Adjust(int *arr,int start,int end)
{
assert(arr != NULL);
int tmp = arr[start];
for(int i = 2*start + 1;
i <= end;
i = 2*i+1)
{
if(i < end && arr[i] < arr[i + 1])//是否有右孩子
{
i++;
//最大值的下标
}
if(arr[i] > tmp)
{
arr[start] = arr[i];
start = i;
}
else
{
break;
}
}
arr[start] = tmp;
}
void HeapSort(int *arr,int len)
{
for(int i = (len - 1 - 1)/2;
i >= 0;
i--)
{
Adjust(arr,i,len - 1);
}
for(int i = 0;
i <= len - 1;
i++)
{
int tmp = arr[0];
arr[0] = arr[len - 1 - i];
arr[len - 1 - i] = tmp;
Adjust(arr,0,len - 1 - 1 - i);
}
}
六、快速排序
时间复杂度:最好情况下:O(nlong2n) 最坏情况下:O(n^2)
空间复杂度:O(nlong2n)
稳定性:不稳定
主要思路:
快速排序是找出一个元素(理论上可以随便找一个)作为基准,然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的值都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n - 1 个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置,排序完成。所以快速排序算法的核心算法是分区操作,及如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
图解:
文章图片
代码:
//快排的递归
intPartition(int *arr,int left,int right)
{
int tmp=arr[left];
//将第一个给tmp
while(lefttmp)//右边的大于tmp时
{
right--;
}
if(left>=right)//第一次循环完了
{
break;
}
else
{
arr[left]=arr[right];
}
while(left=right)
{
break;
}
else
{
arr[right]=arr[left];
}
}
arr[left]=tmp;
return left;
//返回相遇的那个位置
}
void Quick(int *arr,int start,int end)
{
int par=Partition(arr,start,end);
if(par>=start+1)
{
Quick(arr,start,par-1);
//当前面部分有两个以上的数时再次排序
}
if(parleft+1)//左边有数时入栈
{
stack[top++]=left;
stack[top++]=par-1;
}
if(par0)//出栈
{
right=stack[--top];
left=stack[--top];
par=Partition(arr,left,right);
if(par>left+1)
{
stack[top++]=left;
stack[top++]=par-1;
}
if(par start+1)//左边是不是有两个数据以上
{
Quick(arr,start,par-1);
}
if(par < end-1)
{
Quick(arr,par+1,end);
}
}2.三分取中法
/*void Swap(int *arr,int low,int high)
{
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
}
void Median_of_Three(int *arr,int start,int mid,int end)
{//arr[mid]<=arr[start]<=arrr[end]
if(arr[mid] > arr[end])//arr[mid]<=arr[end]
{
Swap(arr,mid,end);
}if(arr[start] < arr[mid])//arr[mid]<=arr[start]
{
Swap(arr,start,mid);
}if(arr[start] > arr[end])
{
Swap(arr,start,end);
}
}
void Quick(int *arr,int start,int end)
{
Median_of_Three(arr,start,(end-start)/2+start,end);
int par = Partion(arr,start,end);
if(par > start+1)//左边是不是有两个数据以上
{
Quick(arr,start,par-1);
}
if(par < end-1)
{
Quick(arr,par+1,end);
}
}
3.聚集相同元素法
void Swap(int *arr,int low,int high)
{
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
}
void Focus_Same_Num(int *arr, int low, int par, int high, int *left, int *right)//优化4
{
int parLeft_Index = par-1;
int parRight_Index = par+1;
for(int i = par-1;
i >= low;
i--)
{
if(arr[i] == arr[par] && i != parLeft_Index)
{
Swap(arr,i,parLeft_Index);
parLeft_Index--;
}
}
*left = parLeft_Index;
for(int i = par+1;
i <= high;
i++)
{
if(arr[i] == arr[par] && i != parRight_Index)
{
Swap(arr,i,parRight_Index);
parRight_Index++;
}
}
*right = parRight_Index;
}void Quick(int *arr,int start,int end)
{int par = Partion(arr,start,end);
int par_left = par-1;
int par_right = par+1;
Focus_Same_Num(arr,start,par,end,&par_left,&par_right);
if(par > start+1)//左边是不是有两个数据以上
{
Quick(arr,start,par-1);
}if(par < end-1)
{
Quick(arr,par+1,end);
}
}
七、基数排序
时间复杂度:最好情况:O(d(n+rd)) 最坏情况:O(d(r+n)) r代表关键字的基数 d代表长度 n代表关键字的个数
空间复杂度:O(rd+n)
稳定性:稳定
主要思路:
将整数按位数切割成不同的数字,然后按每个位数分别比较。
将所有待比较数值统一为同样的数位长度,数位较短的数前面补0.然后,从最低位开始,依次进行排序。这样从最低位一直到最高位排完序后,数列就变成一个有序序列。
图解:
第一次入桶:按个位数大小
文章图片
第二次入桶:按十位数大小
文章图片
第三次入桶: 按百位数的大小
文章图片
代码:
typedef struct Node
{
int data;
struct Node *next;
}Node, *List;
//运用单链表
void InitList(List plist)//初始化
{
assert(plist != NULL);
if (plist == NULL)
{
return;
}
plist->next = NULL;
}
static Node *GetNode(int val)
{
Node *p = (Node *)malloc(sizeof(Node));
assert(p != NULL);
p->data = https://www.it610.com/article/val;
p->next = NULL;
return p;
}
bool Insert_tail(List plist, int val)//尾插
{
Node *p;
for (p = plist;
p->next != NULL;
p = p->next)
{
;
}
Node *pGet = GetNode(val);
p->next = pGet;
return true;
}
bool DeletFirst(List plist, int *rtv)//去掉第一个
{
assert(plist != NULL);
Node *p=plist->next;
if (plist->next == NULL)
{
return false;
}
if (rtv != NULL)
{
*rtv = p->data;
}
plist->next = p->next;
free(p);
p = NULL;
return true;
}
int GetMaxBit(int *arr, int len)//获取最大数的位数
{
int Max =arr[0];
for (int i = 0;
i <= len - 1;
i++)
{
if (arr[i] > Max)
{
Max = arr[i];
}
}
int count = 0;
while (Max != 0)
{
count++;
Max /= 10;
}
return count;
}
int GetNum(int num, int date)//得到num的第date位数字
{
for (int i = 0;
i < date;
i++)
{
num /= 10;
}
return num % 10;
}
void Radix(int *arr, int len, int date)
{
Node head[10];
for (int i = 0;
i < 10;
i++)
{
InitList(&head[i]);
}
int i;
int tmp;
for(i = 0;
i < len;
i++)//入桶
{
tmp = GetNum(arr[i],date);
Insert_tail(&head[tmp],arr[i]);
}
i = 0;
for(int j = 0;
j < 10;
)//出桶
{
if(DeletFirst(&head[j], &arr[i]))
{
i++;
//出一桶内的数据
}
else
{
j++;
//一桶内数据出完后
}}
}
void RedixSort(int *arr, int len)
{
int count = GetMaxBit(arr, len);
//进出桶多少次
for(int i = 0;
i < count;
i++)
{
Radix(arr, len, i);
//i表示从右数第0位开始
}
八、归并排序
时间复杂度:O(nlong2n)
空间复杂度:O(n)
稳定性:稳定
主要思想:
将待排序序列R[0…n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。
图解:
文章图片
代码:
void Mearge(int *arr,int len,int gap)
{
int *brr = (int *)malloc(sizeof(int)*len);
//申请空间
assert(brr != NULL);
int i = 0;
//从第一个开始
int s1 = 0;
//指向的一个元素
int e1 = s1 + gap - 1;
//指向第一个归并段的最后一个元素
int s2 = e1 + 1;
//第二段的第一个元素
int e2 = s2 + gap - 1 < len - 1 ? s2 + gap - 1:len - 1;
//判断e2的位置 若超出len 则指向len-1
while(s2 < len)//当前有两个归并端
{
while(s1 <= e1 && s2 <= e2)
{
if(arr[s1] < arr[s2])//第一个归并段的开头与第二个归并段的开头比较
{
brr[i++] =arr[s1++];
}
else
{
brr[i++] = arr[s2++];
}
}
while(s1 <= e1)
{
brr[i++] = arr[s1++];
}
while(s2 <= e2)
{
brr[i++] =arr[s2++];
}
s1 = e2 + 1;
//第二次重新合并后重新开始
e1 = s1 + gap - 1;
s2 = e1 + 1;
e2 = s2 + gap - 1 < len ? s2 + gap -1:len - 1;
}
while(s1 < len)
{
brr[i++] = arr[s1++];
}
for(int i = 0;
i < len;
i++)
{
arr[i] = brr[i];
}
free(brr);
}
void Mearge_Sort(int *arr,int len)
{
for(int i=1;
i
总结:
1. 当n比较小时,可以直接采用直接插入排序或者选择排序;
2.若数据初始状态基本有序(正序),选择直接插入排序、冒泡排序或者快速排序为宜;
3.若n比较大,则采用时间复杂度为O(nlong2n)的排序算法:快速排序、堆排序或者归并排序;
4.快速排序是目前基于比较的排序中被认为最好的方法,当待排关键字是随机分布时,快速排序的平均时间最短;
5.堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况,所以这两个排序实际运用的时候可以比较一下,选择最优的;但是这两种排序都是不稳定的。
6.若要求排序稳定,则可以选用归并排序,但是实际运用的时候通常可以将它和直接插入排序结合使用,先利用直接插入排序求得较长有序子序列,然后再两两归并。
推荐阅读
- 数据结构与算法|数据结构与算法Java(六)——排序算法
- c语言时尚编程百例,C语言时尚编程百例
- c语言时尚编程百例,C语言时尚编程百例(含1CD)
- C语言入门I|C语言入门I love China,C语言从入门到精通
- 复习——高级语法对象原型,es5新增语法
- 数仓建模—ID Mapping
- R语言数据可视化绘图Slope|R语言数据可视化绘图Slope chart坡度图画法
- 社工|如何防止社工钓鱼——软件伪造
- 芯片|ARM、DSP、FPGA比较——非常详细深入
- (stm32学习总结)—对寄存器的理解|(stm32学习总结)—对寄存器的理解 _