归并排序的相关代码

主要思想：

1.确定分界点 mid=(l+r)/2

2.递归排序 左边和右边

3.归并 把两个有序的数组合并成一个“合二而一”

确定分界点 :mid=(l+r)/2  从整个数组的最中间分开
递归排序  先左后右
归并 合二为一  (难点）  此时需要引入辅助数组即temp[ ];
归并排序是稳定的

如何判断一个排序算法是否稳定：

如果原序列里面有两个数相同，排完序后，如果两个数的相对位置不发生变化，就说明这个排序算法是稳定的。

主要思想：分治

方法：双指针；i从left起始，j从mid起始。

比较q[ i ],q[ j ],较小的那个插入到temp[ ]里，然后向后走，直到左半边或者右半边排序完，然后将没遍历到的那部分剩余的元素，依次插入到temp[ ]数组中。

每一轮结束后，将q[ ]里的元素按相应的顺序排好（即将q[ ]里的元素与辅助数组（temp[ ]）里的元素一一对应。）

代码如下：

#include
using namespace std;
#include
const int N = 100010;
int n;
int q[N];
int temp[N];//辅助数组
 
void merge_sort(int q[], int left, int right)
{
	if (left >= right)
		return;
	int mid = left + right >> 1;//除以2
	merge_sort(q, left, mid);
	merge_sort(q, mid + 1, right);
	int k = 0, i = left, j = mid + 1;
	while (i <= mid && j <= right)
	{
		if (q[i] <= q[j])
			temp[k++] = q[i++];
		else
			temp[k++] = q[j++];
	}
	while (i <= mid) temp[k++] = q[i++];
	while (j <= right)temp[k++] = q[j++];
 
	for (i = left, j = 0; i <= right; i++, j++)
	{
		q[i] = temp[j];
	}
 
 
}
int main()
{
 
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> q[i];
	}
	merge_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)
		cout < 

个人总结：
 
第一遍的时候，“合二为一”归并的时候，想当然的写成了 int i=0，这是不对的。
 
此时 i 是从传入的数组的最左边起，但数组的最左边不一定是 0 。
 
当递归右边时，数组的最左边是 mid+1 。