今天我們繼續(xù)來(lái)講排序算法,歸并排序,難度一般,但是效率也還不錯(cuò)。
老規(guī)矩,先搞清楚原理,再寫(xiě)代碼。
歸并排序分為兩個(gè)步驟,先是拆分,然后再合并。
我們先來(lái)看下合并。
假設(shè)有兩個(gè)有序的數(shù)組,一個(gè)是1、3、5,一個(gè)是2、4、6、8,把他們合并成一個(gè)有序的數(shù)組。 ?
這個(gè)操作應(yīng)該極其簡(jiǎn)單。兩個(gè)下標(biāo),一塊新的內(nèi)存。
1和2比較,1小,把1放在新的內(nèi)存中,x向后走。
2和3比較,2小,把2放在內(nèi)存中,y向后走。
下面依次把4和5放進(jìn)去,最后x達(dá)到了末尾,y變成了6的下標(biāo),那就把y后面的數(shù)據(jù)全部放進(jìn)去就行。
這個(gè)過(guò)程就是合并。
那么問(wèn)題又來(lái)了,去哪找兩個(gè)有序的數(shù)組。
這個(gè)就需要對(duì)數(shù)組做拆分。 ?
比如數(shù)組有8個(gè)元素,我們先從中間拆開(kāi),得到兩個(gè)數(shù)組,每個(gè)4個(gè)元素。
但是這兩個(gè)數(shù)組也不是有序的,于是對(duì)兩個(gè)數(shù)組繼續(xù)拆分。
左邊是兩個(gè)數(shù)組,每個(gè)數(shù)組兩個(gè)元素,右邊也一樣。
這樣還不夠,繼續(xù)拆分,最后得到的數(shù)組只有一個(gè)元素。
如果一個(gè)數(shù)組只有一個(gè)元素,那么它一定就是有序的。
這個(gè)過(guò)程就需要用到遞歸。
過(guò)程清楚了,下面就是用代碼來(lái)實(shí)現(xiàn)它。
#include歸并排序難度不大,但是和堆排序一樣,數(shù)據(jù)越多,順序越亂,效率越高。#include #include #define SIZE 100000 void merge(int *a, int start, int mid, int end) { int left_len = mid - start + 1; int right_len = end - mid; int *L = (int *)malloc(sizeof(int) * left_len); int *R = (int *)malloc(sizeof(int) * right_len); int i, k = start, j; for (i = 0; i < left_len; i++, k++) { L[i] = a[k]; } for (i = 0; i < right_len; i++, k++) { R[i] = a[k]; } for (i = 0, j = 0, k = start; i < left_len && j < right_len; k++) { if (L[i] > R[j]) { a[k] = R[j++]; } else { a[k] = L[i++]; } } if (i < left_len) { for (; i < left_len; i++, k++) { a[k] = L[i]; } } if (j < right_len) { for (; j < right_len; j++, k++) { a[k] = R[j]; } } free(L); free(R); } void merge_sort(int *a, int start, int end) { if (start >= end) return; int mid = (end + start) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge(a, start, mid, end); } int main() { int num, arr[SIZE] = {0}, i; //隨機(jī)產(chǎn)生數(shù)組 srand(time(NULL)); for (i = 0; i < SIZE; i++) { arr[i] = rand() % 100; } merge_sort(arr, 0, SIZE - 1); for (i = 0; i < SIZE; i++) { printf("%d ", arr[i]); } printf(" "); return 0; }
當(dāng)然,歸并排序的缺點(diǎn)就是,需要更多的內(nèi)存空間。
審核編輯:劉清
-
MID
+關(guān)注
關(guān)注
1文章
40瀏覽量
11629 -
printf函數(shù)
+關(guān)注
關(guān)注
0文章
31瀏覽量
6071
原文標(biāo)題:排序算法之歸并排序
文章出處:【微信號(hào):學(xué)益得智能硬件,微信公眾號(hào):學(xué)益得智能硬件】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
十大排序算法總結(jié)
嵌入式stm32實(shí)用的排序算法 - 交換排序
各種排序算法的時(shí)間空間復(fù)雜度、穩(wěn)定性
C語(yǔ)言教程之幾種排序算法
常用排序算法分析
如何去實(shí)現(xiàn)并驗(yàn)證一種歸并排序?

解析數(shù)據(jù)結(jié)構(gòu)的常用七大排序算法
隨機(jī)數(shù)字排序教程

排序算法之“歸并算法”介紹

評(píng)論