? ? ? ? ? ? ? ? ? ? ? ?? ? ?
?个人主页 :阿然成长日记 ?点击可跳转
? 个人专栏: ?数据结构与算法?C语言进阶
? 不能则学,不知则问,耻于问人,决无长进
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
文章目录
- 一、冒泡排序
- 1.原理:
- 2.流程图:
- 3.代码:
- 4.测试结果:
- 5.时间复杂度
- 二、选择排序
- 1.原理:
- 2.流程图:
- 3.代码:
- 4.测试结果:
- 5.时间复杂度
- 三、直接插入排序
- 1.原理:
- 2.流程图:
- 3.代码:
- 4.测试结果:
- 5.时间复杂度
一、冒泡排序
1.原理:
?每次从a]0]开始,从左到右,相邻元素依次进行比较。
?每比较完一轮,序列中最大的一个或最小的一个就被换到了数组最后的位置,数组下标-1。
?继续从头开始下一轮。
2.流程图:
3.代码:
//冒泡排序
int* BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j + 1] < a[j])
{
int tmp = a[j + 1];
a[j + 1] = a[j];
a[j] = tmp;
}
}
}
return a;
}
4.测试结果:
5.时间复杂度
O(N^2)
文章来源地址https://www.uudwc.com/A/20jp1/
二、选择排序
1.原理:
? 第一次选择a[0]元素,开始向后遍历同时找最大值,和最小值,最大值放到末尾,最小值放到开头。
?第二次选择a[1]元素,开始向后遍历同时找最大值,和最小值,最大值放到末尾,最小值放到开头,直到到end-1位置。
?重复上述操作注意:
如果max在beain位置,会造成排序错误,只需max = min即可;
2.流程图:
此流程图是在遍历时只找最小值的方法;
而我们选择优化这个排序,通过在遍历时同时寻找最大值和最小值,来提升排序效率。
3.代码:
//选择排序
void SlectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while(begin<end)
{
int max = begin;
int min = begin;
for (int i = begin+1; i <= end; i++)
{
if (a[min] > a[i])
{
min = i;
}
if (a[max] < a[i])
{
max = i;
}
}
//先交换最小值到左边,
Swap(&a[begin], &a[min]);
//特殊情况。如果max在beain位置,会造成排序错误
if (begin == max)
{
max = min;
}
//在交换最大值到右边
Swap(&a[end], &a[max]);
begin++;
end--;
}
}
4.测试结果:
5.时间复杂度
O(N^2)
三、直接插入排序
1.原理:
?>内循环:每次取end+1下标位置值保存到tmp中,从end下标处向前作比较,如果比他小,就将该元素后移,如果大于或等于就停止,并将tmp值赋值给end+1位置,直到end小于0位置,
?>外循环:end++
2.流程图:
3.代码:
//直接插入排序
int* InsetSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = tmp;
}
return a;
}
4.测试结果:
文章来源:https://www.uudwc.com/A/20jp1/
5.时间复杂度
O(N^2)