[算法与数据结构] - No.5 归并排序

本文主要是介绍[算法与数据结构] - No.5 归并排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：

假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到 n / 2（求天棚） 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，…，如此重复，最后得到一个长度为 n 的有序序列。

算法描述：

MergeSort.cpp

#include <iostream>using namespace std;
void MergeArr(int arr[],int startindex,int mid,int endindex,int temp[])
{int ptr1 = startindex;int ptr2 = mid+1;int ptr3 = 0;while(ptr1<=mid&&ptr2<=endindex){if(arr[ptr1]<arr[ptr2]){temp[ptr3++] = arr[ptr1++];}else{temp[ptr3++] = arr[ptr2++];}}while(ptr1<=mid){temp[ptr3++] = arr[ptr1++];}while(ptr2<=endindex){temp[ptr3++] = arr[ptr2++];}for(int i = 0 ; i<ptr3;i++){arr[i+startindex] = temp[i];}}
void MergeSort(int arr[],int startindex,int endindex,int temp[])
{if(startindex<endindex){int mid = (startindex + endindex)/2;MergeSort(arr,startindex,mid,temp);MergeSort(arr,mid+1,endindex,temp);MergeArr(arr,startindex,mid,endindex,temp);}
}
int main()
{int n;int arr[1000];int temp[1000];cin >> n;for(int i = 0 ; i < n ; i++){cin>>arr[i];}MergeSort(arr,0,n-1,temp);for(int i = 0 ; i<n; i++){cout<<arr[i]<<" ";}
}

P.S.文章不妥指出还望指正

这篇关于[算法与数据结构] - No.5 归并排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---