归并排序

我们知道把两个已经排好序的数组合并成一个是很容易,也非常快的.于是根据这种思路就有个归并排序.

归并排序(Merge Sort)

并归排序利用了递归的思想,把数组分割成很多小的数组序列,然后两两合并,最终整个数组有序.因为递归到一个子数组序列只有一个元素时,然后将这样的数组合并就得到2个元素的有序数组,依次类推.

//合并两个子数组序列,以mid为中间点,begin,end为前后界限,分割成两个子序列.

void MergeSortedArr(int* arr, int begin , int mid , int end, int* tmpArr)

{

int lBegin = begin; //左边序列的起始索引号

int lEnd = mid; //左边序列的最后索引号

int rBegin = mid + 1;

int rEnd = end;

int k = 0; //两个子序列元素个数之和

while( lBegin <= lEnd && rBegin <= rEnd) //当有一个子序列遍历完了退出循环

{

if(arr[lBegin] <= arr[rBegin])

tmpArr[k++] = arr[lBegin++];

else

tmpArr[k++] = arr[rBegin++];

}

while(lBegin <= lEnd)

tmpArr[k++] = arr[lBegin++];

while(rBegin <= rEnd)

tmpArr[k++] = arr[rBegin++];

for(int i = 0; i < k; i++)

arr[begin + i] = tmpArr[i];

}

void MegerSort(int* arr, int begin , int end, int* tmpArr)

{

if( begin < end)

{

int mid = (begin + end) /2;

MergeSort(arr, begin , mid , tmpArr); //将左边序列排序

MergeSort(arr, mid + 1, end, tmpArr); //将右边序列排序

MergeSortedArr(arr, begin , mid, end, tmpArr); //合并两个序列

}

}

测试代码:

int arr[] = { 1,3,2,4,5,7,6,8,9};

int len = sizeof(arr)/sizeof(int);

int* tmpArr = new int[len];

MergeSort(arr, 0, len - 1, tmpArr);

delete []tmpArr;