题目描述
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
归并排序的思路是依赖于分治的思想,
分治思想(以下并不太过严谨,实际的mergeSort中,是优先划分左区间)
其思想是从顶到底部, 将区间l, r分成多个子区间l , l + 1, l + 2, ... r - 1, r
然后在从底部到顶部,合并区间,(l, l + 1) (l + 2, l + 3)...(r - 1, r)
同上,一直合并成大的区间(1, r)
实现
1.先取中间位置mid, 将区间一分为二,即[l, mid] [mid+1, r],将这两个区间继续放入到mergeSort(),继续划分
2.当区间分完,两两进行合并(l, mid) + (mid + 1, r)
合并的思路
2.1 左右区间所有的数是排序完成, 利用双指针i, j滑动,比较左区间第i个值和右区间第j个值大小
2.2 较小的值放入到临时数组tmp中
2.3 将剩余没有遍历的元素放入到数组tmp中
2.4 最终排序完成
2.4 利用tmp更新原数组q的位置
举例
[l, mid] 1, 2, 4, 4 l = 0 mid = 3
[mid + 1, r] 2, 3, 4, 5, mid + 1 = 4 r = 7
i j
1. 1(1) < 2(4) tmp = [1]
2. 2(2) <= 2(4) tmp = [1, 2]
3. 4(3) > 2(4) tmp = [1, 2, 2]
4. 4(3) > 3(5) tmp = [1, 2, 2, 3]
5. 4(3) <= 4(6) tmp = [1, 2, 2, 3, 4]
6. 4(4) <= 4(6) tmp = [1, 2, 2, 3, 4, 4] 左区间遍历完成,很容易发现在右区间剩余元素4,5必然大于左区间最后一个元素
7.将剩余元素添加到tmp tmp = [1, 2, 2, 3, 4, 4, 4, 5]
8.更新tmp数组到原数组的[1, r]区间,这里也变相的说明了为什么左右区间一开始就是有序的
void merge_sort(int q[], int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
for(i = l, k = 0; i <= r; i ++, k ++) q[i] = tmp[k];
}
java 代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int n;
static int[] q = new int[N], tmp = new int[N];
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < n; i ++) q[i] = sc.nextInt();
mergeSort(q, 0, n - 1);
for(int i = 0; i < n; i ++) System.out.print(q[i] + " ");
}
private static void mergeSort(int[] q, int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
mergeSort(q, l, mid);
mergeSort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j++];
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
for(i = l, k = 0; i <= r; i ++, k ++) q[i] = tmp[k];
}
}
python 代码
q = [0] * 100010
tmp = [0] * 100010
def mergeSort(q, l, r):
if(l >= r): return
mid = l + r >> 1
mergeSort(q, l, mid)
mergeSort(q, mid + 1, r)
k = 0
i = l
j = mid + 1
while(i <= mid and j <= r):
if q[i] < q[j]:
tmp[k] = q[i]
k += 1
i += 1
else:
tmp[k] = q[j]
k += 1
j += 1
while(i <= mid):
tmp[k] = q[i]
k += 1
i += 1
while(j <= r):
tmp[k] = q[j]
k += 1
j += 1
k = 0
i = l
while(i <= r):
q[i] = tmp[k]
i += 1
k += 1
def main():
global q
n = int(input())
q = list(map(int, input().split()))
mergeSort(q, 0, n - 1)
print(' '.join(list(map(str, q))))
main()
c++ 代码
#include <iostream>
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
for(i = l, k = 0; i <= r; i ++, k ++) q[i] = tmp[k];
}
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]);
}