归并排序
参考《数据结构与算法c++》书中的归并算法部分
已经测试可用，10万个常数排序，速度非常快。
#include<iostream>
#include<algorithm>
using namespace std;
void Merge(int *arr, int *temp_array, int left_begin, int right_begin, int right) {
//point是开始对temp_数组调整的下标
int point = left_begin;
//左数组结束下标
int left_end = right_begin - 1;
//两个数组的总个数
int num = right - left_begin + 1;
//两个数组同向右遍历，依次找最小值
while (left_begin <= left_end && right_begin <= right) {
//如果左边数组的当前值更小，当前值填入temp_rray中 对应位置中
if (arr < arr) {
temp_array = arr;
}//反之
else {
temp_array = arr;
}
}
//把左数组剩下的填入temp中
while (left_begin<=left_end)
{
temp_array = arr;
}//右数组剩下的
while (right_begin <= right)
{
temp_array = arr;
}//把temp数组中，本轮调整位置的几个数字填回到原数组arr中
//这里循环次数为 right-left+1 次
for (int i = 0; i < num; i++,right--) {
arr = temp_array;
}
}
void Msort(int *arr, int *temp_array, int left, int right) {
//当传入的数组个数大于1时
if (left < right){
//对半分割数组，如果传入5个值，left=0,right=4,center就是2 左边就是下标0~2，右边下标3~4
int center = (right + left) / 2;
//对左边数组继续分割
Msort(arr, temp_array, left, center);
//对右边数组继续分割
Msort(arr, temp_array,center+1,right);
//merge是合并，将两个左右数组按顺序合并传入，左边数组起点，右边数组起点，右边数组终点
Merge(arr, temp_array, left,center+1, right);
}
}
void MergeSort(int *arr, int N) {
//构造临时数组，用于调整数字位置
int* temp_array = new int;
for (int i = 0; i < N; i++) {
temp_array = 0;
}
Msort(arr, temp_array, 0, N - 1);
free(temp_array);
}
int main() {
int size;
//输入数组大小
cin >> size;
//动态分配数组
int* arr = new int;
for (int i = 0; i < size; i++) {
cin >> arr;
}
//主代码
MergeSort(arr, size);
//输出
for (int i = 0; i < size; i++) {
cout << arr << " ";
}
free(arr);
cout << endl;
}
页:
[1]