前言:
如今各位老铁们对“归并排序的流程图”大约比较看重,小伙伴们都想要剖析一些“归并排序的流程图”的相关知识。那么小编在网络上网罗了一些关于“归并排序的流程图””的相关文章,希望各位老铁们能喜欢,兄弟们快快来了解一下吧!1.归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列
(1次比较和交换)然后把各个有序的段序列并成一个有序的长序列,不断合并直到原序列全部排好序
void merge(intUarray[], int temp[], int start, int middle, int end) {
// 将两个有序序列array[start, middle]和array[middle+1, end]进行合并
int i = start, m = middle, j = middle + 1, n = end, k = 0;
while(i <= m && j <= n) { // 哪个小就先插哪个, 然后把temp下标和array插入位置的下标++
if (array[i] <= array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
// 插完之后看谁没插完就继续插谁
while(i <= m) temp[k++] = array[i++];
while(j <= n) temp[k++] = array[j++];
// 把temp的元素copy回array中
for (int i = 0; i < k; i++) array[start + i] = temp[i];
}
void mSort(int array[], int temp[], int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
mSort(array, temp, start, middle); // 递归出来以后左边有序
mSort(array, temp, middle + 1, end); // 右边有序
merge(array, temp, start, middle, end); // 合并两个有序序列
}
}
void mergeSort(int array[], int count){
// 定义辅助数组
int *temp = (int *)malloc(sizeof(array[0]) * count);
// 开始进行归并排序
mSort(array, temp, 0, count - 1);
// 释放指针
free(temp);
}
标签: #归并排序的流程图