题目描述
排序.
归并排序
算法思路
分治法思路.归并排序分为三步:
1.确定分界点:以数组下标中点作为分界点.
2.递归:对左半边和右半边数组做归并排序.
3.合并:将左右半边数组合并.
其中3.是最重要的一步.如何归并?用到双指针思想.
因为递归之后保证左半边L和右半边R数组均有序,每次取L和R的当前第一个数也就是L和R的当前最小值做比较,
每次取更小的放入临时数组中.
归并排序先递归再对区间操作, 其思路与快排相反.因为归并排序是由局部有序到全局有序, 而快排是
全局基本有序到局部排序.
当L[i]==R[j]时,选哪个放入都可,如果选的是L[i]那么排序是稳定的.稳定:如果a[i]==a[j]且i<j,排序后
若对于a[i']和a[j'],i'<j',那么该排序算法是稳定的.(无甚卵用.)快排是不稳定的,我们可以把下标加上去作为
第二关键字排序,那么快排也可以是稳定的.
合并
双指针算法. L, R有序, 指针保证每次指向都是区间剩余元素中的最小值.
时间复杂度
每次划分都要对所有数归并$O(n)$,划分$O(logn次)$,时间复杂度为$O(nlogn)$
C++ 代码
#include<cstdio>
const int Max_N = 1e5 + 10;
int n;
int q[Max_N], temp[Max_N];//待排数组和临时数组
void merge_sort(int q[], int l, int r )
{
if( l<r )//数组个数>1 若==1则已经有序
{
int mid = l + r >> 1; //1.确定分界点
merge_sort(q,l,mid), merge_sort(q,mid+1,r); //2.递归处理
//3.归并
int k = 0, i = l, j = mid + 1;
while( i<=mid && j<=r )
{
if( q[i]<=q[j] )
{
temp[k++] = q[i++];
}
else
{
temp[k++] = q[j++];
}
}
while( i<=mid ) temp[k++] = q[i++];
while( j<=r ) temp[k++] = q[j++];
//将数字放回q[]
for( int i = l; i<=r; i++ )
{
q[i] = temp[i-l];
}
}
}
int main()
{
scanf("%d",&n);
for( int i = 0; i<n; i++ ) scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for( int i = 0; i<n; i++ )
printf("%d ",q[i]);
puts("");
return 0;
}