龙空技术网

归并排序_基本思想

coder人生 78

前言:

如今各位老铁们对“归并排序的流程图”大约比较看重,小伙伴们都想要剖析一些“归并排序的流程图”的相关知识。那么小编在网络上网罗了一些关于“归并排序的流程图””的相关文章,希望各位老铁们能喜欢,兄弟们快快来了解一下吧!

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);

}

标签: #归并排序的流程图