初夏小谈：排序算法---归并排序（非递归）
归并排序（MergeSort）一、归并排序是建立在分治法的基础上进行的排序。归并排序的思想是：先将一组数据进行分割成若干的小子序列，然后将这些子序列进行排序，之后再对这些子序列再进行排序。当将两个子序列合并成一个有序子序列，称之为二路归并。
在进行归并排序时需要进行三步：①：针对两个有序子序列的合并
②：针对一趟所有子序列的合并
③：循环使得子序列越来越少最终全部合并完毕
针对第一个步骤①：当所有子序列的元素个数都是1时，那么每个子序列都是有序的。因此第一次就是两个元素（也是两个子序列）进行合并。
针对第二个步骤②：就是把所有子序列进行两两合并（注意：第一次就是把所有的元素两两合并）
针对第三个步骤③：由于是二路归并所以每一趟合并的子序列就是上一次长度的二倍。所以此次循环O(logn)次
二、代码如下：
头文件：
#pragma once
#include<ctime>
#include<malloc.h>
#include<iostream>
using namespace std;
//将两个有序子序列合并
void merge(int arr[], int small, int mid, int big);
//进行一趟子序列的全排序
void OneMerge(int arr[], int length, int size);
//进行归并排序
void MergeSort(int arr[], int size);
//打印
void PrintMergeSort(int array[], int size);
函数体：
#include"MergeSort.h"
//将两个有序子序列合并
void merge(int arr[], int small, int mid, int big)
{
//创建一个临时数组来存储排序后的子序列
int* ptr = (int*)malloc(sizeof(int)*(big - small + 1));
int i = small;//0
int j = mid + 1;//2
int k = 0;
while (i <= mid && j <= big)
{
if (arr <= arr)
{
ptr = arr;
}
else
{
ptr = arr;
}
}
while (i <= mid)
{
ptr = arr;
}
while (j <= big)
{
ptr = arr;
}
for (i = small, k = 0; i <= big; k++, i++)
{
arr = ptr;
}
free(ptr);
ptr = nullptr;
}
//进行一趟子序列的全排序
void OneMerge(int arr[], int length, int size)
{
int i;
for (i = 0; i + 2 * length - 1 < size; i = i + 2 * length)
{
merge(arr, i, i + length - 1, i + 2 * length - 1);
}
if (i + length - 1 < size)
{
merge(arr, i, i + length - 1, size - 1);
}
}
//进行归并排序
void MergeSort(int arr[], int size)
{
for (int i = 1; i <= size; i *= 2)
{
OneMerge(arr, i, size);
}
}
//打印
void PrintMergeSort(int array[], int size)
{
int i = 0;
while (i < size)
{
cout << array << " ";
}
cout << endl;
}
主函数：
#include"MergeSort.h"
#define ARRA_YSIZE 100
int main()
{
srand((unsigned int)time(NULL));
int array;
for (int i = 0; i < ARRA_YSIZE; i++)
{
array = rand() % 100;
}
int size = sizeof(array) / sizeof(array);
cout << "未排序：";
PrintMergeSort(array, size);
MergeSort(array, size);
cout << "归并排序：";
PrintMergeSort(array, size);
system("pause");
return 0;
}
结果显示：
三、归并排序的特性：
①：归并排序的不足在于它需要借助O(N)的空间复杂度。归并排序可以解决当数据达到无法全部加载进内存的数据的排序。
②：时间复杂度O(nlogn)
③：空间复杂度O(n) --->需要借助空间来存放合并的子序列
④：归并排序是一种稳定的排序算法
珍&源码
https://blog.51cto.com/u_15091844/4850590
页:
[1]