归并排序是一种常用的排序算法,其原理是将每一个数看作一个有序序列,然后不断地将两个相邻的有序序列合并成一个有序序列,最后剩下一个有序序列就是排序后的结果。用到的是递归和分治思想。
#include<iostream>
#include<malloc.h>
using namespace std;
void merge(int arr[], int tempArr[], int left, int mid, int right){
int l_pos = left; //左半区第一个未排序的元素位置
int r_pos = mid+1; //右半区第一个未排序的元素位置
int pos = left; //存入临时数组时的元素位置
//进行归并排序的合并操作
while(l_pos<=mid && r_pos<=right){
if(arr[l_pos] < arr[r_pos]){
tempArr[pos++] = arr[l_pos++];
}else{
tempArr[pos++] = arr[r_pos++];
}
}
//左半区有剩余元素
while(l_pos <= mid){
tempArr[pos++] = arr[l_pos++];
}
//右半区有剩余元素
while(r_pos <= right){
tempArr[pos++] = arr[r_pos++];
}
//把合并好的临时数组复制回原始数组
pos = left;
while(pos <= right){
arr[pos] = tempArr[pos];
pos++;
}
}
void msort(int arr[], int tempArr[], int left, int right){
if(left < right){ // 有两个及以上的元素时进行划分
int mid = (right + left) / 2; // 找到中间的位置
msort(arr, tempArr, left, mid); // 递归划分arr数组的左半部分
msort(arr, tempArr, mid+1, right); // 递归划分arr数组的右半部分
merge(arr, tempArr, left, mid, right); // 合并已经排序的部分
}
}
// 归并排序入口
void MergeSort(int arr[], int n){
// 进行归并排序的原始数组arr, 数组长度n
// 申请相同长度的临时数组空间
int *tempArr = (int*)malloc(n * sizeof(int));
if(tempArr){
cout << "Allocate Memory successfully" << endl;
msort(arr, tempArr, 0, n-1);
for(int i=0; i<n; i++){
cout << *(tempArr+i) << " ";
}
free(tempArr);
}else{
cout << "error: failed to allocate memory!" << endl;
}
}
int main(){
int arr[9] = {3, 56, 32, 11, 14, 20, 39, 45, 109};
MergeSort(arr, 9);
return 0;
}