【算法导论】归并排序
2021-07-14 13:04
标签：合并 图片 规模 div color mat 代码实现 http signed 1. 分治法：分治模型在每层递归的时都有三个步骤： a.分解原问题为若干个子问题，这些子问题是原问题的规模较小的实例； b. 解决这些子问题，递归地求解各子问题的规模足够小，则直接求解； c. 合并这些子问题的解 成 原问题的解。 2. 归并排序算法完全遵循分治模式。 a. 分解：分解待排序的n个元素的序列成各具 n/2 个元素的子序列 b. 解决：使用归并排序递归地排序子序列 c. 合并：合并两个已经排序的子序列以产生已排序的答案。 3.归并排序算法图示，实话说我没看懂第一个图。。但是第二个图很好理解 4. 伪代码 5. 算法分析： 排序就是比较，比较最终都是两个数比较 直接看MERGE（A, p, q, r）这个算法,这个算法的前提就是假设 A[p] - A[q]是有序的， A[q+1]到A[r]是有序的，那么归并后肯定是有序的. 怎么做到这个前提，就是最终把所有的数分到最小粒度， 也就是数组只有一个数的时候，它一定是有序的， 然后一层一层向上归并，得到最终的有序序列 6. 代码实现 java python c语言 【算法导论】归并排序 标签：合并 图片 规模 div color mat 代码实现 http signed 原文地址：https://www.cnblogs.com/yeyeck/p/9538394.html
MERGE(A, p, q, r)
n1 = q-p+1
n2 = r-q
//let L[1....n1+1] and R[1....n2+1] be new arrays
for i =1 to n1
L[i] = A[p+i-1]
for j=1 to n2
R[j] = A[q+j]
L[n1+1] = ∞
L[n2+1] = ∞
i=1
j=1
for k =p to r
if L[i]R[j]
A[k] = L[i]
i = i + 1
else
A[k]=R[j]
j = j+1
MERGE-SORT(A,p,r)
if p r
q =(p+r)/2 //向下取整，不会打那个符号
MERGE-SORT(A, p, q)
MERGE-SORT(A, q+1, r)
MERGE(A, p, q, r)
void mergeSort(int[] A, int p, int r) {
if (p r) {
int q = (int)Math.floor((p + r)/2);
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
void merge(int[] A, int p, int q, int r){
int n1 = q - p + 1;
int n2 = r - q ;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];
for (int i = 0; i ) {
L[i] = A[p+i];
}
for (int j = 0; j ) {
R[j] = A[q+j+1];
}
L[n1] = R[n2] = Integer.MAX_VALUE;
int i = 0, j = 0;
for (int k = 0; k ) {
if (L[i] R[j]) {
A[p+k] = L[i];
i++;
} else {
A[p+k] = R[j];
j++;
}
}
}
import math
import sys
def merge_sort(arr, p, r):
if p r:
q = math.floor((p + r) / 2)
merge_sort(arr, p, q)
merge_sort(arr, q + 1, r)
merge(arr, p, q, r)
# 0, 5, 10
def merge(arr, p, q, r):
n1 = q - p + 1
n2 = r - q
m = []
n = []
for i in range(n1):
m.append(arr[p+i])
for j in range(n2):
n.append(arr[q+j+1])
m.append(sys.maxsize)
n.append(sys.maxsize)
i = j = 0
for k in range(r - p + 1):
if m[i] n[j]:
arr[p+k] = m[i]
i += 1
else:
arr[p+k] = n[j]
j += 1
// 0, 10
void merge_sort(int arr[], int p, int r)
{
if(r > p)
{
int q = (p + r) / 2;
merge_sort(arr, p, q);
merge_sort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
// 0, 5, 10
void merge(int arr[], int p, int q, int r)
{
int n1 = q - p +1;
int n2 = r - q;
int L[n1+1], R[n2+1];
int i, j, k;
for(i = 0; i )
L[i] = arr[p+i];
for(j = 0; j )
R[j] = arr[q+j+1];
L[n1] = R[n2] = (unsigned)(~0) >> 1;
i = j =0;
for(k = 0; k 1; k++)
{
if(L[i] R[j])
{
arr[p+k] = L[i];
i++;
}
else
{
arr[p+k] = R[j];
j++;
}
}
}