C語言簡明講解歸並排序的應用
一.歸並排序
1.1歸並排序引入
對於堆排序來說，因為用到瞭完全二叉樹的深度是（log2n+1）的特性，所以效率就比較高，但是堆結構的設計比較復雜，現在我們想要可以直接利用完全二叉樹來排序的方法，這個方法就是歸並排序。
1.2歸並排序的概念
歸並排序是建立在歸並操作上的一種有效的排序算法，歸並排序對序列的元素進行逐層折半分組，然後從最小分組開始比較排序，合並成一個大的分組，逐層進行，最終所有的元素都是有序的。
1.3歸並排序的原理
原理：假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2或1的有序子數列，再兩兩歸並，如此重復直到得到一個長度為n的有序序列為止。
1.4實例說明
(1).以4，5，8，1，7，2，6，3為例，排序過程：
(2).以84，9，18，19，48，12，90，84，8，12為例，排序過程：
這裡的兩兩合並指的是兩個組合並；
每組的數據單獨看是有序的。
1.5具體步驟說明
以實例中的第一個為例：
序列逐層拆分如下：
然後從下往上逐層合並，首先對第一層序列1（隻包含元素4）和序列2（隻包含元素5）進行合並
創建一個大序列，序列長度為兩個小序列長度之和，A、B指針分別指向兩個小序列的第一個元素，C指向大序列的第一個元素
比較A、B指向的元素，4小於5，將4填入C指向的元素，C、A往右移一位
此時，序列1已經沒有元素，將序列2的元素依次填入大序列中
序列8和1，序列7和2，序列6和3，用同樣的方式填入新的序列
接著，以4、5為序列1，1、8為序列2，繼續進行合並
創建一個序列長度為4的大序列，A指向序列1的第一個元素4，B指向序列2的第一個元素1，C指向大序列的第一個元素
4和1比較，4大於1，1填入C指向的元素，C、B往右移一位
4和8比較，4小於8，4填入C指向的元素，C、A往右移一位
5和8比較，5小於8，5填入C指向的元素，C、A往右移一位
自此，序列1已經沒有元素，將序列2的元素依次填入大序列中
序列2、7和序列3、6以同樣的方式合並成新的序列
最後，將序列1、4、5、8和序列2、3、6、7以同樣的方式繼續合並成新的序列
所有元素均已排好。
1.6代碼實現
void MergeSort(int *arr, int len)
{
for(int i=1; i<len; i*=2)// O（logn）
{
Merge(arr, len, i);
}
}
//一次劃分函數 核心函數 //返回基準值最終所在下標
int Partition(int *arr, int left, int right)
{
//先講arr數組裡的[left， right]的第一個值 作為基準值
int tmp = arr[left];
while(left < right)
{
while(left<right && arr[right] > tmp)//左右邊界沒有相遇且當前右邊的值大於基準值tmp
right--;
if(left < right)//如果此時，左右邊界沒有相遇，那就隻能證明右邊right找到瞭一個小於等於基準值tmp的值
{
arr[left] = arr[right];
}
else
{
break;
}
while(left<right && arr[left] <= tmp)//左右邊界沒有相遇且當前左邊的值小於等於基準值tmp
left++;
if(left < right)//如果此時，左右邊界沒有相遇，那就隻能證明左邊left找到瞭一個大於基準值tmp的值
{
arr[right] = arr[left];
}
else
{
break;
}
}
arr[left] = tmp;//此時 因為 left == right
return left;//return right ok
}
1.7性能分析
- 時間復雜度：最好，最壞，平均的時間復雜度均為O(nlogn)。
- 空間復雜度：空間復雜度O（n）。
- 穩定性：穩定。
到此這篇關於C語言簡明講解歸並排序的應用的文章就介紹到這瞭,更多相關C語言歸並排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！