【排序算法 C++和Python实现】合并排序(归并排序)

合并排序(归并排序)

C++python

#include 
#define N 10
using namespace std;

void merge(int A[], int low, int mid, int high)
{
	// 申请一个辅助数组
	int* B = new int[high - low + 1];
	int i = low, j = mid + 1, k = 0;
	// 按从小到大存放到辅助数组B[]中
	while (i <= mid && j<=high)
	{
		if (A[i] <= A[j]) B[k++] = A[i++];
		else B[k++] = A[j++];
	}
	// 如果子序列还有剩余，将剩余的移到B[]
	while (i <= mid) B[k++] = A[i++];
	while (j <= high) B[k++] = A[j++];
	// 将合并后的序列复制到A[]
	for (i = low, k = 0; i <= high; i++)
		A[i] = B[k++];

	//删除辅助数组
	delete []B;
}
void mergeSort(int A[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;
		// 对A[low:mid]中的元素进行合并排序
		mergeSort(A, low, mid);
		// 对A[mid+1:high]中的元素进行合并排序
		mergeSort(A, mid + 1, high);
		// 合并
		merge(A, low, mid, high);

	}
}
int main()
{
	int numbers[N] = { 3,2,1,5,6,2,8,6,9,7 };
	mergeSort(numbers, 0,N-1);
	for (int i = 0; i < N; i++)
		cout << numbers[i] << " ";
	cout << "n";
	return 0;
}

def merge(A, low_index, mid, high_index):
    B = []
    i = low_index
    j = mid + 1
    while (i <= mid) and (j <= high_index):
        if A[i] <= A[j]:
            B.append(A[i])
            i += 1
        else:
            B.append(A[j])
            j += 1

    while i <= mid:
        B.append(A[i])
        i += 1
    while j <= high_index:
        B.append(A[j])
        j += 1
    A[low_index:high_index+1] = B


def merge_sort(A:List[int], low_index, high_index):
    if low_index < high_index:
        mid = int((low_index + high_index) / 2)
        merge_sort(A, low_index, mid)
        merge_sort(A, mid + 1, high_index)
        merge(A, low_index, mid, high_index)


if __name__ == '__main__':
    r = [3, 2, 1, 5, 6, 2, 8, 6, 9, 7]
    merge_sort(r, 0, 9)
    print(r)