- 论坛徽章:
- 0
|
归并排序主要分两步:
一是将序列分成两份子序列,然后每个子序列再分成两份,如此下去,直到每个序列里面只有一个元素,那么可以认为序列有序了。这个由一个递归功能的mergesort函数实现。
二是完成两个有序子序列合并,在merge函数里面实现。
将两个部分组合起来,就实现了归并排序,mergesort函数实现。
代码如下:- #include <stdio.h>
- void print_arr(int *arr, int arr_len);
- void merge(int *arr, int left, int midle, int right);
- void mergesort(int *arr, int left, int right);
- int
- main()
- {
- int arr[] = {78, 56, 13, 67, 35, 87, 92, 48, 52, 18};
- int arr_len = sizeof(arr) / sizeof(arr[0]);
- print_arr(arr, arr_len);
- mergesort(arr, 0, arr_len - 1);
- print_arr(arr, arr_len);
- return 0;
- }
- void
- merge(int *arr, int left, int midle, int right)
- {
- int arr_tmp[right - left + 1];
- int k = 0;
- int i = left;
- int j = midle + 1;
- while (i <= midle && j <= right) {
- if (arr[i] <= arr[j]) {
- arr_tmp[k] = arr[i];
- i++;
- k++;
- } else {
- arr_tmp[k] = arr[j];
- j++;
- k++;
- }
- }
- while (i <= midle) {
- arr_tmp[k] = arr[i];
- i++;
- k++;
- }
- while (j <= right) {
- arr_tmp[k] = arr[j];
- j++;
- k++;
- }
-
- int index = 0;
- while (index < k) {
- arr[left + index] = arr_tmp[index];
- index++;
- }
- }
- void
- mergesort(int *arr, int left, int right)
- {
- int midle;
- if (left < right) {
- midle = (left + right) / 2;
- mergesort(arr, left, midle);
- mergesort(arr, midle + 1, right);
- merge(arr, left, midle, right);
- }
- }
- void
- print_arr(int *arr, int arr_len)
- {
- int i = 0;
- while (i < arr_len) {
- printf("%d ", arr[i]);
- i++;
- }
- printf("\n");
- }
复制代码 |
|