目前更新3种排序算法
排序算法
前言
没想到嵌入式C语言课程进行的这么快，开始讲到排序的算法了，老朋友又来了😂。在学习Java的时候排序算法也只是讲了一下，这次嵌入式学习这点却很重要（毕竟不是包装哈哈🤓）。不过感觉进度上来，提前预习那点东西也快没用了，快没什么装逼的资本了。之后的数据结构也看的断断续续，一周多链表还没看完，为了以后能依旧展现装逼风采，立个flag🚩月底结束线性表、栈与队列！这次排序算法的总结就做为一个良好的开始吧😆
冒泡排序
冒泡排序！话不多说直接上图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <stdio.h>
void swap(int arr[], int i, int j)
{
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
void output(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
printf("%d\n", arr[i]);
}
void bubble_sort(int arr[], int size)
{
int i, j;
for(i = 1; i < size; i++)
{
for(j = 0; j < size - i; j++)
swap(arr, j, j+1);
}
}
int main()
{
int arr[] = {5, 4, 3, 2, 1};
int size = sizeof(arr) / sizeof(int);
bubble_sort(arr, size);
output(arr,size);
return 0;
}
|
怎么说呢，感觉最主要的是第21、23行代码
1
2
3
4
5
6
7
8
9
| void bubble_sort(int arr[], int size)
{
int i, j;
for(i = 1; i < size; i++)
{
for(j = 0; j < size - i; j++)
swap(arr, j, j+1);
}
}
|
我们在循环中拿第一个元素和后一个元素进行比较，如果后一个数大就交换（从小到大排序），依次类推，第一次外层循环结束后，我们就把最大的数放到了数组的最后一位。第一次外层循环结束后，数组的第一个位置就排好了，每次内层循环都是从数组第一位开始的，而结束是在数组size-i位置，所以这个和上一个的区别就是每次外层循环把最大的值放在数组末尾。
一开始会疑惑为什么i要从1开始，其实想想就能理解，后面的都排好第一位的数据就不用管了。
选择排序
还是一样直接上图
大体思路就是第一次循环我们把数组第一个数据假设为最小的值，接着我们在内层循环中将后面的数据一一和它相比，如果发现有比它更小的数据，就把数组下标和第一个数据的下标交换，然后再对比其余的数据，直到找到最小的下标，我们再将下标和我们假设的最小下标进行比较，如果不相等就使用swap函数进行交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void select_sort(int arr[], int size)
{
int i, j;
for(i = 0; i < size - 1; i++)
{
int min = i;
for(j = i + 1; j < size; j++)
{
if(arr[min] > arr[j])
min = j;
}
if(i != min)
swap(arr, i, min);
}
}
|
插入排序
一开始对插入排序还是一知半解，不过看了动图一下子就清楚了。插入排序就像是扑克牌抓牌，抓到的牌插入到我们的手牌中的过程。我们可以抽象成两个数组，插入排序的过程就是选择无序数组的首位，插入到有序数组的对应位置，知道全部数据插入完成为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void insert_sort(int arr[], int size)
{
int i, j;
for(i = 1; i < size; i++)
{
j = i;
int temp = arr[i];
for(; j > 0; j--)
{
if(arr[j - 1] > temp)
arr[j] = arr[j - 1];
else
break;
}
}
}
|
其中外层循环是已经排好的数据，每次选取未排序的第一个数据，而内层每一次循环可以看作将拿到的第一个数据插入到对应位置，而在对应位置和后面位置的数据就要往后挪一位。
不过这样写还是不太严谨，如果数组长度为空或者只有一个元素的时候，对造成数组下标越界，这在C语言中时不会检查的，我们要加入相应的判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void insert_sort(int arrp[], int size)
{
int i, j;
if(size == 0 || size == 1)
return;
for(i = 1; i < size; i++)
{
j = i;
int temp = arr[i];
for(; j > 0; j--)
{
if(arr[j - 1] > temp)
arr[j] = arr[j - 1];
else
break;
}
}
}
|
