[数据结构与算法]算法学习笔记DAY1（插入排序&归并排序）

1. 插入排序

?空间复杂度：O(1)

时间复杂度：

Best case:have sorted?=> O(n)

Worset case:reverse sorted => O(n^2)

Average case:O(n^2)

#include <iostream>
using namespace std;
void insertionsort(int a[], int n)
{
	int i, j;
	for (i = 2; i <= n; i++)
	{
		if (a[i] < a[i - 1])
		{
			a[0] = a[i];
			for (j = i - 1; a[j] > a[0]; --j)
			{
				a[j + 1] = a[j];
			}
			a[j + 1] = a[0];
		}
	}
}

int main()
{
	int i, a[100], n;
	scanf_s("%d", &n);
	for (i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	insertionsort(&a[0], n);
	for (i = 1; i <= n; i++)
	{
		cout << a[i];
	}
	return 0;
}

该算法为带哨兵版本，即空出数组a[0]位作为哨兵存储key值，
从而避免每次内循环需判断j>=0的问题
(该版本提升不明显,没必要使用)

出现的错误：调用函数时写成&a[0]。应注意&a[0]与&a[100]的区别

????????2.归并排序

核心操作：把数组内两个有序数列归并为一个（也可能为两个独立数字归并）

例：A[low ... mid] 与 A[mid + 1... high] 归并

/****
把多个已经有序的数列合并成一个
核心：二路归并
****/

#include <iostream>
using namespace std;
int n;
void Merge(int A[], int low, int mid, int high)
{
	int i, j, k;
	int *B = new(int [n]);            //辅助数组
	for (k = low; k <= high; k++)
	{
		B[k] = A[k];                  //将A复制到B
	}
	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)  //归并
	{
		if (B[i] <= B[j])
			A[k] = B[i++];
		else
			A[k] = B[j++];
	}
	while (i <= mid) A[k++] = B[i++];
	while (j <= high) A[k++] = B[j++];  //仅剩一个数列时，直接复制下来
	delete[] B;
}

void Mergesort(int A[], int low, int high)
{
	if (low < high)
	{
	int mid = (low + high) / 2;
	Mergesort(A, low, mid);
	Mergesort(A, mid + 1, high);
	Merge(A, low, mid, high);
	}
}
//Mergesort可对一个无序数列进行归并排序，利用递归拆分为两两归并

int main()
{
	int A[100], i, low = 0, mid = 2, high = 5;
	cin >> n;
	for (i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	Mergesort(&A[0], low, high);
	for (i = 0; i < n; i++)
	{
		cout << A[i] << endl;
	}
	return 0;
}