归并排序 c++ and python
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5 + 5; int a[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) tmp[k ++] = q[i] <= q[j] ? q[i ++] : q[j ++]; while(i <= mid) tmp[k ++] = q[i ++]; while(j <= R) tmp[k ++] = q[j ++]; for(int i = L, j = 0; i <= R; ++ i, ++ j) q[i] = tmp[j]; return ; } int main() { int n; scanf("%d", &n); for(int i = 0; i < n; ++ i) scanf("%d", &a[i]); merge_sort(a, 0, n - 1); for(int i = 0; i < n; ++ i) printf("%d ", a[i]); return 0; }
def merge_sort(q, L, R): if L >= R: return mid = L + R >> 1 merge_sort(q, L, mid) merge_sort(q, mid + 1, R) i = L j = mid + 1 tmp = [] while i <= mid and j <= R: if q[i] < q[j]: tmp.append(q[i]) i += 1 else: tmp.append(q[j]) j += 1 while i <= mid: tmp.append(q[i]) i += 1 while j <= R: tmp.append(q[j]) j += 1 k = 0 for i in range(L, R + 1): q[i] = tmp[k] k += 1 return n = int(input()) a = list(map(int, input().split())) merge_sort(a, 0, n - 1) for i in range(n): print(a[i], end=" ")
测试通过题目https://www.acwing.com/problem/content/description/789/
相关推荐
nongfusanquan0 2020-08-18
Broadview 2020-07-19
数据与算法之美 2020-07-05
Masimaro 2020-06-21
wonner 2020-06-17
Oudasheng 2020-06-04
从零开始 2020-06-05
清溪算法君老号 2020-06-01
风吹夏天 2020-05-26
yangjingdong00 2020-05-11
Tips 2020-04-30
troysps 2020-04-26
ustbfym 2020-04-25
清溪算法君老号 2020-04-24
dushine00 2020-04-19
数据与算法之美 2020-04-18
wulaxiaohei 2020-04-17
nurvnurv 2020-04-16