王道数据结构 (22) 归并排序
2023-09-11 14:22:18 时间
示例:
合并方法:
示例代码:
#include <stdio.h>
#define LEN 8 // 合并
void merge(int a[], int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
int left[n1], right[n2];
int i, j, k;
for (i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i] = a[start + i];
for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j] = a[mid + 1 + j];
i = j = 0;
k = start;
while (i < n1 && j < n2)
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
while (i < n1) /* left[] is not exhausted */
a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
a[k++] = right[j++];
}
// merge_sort():先排序,再合并
void merge_sort(int a[], int start, int end)
{
int mid;
if (start < end)
{
mid = (start + end) / 2;
printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", start, mid, mid + 1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); // 分解 + 解决:Divide + Conquer
merge_sort(a, start, mid); // 递归划分原数组左半边array[start...mid]
merge_sort(a, mid + 1, end); // 递归划分array[mid+1...end] // 合并:Combine
merge(a, start, mid, end); // 合并
printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n", start, mid, mid + 1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
}
}
int main(void)
{
int a[LEN] = {5, 2, 4, 7, 1, 3, 2, 6};
merge_sort(a, 0, LEN - 1);
return 0;
}
运行:
完整代码 :
8 #include <stdio.h> 9 #define LEN 8 10 11 // 合并 12 void merge(int a[], int start, int mid, int end) 13 { 14 int n1 = mid - start + 1; 15 int n2 = end - mid; 16 int left[n1], right[n2]; 17 int i, j, k; 18 19 for (i = 0; i < n1; i++) /* left holds a[start..mid] */ 20 left[i] = a[start+i]; 21 for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */ 22 right[j] = a[mid+1+j]; 23 24 i = j = 0; 25 k = start; 26 while (i < n1 && j < n2) 27 if (left[i] < right[j]) 28 a[k++] = left[i++]; 29 else 30 a[k++] = right[j++]; 31 32 while (i < n1) /* left[] is not exhausted */ 33 a[k++] = left[i++]; 34 while (j < n2) /* right[] is not exhausted */ 35 a[k++] = right[j++]; 36 } 37 38 // merge_sort():先排序,再合并 39 void merge_sort(int a[], int start, int end) 40 { 41 int mid; 42 if (start < end) 43 { 44 mid = (start + end) / 2; 45 printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", 46 start, mid, mid+1, end, 47 a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); 48 49 // 分解 + 解决:Divide + Conquer 50 merge_sort(a, start, mid); // 递归划分原数组左半边array[start...mid] 51 merge_sort(a, mid+1, end); // 递归划分array[mid+1...end] 52 // 合并:Combine 53 merge(a, start, mid, end); // 合并 54 55 printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n", 56 start, mid, mid+1, end, 57 a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); 58 } 59 } 60 61 int main(void) 62 { 63 int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 }; 64 merge_sort(a, 0, LEN-1); 65 66 return 0; 67 }
代码仓库:
相关文章
- Java实现 LeetCode 451 根据字符出现频率排序
- Java实现 LeetCode 148 排序链表
- Java实现奇偶数排序
- Python实现的选择排序算法原理与用法实例分析
- java算法 -- 归并排序
- 数据结构和算法-排序算法-希尔排序
- LinkedList中将对象按照某一属性排序
- mysql 排序 oder by 和 使用hibernate 排序
- 【刷题】面筋-数据结构-排序算法的复杂度、稳定性、内部外部排序
- LeetCode(33):搜索旋转排序数组
- C/C++基础讲解(十三)之数据结构篇排序大比拼
- 一个包含嵌套递归数据结构的对象的排序实现
- 程序实现对数据排序并按出现次数进行排序 目录 1. 题目程序实现对数据排序并按出现次数进行排序1 2. 思路2 3. 效果2 4. 代码 /00listPrj/src/Sort.java2
- 【书上讲解】归并排序的非递归写法
- 华为OD机试 - 打印任务排序
- Android 面试算法题 删除排序数组中的重复项和旋转数组
- 野生前端的数据结构练习(9)冒泡排序,选择排序,插入排序
- 2475. 数组中不等三元组的数目-快速排序+遍历求和
- 一个数据表对象(NSManagedObject)加入排序
- 数据结构和算法设计专题之---八大内部排序
- 《数据结构与算法之美》——冒泡排序、插入排序、选择排序
- 一步一步写算法(之排序二叉树)
- JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序
- 数据结构期末考试题库——排序1
- DSA之十大排序算法第五种:Merge Sort