首页 > 代码库 > 归并排序
归并排序
先说一下，这个归并排序是我自己的一些想法。简单地浏览了一下书本（《算法：C语言实现》（第三版）），实现方法并不一致。
但是这个算法我测试了一下，还行。
归并排序：分治法的思路。把一个待排序的数组（arr）分成两半（arrA和arrB）进行归并排序。在归并排序的过程中，arrA再分成两半……这个过程直到子数组无可再分。然后就回溯（应该是这么用这个名词），分别这些一对一对的细小的子数组进行插入排序……当这个过程回溯到arr的时候，由于arrA和arrB都已经是有序的子数组了，对arr的插入排序的工作量就相当小了。
1 void 2 InsertSort(int arr[], int left, int right) 3 { 4 for (int i = left+1; i <= right; i++) { 5 int tmp = arr[i]; 6 for (int j = i-1; j >= 0 && arr[j] > tmp; j--) { 7 arr[j+1] = arr[j]; 8 arr[j] = tmp; 9 }10 }11 }12 13 void14 MergeSort(int arr[], int left, int right)15 {16 if (left == right) {17 return;18 }19 20 int middle = (left + right) / 2;21 22 MergeSort(arr, left, middle);23 MergeSort(arr, middle+1, right);24 25 InsertSort(arr, left, right);26 }
归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。