上次是快排和冒泡
今天为大家带来归并排序
1.基本思想
归并排序是一种分治算法，它将序列分成两个子序列，分别对子序列进行排序，然后将排序好的子序列合并起来。这个过程可以递归地进行，直到序列长度小于等于1时停止递归。
在合并子序列的过程中，需要比较两个子序列的元素，并按顺序将它们合并成一个有序序列
注意：归并排序的关键在于合并两个有序的子序列，这一步需要额外的空间来存储中间结果。在实际的实现中，可以使用递归或非递归的方式来完成归并排序
2.递归实现
递归归并排序:
- 如果序列长度小于等于1，无需排序，直接返回
- 将序列分成两个子序列，分别进行递归归并排序
- 合并两个已排序的子序列
void _MergeSort(int* a, int* tmp, int left, int right)//是下标，不是值 { if (left >= right)//只有一个元素或不存在这样的区间递归停止 { return; } int mid = (left + right) / 2;//分成两部分，分别有序后再进行归并 // [begin, mid][mid+1, end] _MergeSort(a, tmp, left, mid); _MergeSort(a, tmp, mid+1,right );//这两部分都有序啦 //开始归并：归并到到tmp数组的相同位置，再拷贝回去 int left1 = left; int right1 = mid;//第一个数组的两端 int left2 = mid+1; int right2 = right;//第二个数组的两端 int index = left;//两个数组是从left开始的，left给index就是到相同区间上 while (left1 <= right1 && left2 <= right2)//两个比，小的放进去 { if (a[left1] < a[left2]) { tmp[index] = a[left1]; index++; left1++; } else { tmp[index] = a[left2]; index++; left2++; } }//有一个排完了，剩下的一个就直接放 while (left1 <= right1) { tmp[index] = a[left1]; index++; left1++; } while (left2 <= right2) { tmp[index] = a[left2]; index++; left2++; }//到此，tmp内已经归并成功，接下来复制回a中 memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1)); } void MergeSort(int* a, int n) { //创建一个临时数组 int tmp = (int*)malloc(sizeof(int) * n); assert(tmp); _MergeSort(a, tmp, 0, n - 1);//子函数，在这里递归不好，有动态开辟 free(tmp); } int main() { int a[] = { 10,6,7,1,3,9,4,2 }; //MergeSortNonR(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int));//用来打印数组的 MergeSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); return 0; }
3.非递归实现
非递归实现归并排序是一种迭代式的排序算法，它避免了递归调用带来的额外开销，通常使用循环和迭代来实现归并排序的过程：
确定归并区间的思路：对于给定的数组，首先将相邻的元素两两归并（gap=1），然后将归并的区间长度不断扩大，依次归并相邻的区间、长度为 2 的区间、长度为 4 的区间，直到整个数组都归并完成（gap=2）。*
归并的逻辑：在每次归并的过程中，根据当前的区间长度，确定待归并的两个区间的边界。然后比较这两个区间的元素，并将较小的元素依次放入临时数组中。当某一个区间的元素已经全部放入临时数组后，将另一个区间剩余的元素直接放入临时数组中。
复制回原数组：在每次归并完成后，将临时数组中归并好的结果复制回原数组中，以便进行下一轮的归并操作。
不断扩大归并区间：通过不断扩大归并的区间长度，最终完成整个序列的排序
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); assert(tmp); int gap = 1;//第一次1为长度 while (gap < n) { for (int i = 0; i < n ; i += 2*gap)//每次两个区间的左起点都是i ,每次跳过两个gap { //一个区间里有gap个元素 int left1 = i; int right1 = i + gap - 1;//第一个区间 int left2 = i+gap; int right2 = i + 2*gap - 1;//第二个 if (left2 > n)//没有与之相归并的第二个数组 { break;//直接出去，进行下一层 } if (right2 > n) { right2 = n - 1; } //开始归并 int index = i; while (left1 <= right1 && left2 <= right2)//两个比，小的放进去 { if (a[left1] < a[left2]) { tmp[index] = a[left1]; index++; left1++; } else { tmp[index] = a[left2]; index++; left2++; } }//有一个排完了，剩下的一个就直接放 while (left1 <= right1) { tmp[index] = a[left1]; index++; left1++; } while (left2 <= right2) { tmp[index] = a[left2]; index++; left2++; }//到此，tmp内已经归并成功，接下来复制回a中 memcpy(a + i, tmp + i, sizeof(int) * (right2 - i + 1)); } gap *= 2; } }
