归并排序的C语言实现

2019-11-06 07:14:44

字体：大中小

来源：转载

供稿：网友

实现如下:

#include <stdio.h>#include <stdlib.h>#define SIZE 20void initArray(int array[], const int size);void PRintArray(int array[], const int size);void merge_sort(int array[], const int head, const int tail);void merge(int array[], const int head, const int mid, const tail);int main(int argc, char const *argv[]){ int array[SIZE]; initArray(array, SIZE); printArray(array, SIZE); merge_sort(array, 0, SIZE - 1); printArray(array, SIZE); return 0;}void initArray(int array[], const int size) { srand(time(NULL)); int count = 0; for (count = 0; count < size; count++) { array[count] = rand() % size + 1; }}void printArray(int array[], const int size) { int count = 0; printf("The current array is:/n"); for (count = 0; count < size; count++) { printf("%d ", array[count]); } printf("/n");}void merge_sort(int array[], const int head, const int tail) { if (head >= tail) return; int mid = (head + tail) / 2; merge_sort(array, head, mid); merge_sort(array, mid + 1, tail); merge(array, head, mid, tail);}void merge(int array[], const int head, const int mid, const int tail) { int temp[SIZE]; int i = head, j = mid + 1; int count = 0; while (i <= mid && j <= tail) { if (array[i] <= array[j]) { temp[count] = array[i]; i++; } else { temp[count] = array[j]; j++; } count++; } for (; i <= mid; i++, count++) { temp[count] = array[i]; } for (; j <= tail; j++, count++) { temp[count] = array[j]; } for (i = 0; i < count; i++) { array[head + i] = temp[i]; }}

程序使用标准函数库中函数rand随机产生SIZE个随机数并对其进行归并排序。归并排序是稳定非原地的排序，其主要思想为将待排序数分为两部分，分别对其递归进行归并排序。当到底层只剩下一个数字时递归结束并对其进行merge操作。merge操作将两个已排序的数组合并成一个已排序的数组。归并排序算法渐近确界为Θ(nlogn) $Θ(nlogn)$ 。计算过程见算法导论第二章。

上一篇：玲珑学院OJ 1103 萌萌哒的第八题【dp+线段树】

下一篇：随想录（git操作）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注