排序--歸并排序

2019-11-08 03:03:27

字體：大中小

來源：轉載

供稿：網友

基本原理：利用遞歸和分治的思想。原理見下圖：利用歸并排序，對數組[10 4 6 3 8 2 5 7]進行排序(升序)。這里寫圖片描述

復雜度分析：分割的次數為logN,共有N個數，時間復雜度為(N*logN)。

代碼實現(C)

#include <stdio.h> void mergearray(int a[], int first, int mid, int last, int temp[]) //將二個有序數列a[first...mid]和a[mid...last]合并//比較二個數列的第一個數，誰小就先取誰，取了后就在對應數列中刪除這個數。然后再進行比較，如果有數列為空，那直接將另一個數列的數據依次取出即可。{ int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; //合并后的數列放在a[]中} void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; //將數列分割成二部分 mergesort(a, first, mid, temp); //遞歸分解數列：左邊有序 mergesort(a, mid + 1, last, temp); //右邊有序 mergearray(a, first, mid, last, temp); //依次將二個有序數列合并 } } int main(){ int a[] = {1,4,2,3,6,5,7,9,8,0}; int n = sizeof(a)/sizeof(a[0]); int b[n]; int i; mergesort(a,0,n-1,b); for(i=0; i<n; i++) {