查找与排序-归并排序
排序算法可以分为内部排序和外部排序，
内部排序是数据记录在内存中进行排序，
外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。代价是需要额外的内存空间。若将两个有序表合并成一个有序表，称为2-路归并。 该算法时间复杂度为O(n log n)。
算法的原理如下：
- 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
- 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
假设我们有一个初始数列为{8, 4, 5, 7, 1, 3, 6, 2}，整个归并排序的过程如下图所示。
算法性能
速度仅次于快速排序。
时间复杂度
O(nlogn)。
空间复杂度
O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序。
稳定性
稳定。
// 归并排序
void MergeSort(int arr[], int start, int end, int * temp) // start和end分别是左边界和右边界
{
if (start >= end)
return;
int mid = (start + end) / 2;
MergeSort(arr, start, mid, temp);
MergeSort(arr, mid + 1, end, temp);
// 合并两个有序序列
int length = 0; // 表示辅助空间有多少个元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end)
{
if (arr[i_start] < arr[j_start])
{
temp[length] = arr[i_start];
length++;
i_start++;
}
else
{
temp[length] = arr[j_start];
length++;
j_start++;
}
}
while (i_start <= i_end) // 把剩下数的合并
{
temp[length] = arr[i_start];
i_start++;
length++;
}
while (j_start <= j_end)
{
temp[length] = arr[j_start];
length++;
j_start++;
}
// 把辅助空间的数据放到原空间
for (int i = 0; i < length; i++)
{
arr[start + i] = temp[i];
}
}
原文地址：https://blog.csdn.net/wlq_567/article/details/142686607
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！