本文主要是介绍[算法与数据结构] - 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 归并排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!