文章目录
合并排序(归并排序)
C++python 合并排序(归并排序) C++
#include #define N 10using 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;}
python
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] = Bdef 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)