排序算法之归并排序
一、基本思想归并排序，和快排一样同样采用了分治的思想，将两个（或以上）有序表合并成一个新的有序表。
归并排序步骤如下：
把N个记录看成 N个长度为 1 的有序子表；
进行两两归并使记录关键字有序，得到 N/2 个长度为 2 的有序子表；
重复第2步直到所有记录归并成一个长度为N的有序表为止。
二、算法实现
下面是归并排序算法的递归实现：
#include <iostream>
#include <malloc.h>
using namespace std;
// 合并两个有序部分
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
if (first >= last) {
return;
}
int i = first, j = mid + 1;
int k = first;
while (i <= mid && j <= last) {
if (a[i] > a[j]) {
temp[k++] = a[j++];
} else {
temp[k++] = a[i++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= last) {
temp[k++] = a[j++];
}
// 回写到原来数组中
for (k = first; k <= last; k++) {
a[k] = temp[k];
}
}
// 递归调用归并
void mSort(int* a, int first, int last, int *temp) {
if (first < last) {
int mid = (first + last) >> 1;
mSort(a, first, mid, temp);
mSort(a, mid + 1, last, temp);
mergeArray(a, first, mid, last, temp);
}
}
// 归并排序算法
void mergeSort(int *a, int len) {
int* temp = (int*) malloc(len * sizeof(int));
mSort(a, 0, len - 1, temp);
free(temp);
}
int main() {
int arr[] = { 213, 43, 43, 123, 45, 52, 67, 234, 452, 5, 67 };
int len = 11;
cout << "Before sorting:" << endl;
for (int i = 0; i < len; i++) {
cout << arr[i] << "\t";
}
mergeSort(arr, len);
cout << endl << "After merge sorting:" << endl;
for (int i = 0; i < len; i++) {
cout << arr[i] << "\t";
}
cout << endl;
return 0;
}
三、算法分析
归并排序最好、平均、最坏时间复杂度都是：O(n*log2(n))，
归并排序需要额外的存储空间，其空间复杂度为：O(n).
归并排序和快排、堆排序一样是一种高效的排序算法，在数据规模较大而且存储空间要求足够的情况下是非常好的选择。
四、算法改进
归并排序改进和优化的方向如下：
当问题分割很小到某个规模的时候停止递归，采用简单插入排序；
消除递归调用
消除反复回写
...
下面是改进的一个消除递归算法：
#include <iostream>
#include <malloc.h>
using namespace std;
// 合并数组中连续的两个有序部分
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
int i = first, j = mid + 1;
int k = first;
while (i <= mid && j <= last) {
if (a[i] > a[j]) {
temp[k++] = a[j++];
} else {
temp[k++] = a[i++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= last) {
temp[k++] = a[j++];
}
}
// 根据设定的步长来顺序归并
void mergeStep(int a[], int step, int len, int temp[]) {
int first, mid, last;
first = 0;
last = first + step + step - 1;
mid = first + step - 1;
while (last < len) {
mergeArray(a, first, mid, last, temp);
first = last + 1;
last = first + step + step - 1;
mid = first + step - 1;
}
// 末端注意数组边界
if (mid > len) {
for (int i = first; i < len; i++) {
temp[i] = a[i];
}
} else {
mergeArray(a, first, mid, len - 1, temp);
}
}
void mergeSort(int a[], int len) {
cout << "Before sorting:" << endl;
for (int i = 0; i < len; i++) {
cout << a[i] << "\t";
}
cout << endl;
//
int flag = 0; // 写入方向标识
int* temp = (int*) malloc(len * sizeof(int));
// 消除递归
for (int step = 1; step < len; step = step << 1) {
// 避免返回回写
if (flag++ % 2) {
// flag初始为奇数，向a写入排序结果，执行后flag为偶数
mergeStep(temp, step, len, a);
} else {
// flag初始为偶数，向temp写入即可,执行后flag为奇数
mergeStep(a, step, len, temp);
}
}
// 若flag为奇数，则表明排序结果存在于temp中，需要回写
if (flag % 2) {
for (int i = 0; i < len; i++) {
a[i] = temp[i];
}
}
//
free(temp);
//
cout << "After merge sorting:" << endl;
for (int i = 0; i < len; i++) {
cout << a[i] << "\t";
}
cout << endl;
}
int main() {
int arr[17] = { 213, 67, 89, 10, 23, 9, 23, 45, 12, 456, 234, 67, 12, 0 };
int len = 17;
mergeSort(arr, len);
return 0;
}
补充：软件开发 , C++ ,
