C++实现归并排序（详细代码）

#include<iostream> using namespace std; #define num 10

void merge(int* a, int len); void merge(int* a, int l, int m, int r); //归并排序

//把一个数组拆成两等份 递归 void mergeSort(int * a,int l, int r) { if (l == r) { return; } int m = l + (r - l) / 2; mergeSort(a, l, m); mergeSort(a, m + 1, r); merge(a, l, m, r);

}

//合并两个数组为一个 a为数组首地址 l为左边元素下标 m为中间元素下标 r为右边元素下标 void merge(int* a, int l, int m, int r) { //准备临时数组 int* pTemp = NULL; int len = r - l + 1; pTemp = new int[len]; int k = 0;//临时数组下标 int left = l;//左边数组第一个下标 int right = m+1;//右边元素第一个下标

//将数据放入临时数组 while (left <= m && right <= r) { if (a[left] < a[right]) { pTemp[k++] = a[left++]; } else { pTemp[k++] = a[right++]; } } while(left <= m) { pTemp[k++] = a[left++]; } //放剩下的数组 while (right <= r) { pTemp[k++] = a[right++]; }

//拷贝回原数组并释放内存 //int i = 0; //for (int j = 0; j < num; j++) //{ // a[i++] = pTemp[j]; //} memcpy(a+l, pTemp, sizeof(int)*len); delete[] pTemp; pTemp = NULL; }

void merge(int* a, int len) { mergeSort(a, 0, len - 1); }

void print(int* a,int len) { for (int i = 0; i < len; i++) { cout << a[i] << " "; } }

int main() { int a[num] = { 907,37,2,52,527,666,998,386,667,233 }; int len = sizeof(a) / sizeof(a[0]); print(a, len);

merge(a, len ); print(a, len); system("pause"); return 0; }