C語言常見排序算法歸并排序
前言
本期為大家?guī)淼氖浅R娕判蛩惴ㄖ械?strong>歸并排序,博主在這里先分享歸并排序的遞歸算法,包您一看就會,快來試試吧~
一、歸并排序
1.1 基本思想
歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法 (Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序 列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。
1.2 算法思想
到這里,我們可以得到一條結論,兩個有序的子序列可以合成一個新的有序子序列,通過遞歸,我們兩個新的有序序列也可以組成新的有序數(shù)列,最終實現(xiàn)排序的目的。有些朋友就會問了,這個我懂,關鍵是咋實現(xiàn)有序數(shù)列,其實非常的簡單,分割遞歸至每個子序列只有一個元素時,是不是就有序啦,然后就可以合成有兩個元素有序的列表嘛,再合成4個,8個……
1.3 程序設計思想
定義一個tmp數(shù)組,可以是動態(tài)開辟的(malloc),用于臨時存放合并后的有序數(shù)據(jù),定義_MergeSort()函數(shù),用于分解,合并數(shù)據(jù)(遞歸實現(xiàn)),參數(shù)有,待處理數(shù)組,數(shù)據(jù)區(qū)間(數(shù)組下標),tmp數(shù)組。
- 判斷區(qū)間是否存在,區(qū)間不存在以及只有一個元素的情況結束程序。
- 分割區(qū)間:mid=(left+right)/2;遞歸左右區(qū)間,分割遞歸至每個子序列只有一個元素。
- 每兩個子序列一組,循環(huán)遍歷每一個元素,if比較兩個子序列各元素的大小,取大或取小,放入tmp數(shù)組,tmp[index++]=子序列++;直到有一個子序列遍歷完,循環(huán)結束。
- 循環(huán)判斷是子序列是否遍歷完畢,未遍歷完畢的子序列剩余元素直接給到tmp數(shù)組。將tmp數(shù)組的對應的元素拷貝回原數(shù)組(已有序)。
1.4 程序?qū)崿F(xiàn)
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>//動態(tài)開辟空間的函數(shù)的頭文件 void _MergeSort(int *a,int left,int right,int *tmp) { //區(qū)間不存在以及只有一個元素的情況結束程序 if (left>=right) { return; } int mid = (left + right) / 2; //假設[left,mid],[mid+1,right]有序,那么我們就可以歸并了 //遞歸使左右區(qū)間有序 //分割遞歸至每個子序列只有一個元素 _MergeSort(a,left,mid,tmp); _MergeSort(a, mid+1,right, tmp); //歸并 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1<=end1&&begin2<=end2)//有一個子序列遍歷完,循環(huán)結束 { if (a[begin1] < a[begin2])//升序,取小 { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //判斷子序列是否遍歷完,未遍歷完畢的子序列剩余元素直接給到tmp數(shù)組 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2<=end2) { tmp[index++] = a[begin2++]; } //拷貝回去 for (int i=left;i<=right;++i) { a[i] = tmp[i]; } } //歸并排序 void MergeSort(int *a,int n) { int* tmp=(int*)malloc(sizeof(int)*n);//動態(tài)開辟與待排序數(shù)組大小相等的一片連續(xù)的空間 _MergeSort(a,0,n-1,tmp);//子函數(shù)實現(xiàn)歸并 free(tmp);//釋放動態(tài)開辟的空間 } //打印 void Print(int* a, int n) { for (int i=0;i<n;++i) { printf("%d ",a[i]); } } int main() { int a[] = {10,6,7,1,3,9,4,2}; MergeSort(a,sizeof(a)/sizeof(a[0])); Print(a,sizeof(a)/sizeof(a[0])); return 0; }
1.5 歸并排序的特性總結
- 1. 歸并的缺點在于需要O(N)的空間復雜度,歸并排序的思考更多的是解決在磁盤中的外排序問 題。
- 2. 時間復雜度:O(N*logN)
- 3. 空間復雜度:O(N)
- 4. 穩(wěn)定性:穩(wěn)定
到此這篇關于C語言常見排序算法歸并排序的文章就介紹到這了,更多相關C語言歸并排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
C++實現(xiàn)主機字節(jié)序和網(wǎng)絡字節(jié)序轉(zhuǎn)換示例
這篇文章主要為大家介紹了C++實現(xiàn)主機字節(jié)序和網(wǎng)絡字節(jié)序轉(zhuǎn)換示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11C++11中跳轉(zhuǎn)initializer_list實現(xiàn)分析
這篇文章主要介紹了C++11中跳轉(zhuǎn)initializer_list實現(xiàn)分析,實例分析initializer_list<T>初體驗,結合示例代碼給大家介紹的非常詳細,需要的朋友可以參考下2022-04-04C++實現(xiàn)LeetCode(199.二叉樹的右側(cè)視圖)
這篇文章主要介紹了C++實現(xiàn)LeetCode(199.二叉樹的右側(cè)視圖),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08C語言scandir函數(shù)獲取文件夾內(nèi)容的實現(xiàn)
scandir?函數(shù)用于列舉指定目錄下的文件列表,本文主要介紹了C語言scandir函數(shù)獲取文件夾內(nèi)容的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2024-03-03