嵌入式Linux
喜欢看排序算法动态效果的，可以看看这个网站
https://visualgo.net/zh/sorting
里面很多算法的动画解释，可以看到算法的排序效果，而且还附带了伪代码的实现过程。
本来想录制几张动图放上来，但是因为图片较大，传不上来，公众号对动态图片有限制，喜欢的同学可以点击我上面的链接，自己去尝试一下。
我画了一个图片，用来表示归并排序的运算过程
排序的过程
先把需要排序的数据分成两份。
把两份的数据依次进行排序并组合在一起。
再把排序后的两组数据进行并入一起排序。
好了，写代码吧
我们先实现，「把两份的数据依次进行排序并组合在一起」
下面是实现这个的算法过程
/*
* r[] : 需要排序的数组
* s[] : 排序后保存数据的数组
* left: 排序的起始位置
* mid : 排序的中间位置
* right:排序的最右边位置
*/
int merge(int r[],int s[],int left,int mid,int right)
{
int i,j,k;
i=left;
j=mid+1;
k=left;
for(;i <= mid && j<=right;){
if(r[i]<=r[j])
s[k] = r[i++];
else
s[k] = r[j++];
k++;
}
for(;i<=mid;)
s[k++]=r[i++];
for(;j<=right;)
s[k++]=r[j++];
return 0;
}
如果我们对两个数进行排序
经过上面的那个函数排序后，我们会把[3,1]排序成[1,3]。
——
那，如果我们需要对4个数字进行排序呢？
我们需要先把4个数字分成2组
然后，我们需要依次对上面的两组数据进行排序，得到下面新的两组数据
然后，我们需要把已经排序的两个数组进行排序
s[] 是保存的排序结果，r[] 是需要排序的数组。
left，mid，right 是排序数组中的三个位置。
left = 0;
right = 3;
mid = ( left + right )/2 = 1;
进入函数体，我们需要三个变量来协助我们进行运算
i = left = 0;
j = mid +1 = 1 +1 = 2;
k = left = 0;
它们看起来是这样子的
把r[i] 和 r[j] 两个数进行比较，把小的那个数放到s[k] 里面，然后再移位
比较之后变成
然后再执行下面的代码
for(;i <= mid && j<=right;){
if(r[i]<=r[j])
s[k] = r[i++];
else
s[k] = r[j++];
k++;
}
这时候 j = 4
这时候就退出了 for 循环
退出for 循环后 就开始执行下面的 for 循环
for(;i<=mid;)
s[k++]=r[i++];
for(;j<=right;)
s[k++]=r[j++];
这样后，会变成这样
这样就退出 merge 函数
经过上面的过程，我们需要应该有点悟性，我们需要使用递归来解决这些问题
可以看下面的文章了解啥是递归
然后呢，我们就写了一个这样的递归函数，放心吧，在学习树的时候，也是需要这种递归操作的。
/*
* r[] : 需要排序的数组
* s[] : 排序后保存数据的数组
* left: 排序的起始位置
* right:排序的最右边位置
*/
int merge_sort(int r[],int s[],int left,int right)
{
int mid;
int t[20];
if(left==right)
s[left]=r[right];
else
{
mid=(left+right)/2;
merge_sort(r,t,left,mid);/*sort left~mid*/
merge_sort(r,t,mid+1,right);/*sort mid+1~right*/
merge(t,s,left,mid,right);/*merge sort left,mid,right*/
}
return 0;
}
这个函数就是递归函数，递归最后退出机制是
left == right
再然后，我们需要一个 main 函数
完整的代码实现如下
#include <stdio.h>
#include <stdlib.h>
/*
* r[] : 需要排序的数组
* s[] : 排序后保存数据的数组
* left: 排序的起始位置
* mid : 排序的中间位置
* right:排序的最右边位置
*/
int merge(int r[],int s[],int left,int mid,int right)
{
int i,j,k;
i=left;
j=mid+1;
k=left;
for(;i <= mid && j<=right;){
if(r[i]<=r[j])
s[k] = r[i++];
else
s[k] = r[j++];
k++;
}
for(;i<=mid;)
s[k++]=r[i++];
for(;j<=right;)
s[k++]=r[j++];
return 0;
}
/*
* r[] : 需要排序的数组
* s[] : 排序后保存数据的数组
* left: 排序的起始位置
* right:排序的最右边位置
*/
int merge_sort(int r[],int s[],int left,int right)
{
int mid;
int t[20];
if(left==right)
s[left]=r[right];
else
{
mid=(left+right)/2;
merge_sort(r,t,left,mid);/*sort left~mid*/
merge_sort(r,t,mid+1,right);/*sort mid+1~right*/
merge(t,s,left,mid,right);/*merge sort left,mid,right*/
}
return 0;
}
int main()
{
int a[8] = {6,5,3,1,8,7,2,4};
int i;
merge_sort(a,a,0,7);
for(i=0;i<sizeof(a)/sizeof(a[0]);i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
程序输出
1 2 3 4 5 6 7 8
算法复杂度，翻开以前写的文章
中间是 mid = (left+right)/2
可以猜到是 O(logN) ,也就是排序的时间是用logN时间去拆分的，而且拆分的时候，我们还需要进行排序，也就是代码里面提到的，排序的时间是O(n)，所以在拆分和排序中需要花费的时间是 O(NlogN)。
拆分需要花费 O(logN) ，那合并的时候自然也需要花费O(logN)
总的算法时间是
O(NlogN + logN) = O(NlogN)
