程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 從排序開始(三)歸並排序

從排序開始(三)歸並排序

編輯:C++入門知識

歸並排序是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。   歸並操作的過程如下: 1.申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合並後的序列 2.設定兩個指針,最初位置分別為兩個已經排序序列的起始位置 3.比較兩個指針所指向的元素,選擇相對小的元素放入到合並空間,並移動指針到下一位置 4.重復步驟3直到某一指針達到序列尾 5.將另一序列剩下的所有元素直接復制到合並序列尾   簡單地說,歸並排序就是將序列不斷地劃分,直到每個序列只有一個元素(一個元素的序列肯定是有序的),然後這些有序序列不斷歸並,合成新的有序序列,最後,歸並成全部有序的序列。   這幅 Wiki 的圖很直觀地解釋了歸並排序:     最差時間復雜度  O(n logn) 最優時間復雜度  O(n) 平均時間復雜度  O(n logn)   穩定性:穩定   實現:  

#include <iostream>  
  
using namespace std;  
  
//歸並操作,將有兩個個有序數列 num[start...mid] 和 num[mid...end] 歸並並。  
//歸並至 sorted 序列,然後復制回原數組  
void merge(int num[], int start, int mid, int end, int sorted[])  
{  
    int i = start, j = mid + 1;  
    int m = mid,   n = end;  
    int k = 0;  
      
    //每次比較兩個元素,直到某個序列到達末尾  
    while (i <= m && j <= n)  
    {  
        if (num[i] <= num[j])  
            sorted[k++] = num[i++];  
        else  
            sorted[k++] = num[j++];  
    }  
      
    //將序列中剩余元素直接復制到 sorted 序列尾  
    while (i <= m)  
        sorted[k++] = num[i++];  
      
    while (j <= n)  
        sorted[k++] = num[j++];  
      
    //將排序好的序列寫回原數組  
    for (i = 0; i < k; i++)  
        num[start + i] = sorted[i];  
}  
  
void mergesort(int a[], int start, int end, int sorted[])  
{  
    if (start < end)  
    {  
        //進行分治  
        int mid = (start + end) / 2;  
        mergesort(a, start, mid, sorted);      
        mergesort(a, mid + 1, end, sorted);   
        merge(a, start, mid, end, sorted);   
    }  
}  
  
bool MergeSort(int num[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(num, 0, n - 1, p);  
    delete[] p;  
    return true;  
}  
  
//簡單測試,建議數據不要太大,那是在刷屏啊 o(╯□╰)o  
int main()  
{  
    int n;  
    //測試 n 個隨機數的排序  
    while(cin>>n)  
    {  
        int *p = new int[n];  
        if (!p)  
        {  
            cout<<"Failed..."<<endl;  
            continue;  
        }  
        for(int i=0;i<n;++i)  
            p[i] = rand();  
        bool flag = MergeSort(p,n);  
        if(!flag)  
        {  
            cout<<"Failed..."<<endl;  
            continue;  
        }  
        for(int i=0;i<n;++i)  
            cout<<p[i]<<' ';  
        cout<<endl;  
        delete []p;  
    }  
    return 0;  
}  

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved