湖南营销型网站建设报价,设计游戏的软件,wordpress编辑器不要用5.0,wordpress 文章页 下载地址归并排序#xff08;稳定的排序#xff09;#xff1a;
归并排序是一种分治策略的排序算法#xff0c;其基本思想是将待排序数组分成两个子数组#xff0c;分别对这两个子数组进行排序#xff0c;然后合并这两个已经排序好的子数组#xff0c;最终得到完整的已排序数组… 归并排序稳定的排序
归并排序是一种分治策略的排序算法其基本思想是将待排序数组分成两个子数组分别对这两个子数组进行排序然后合并这两个已经排序好的子数组最终得到完整的已排序数组。
具体实现过程如下
将待排序数组从中心位置分成两个子数组分别为左子数组和右子数组。对左子数组和右子数组分别进行递归排序。将排好序的左子数组和右子数组合并成一个有序数组。重复执行步骤3直到所有子数组都被合并成一个有序数组。
归并排序的时间复杂度为O(nlogn)空间复杂度为O(n)。它是一种稳定排序算法适用于处理大规模数据的排序任务。
下面我们来看一下代码如何实现
首先是对数组划分
void mergesort(int a[],int low,int high)
{if (low high){int mid (low high) / 2;//从中间划分两个子序列mergesort(a, low, mid);//对左侧子序列进行递归排序mergesort(a, mid 1, high);//对右侧子序列进行递归排序merge(a, low, mid, high);//归并排序}
}
再进行归并
void merge(int a[], int low, int mid, int high)
{int* B (int*)malloc(sizeof(int) * (high 1));//辅助数组Bint i 0;int j 0;int k 0;for (k low; k high; k)B[k] a[k];//将a中所有元素复制到B中for (i low, j mid 1, k i; i mid j high; k){if (B[i] B[j])//比较B中的左右两段中的元素a[k] B[i];//将较小值复制到a中elsea[k] B[j];}while (i mid)//若第一个表为检测完一次复制到a中a[k] B[i];while (j high)//若第二个表为检测完一次复制到a中a[k] B[j];
}
完整测试代码
#includestdio.h
#includestdlib.h
void merge(int a[], int low, int mid, int high)
{int* B (int*)malloc(sizeof(int) * (high 1));//辅助数组Bint i 0;int j 0;int k 0;for (k low; k high; k)B[k] a[k];//将a中所有元素复制到B中for (i low, j mid 1, k i; i mid j high; k){if (B[i] B[j])//比较B中的左右两段中的元素a[k] B[i];//将较小值复制到a中elsea[k] B[j];}while (i mid)//若第一个表为检测完一次复制到a中a[k] B[i];while (j high)//若第二个表为检测完一次复制到a中a[k] B[j];
}
void mergesort(int a[],int low,int high)
{if (low high){int mid (low high) / 2;//从中间划分两个子序列mergesort(a, low, mid);//对左侧子序列进行递归排序mergesort(a, mid 1, high);//对右侧子序列进行递归排序merge(a, low, mid, high);//归并排序}
}
int main()
{int a[] { 49,38,65,97,76,13,27 };int sz sizeof(a) / sizeof(a[0]);int j 0;printf(原始待排序的数组为);for(j 0; j sz; j)printf(%d , a[j]);mergesort(a,0,sz-1);printf(\n归并排序后的数组为);for (j 0; j sz; j)printf(%d , a[j]);return 0;
}
