赞
踩
归并排序:将两段有序的数据合并成一段有序的数据,直到所有的数据有序(二路归并)
#include<stdio.h> #include<stdlib.h> #include<assert.h> //一次归并,gap为归并段的长度 static void Merge(int* arr, int len, int gap)//一次归并时间复杂度O(n) { int low1 = 0; int high1 = low1 + gap - 1; int low2 = high1 + 1; int high2 = low2 + gap < len ? low2 + gap - 1 : len - 1; int* brr = (int*)malloc(len * sizeof(int)); assert(brr != NULL); int i = 0;//brr的下标 //有两个归并段 while (low2 < len) { while (low1 <= high1 && low2 <= high2) { //两个归并段还有数据需要比较 if (arr[low1] <= arr[low2]) { brr[i++] = arr[low1++]; } else { brr[i++] = arr[low2++]; } } //一个归并段已完成,另一个还有数据 while (low1 <= high1) { brr[i++] = arr[low1++]; } while (low2 <= high2) { brr[i++] = arr[low2++]; } //下两个归并段(四个变量往后走) low1 = high2 + 1; high1 = low1 + gap - 1;//越界也没事,因为循环判断条件是low2<len low2 = high1 + 1; high2 = low2 + gap < len ? low2 + gap - 1 : len - 1; } //只有一个归并段 while (low1 < len) { brr[i++] = arr[low1++]; } //将归并好的数据拷贝到arr里 for (int i = 0; i < len; i++) { arr[i] = brr[i]; } free(brr); } void MergeSort(int* arr, int len)//时间复杂度 O(nlogn),空间复杂度O(n),有辅助空间,稳定的 { for (int i = 1; i < len; i *= 2) { Merge(arr, len, i);//一次归并 } } int main() { int a[] = { 2,5,4,6,3,9,8,7 }; int len = sizeof(a) / sizeof(a[0]); MergeSort(a, len); for (int i = 0; i < len; i++) { printf("%d ", a[i]); } }
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。