当前位置：网站首页>排序——归并排序

排序——归并排序

2022-06-11 07:37:00 【AcTarjan】

归并排序

算法设计

将大的问题分解成多个子问题进行求解，子问题还可以继续分解，直到问题规模可以直接求解。
将序列分成两个子序列，使子序列有序，然后将两个有序的子序列合并成有序序列

C语言实现

void mergeSort(int* arr,int start,int end) {
    
    int len = end - start;
    if (len <= 1) {
    
        return;
    }
    int mid = (start+end)/2;
    mergeSort(arr,start,mid);
    mergeSort(arr,mid,end);
    int* temp = (int*)malloc(len * sizeof(int));
    int l=start,r=mid,index=0;
    while (l< mid && r < end) {
    
        if (arr[l] <= arr[r]) {
    
            temp[index] = arr[l];
            l++;index++;
        } else {
    
            temp[index] = arr[r];
            r++;index++;
        }
    }
    while (l < mid) {
    
        temp[index] = arr[l];
        l++;index++;
    }
    while (r < end) {
    
        temp[index] = arr[r];
        r++;index++;
    }
    for (l = start,index = 0; l < end; l++,index++) {
    
        arr[l] = temp[index];
    }
    free(temp);
}