數(shù)據(jù)結(jié)構----歸并排序

原理：參考趣學數(shù)據(jù)結(jié)構

代碼：

#include<stdio.h> #include<stdlib.h> #define N 100 void guiBingSort(int a[], int l, int h,int length) {//歸并排序int mid = (l + h) / 2;int* b =(int *)malloc(N*sizeof(int));int i = l, j = mid + 1, k = 0;if (i < j) {while (i<=mid&&j<=h) {//對排好序的兩堆元素 比較排序if (a[i] > a[j]) {b[k++] = a[j++];}else {b[k++] = a[i++];}}while (i <= mid) {//剩余的一堆排好序的直接尾添加b[k++] = a[i++];}while (j <= h) {//剩余的一堆排好序的直接尾添加b[k++] = a[j++];}}for (i = l; i <=h; i++) {//l-h數(shù)組這段元素排序，并對a重新賦值a[i] = b[i-l];}free(b);//釋放b數(shù)組內(nèi)存空間 } void fenZhi(int a[], int l, int h,int length) {//分治if (l < h) {//2個以上才 分半int mid = (l + h) / 2;fenZhi(a, l, mid ,length);fenZhi(a, mid + 1, h,length);guiBingSort(a, l, h,length);//歸并排序} } void print8(int a[], int length) {for (int i = 0; i < length; i++) {printf("%d ", a[i]);}printf("\n"); } int main() {int a[] = { 1,4,6,7,4,3,2,11,5,7,8,9,6,55 };int length = sizeof(a) / sizeof(a[0]);printf("排序前\n");print8(a, length);fenZhi(a, 0, length - 1,length);printf("排序后\n");print8(a, length);system("pause");return 0; }

測試截圖：

時間復雜度O(nn),空間復雜度O(n)*

如果存在什么問題，歡迎批評指正！謝謝！

總結(jié)

以上是生活随笔為你收集整理的数据结构----归并排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。