歸并排序

#include"iostream"

using namespace std;

//讓兩個數組融合

int Merge(int a[], int low,int mid,int high){

//space暫時的數組去存儲融合好的兩個數組！

int *space = (int *)malloc(sizeof(int)*(high - low + 1));

if (space == NULL){

return -1;

}

int l = low;

int m = mid+1;

int h = high; 

int i = 0;

//紅色部分是将兩個數組融合的關鍵

while ((l<= mid)&&(m <= high)){

space[i++] = (a[l]>a[m]) ? a[m++] : a[l++];

//注意這裡你取走誰的值就實行自加；

while (l <=mid){//第一個數組有剩餘！

space[i++] = a[l++];

while (m <= high){//第二個數組有剩餘！

space[i++] = a[m++];

for (int i = low,k=0; i <=high; i++,k++){

a[i] = space[k];//讓臨時數組的值全都指派過去

return 0;

void MergeSort(int a[], int low, int high){

if (low < high){

int mid=(low+high)/2;

//采用分冶法進行排序。讓數組中一部分一部分的排好。最後慢慢融合

MergeSort(a, low, mid);//讓a[low]到a[mid]排好序！

MergeSort(a, mid + 1, high);//讓a[mid+1]到a[high]排好序！

Merge(a, low, mid, high);//最後融合

return;

int main()

{

//int array[] = {21, 25, 49, 25, 16, 8};

int array[] = { 21, 25,56,32,14,5,7,8,64 };

int len = sizeof(array) / sizeof(*array);

MergeSort(array, 0,len-1);

for (int i = 0; i < len; i++){

cout << array[i] << " ";

cout << endl;

system("pause");

本文轉自 神迹難覓 51CTO部落格，原文連結：http://blog.51cto.com/ji123/1926062，如需轉載請自行聯系原作者