当前位置：首页 > news >正文

排序算法--归并排序

news 2025/8/1 1:32:37

实现逻辑
① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
③ 重复步骤②，直到所有元素排序完毕

void print_array(int a[], int n){for (int i = 0; i < n; ++i){cout << a[i] << " ";}cout << endl;
}/************************************************************************
* 功能描述:二路归并排序(两个有序序列)
* 参	数:有序序列下标 f 第一个， s 第二个
* 日	期:2023/11/22                                                   
************************************************************************/
void merge(int arr[], int fBegin, int fEnd, int sBegin, int sEnd, int newArray[])
{int index = fBegin;//新数组的下标int f = fBegin;//遍历第一个有序序列int s = sBegin;//遍历第二个有序序列while (f <= fEnd && s <= sEnd){if (arr[f] <= arr[s]){newArray[index++] = arr[f++];}else{newArray[index++] = arr[s++];}}while (f <= fEnd){newArray[index++] = arr[f++];}while (s <= sEnd){newArray[index++] = arr[s++];}memcpy(arr + fBegin, newArray + fBegin, sizeof(int) *(sEnd - fBegin +1));
}//多路归并排序
void mergeSort(int arr[], int left, int right, int newArray[])
{if (left >= right){return;}int mid = (left + right) / 2;mergeSort(arr, left, mid, newArray);mergeSort(arr, mid + 1, right, newArray);merge(arr, left, mid, mid + 1, right, newArray);
}int main(){int arr[] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3};int len = sizeof(arr)/sizeof(arr[0]);int newArray[10] = {0};cout << "排序前：";print_array(arr, len);mergeSort(arr, 0, len - 1, newArray);cout << "排序后：";print_array(arr, len);return 0;
}