归并排序

 参考链接

排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili

#include <stdio.h>
#include <stdlib.h>// 合并
void merge(int arr[], int tempArr[], int left, int mid, int right)
{// 标记左半区第一个未排序的元素int l_pos = left;// 标记右半区第一个未排序的元素int r_pos = mid + 1;// 临时数组元素的下标int pos = left;// 合并while (l_pos <= mid && r_pos <= right){if (arr[l_pos] < arr[r_pos])  // 左半区第一个剩余元素更小tempArr[pos++] = arr[l_pos++];else  // 右半区第一个剩余元素更小tempArr[pos++] = arr[r_pos++];}// 合并左半区剩余的元素while (l_pos <= mid)tempArr[pos++] = arr[l_pos++];// 合并右半区剩余的元素while (r_pos <= right)tempArr[pos++] = arr[r_pos++];// 把临时数组中合并后的元素复制回原来的数组while (left <= right){arr[left] = tempArr[left];left++;}
}// 归并排序
void msort(int arr[], int tempArr[], int left, int right)
{// 如果只有一个元素，那么不需要继续划分// 只有一个元素的区域，本生就是有序的，只需要被归并即可if (left < right){// 找中间点int mid = (left + right) / 2;// 递归划分左半区msort(arr, tempArr, left, mid);// 递归划分右半区msort(arr, tempArr, mid + 1, right);// 合并已经排序的部分merge(arr, tempArr, left, mid, right);}
}// 归并排序入口
void merge_sort(int arr[], int n)
{// 分配一个辅助数组int tempArr[n];// 调用实际的归并排序msort(arr, tempArr, 0, n - 1);
}void print_arr(int *arr,int n)
{for(int i = 0 ; i < n ; i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int arr[] = {9,5,2,7,12,4,3,1,11};int n = 9;print_arr(arr,n);merge_sort(arr,n);print_arr(arr,n);return 0;
}