数据结构初阶：排序

void InsertSort(int* a, int n)
{
	//单趟  升序
	//[0,end] end+1
	int end;
	int tmp = a[end + 1];
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + 1] = a[end];
			--end;
		}
		else
		{
			break;
		}
	}
	a[end + 1] = tmp;
}

最终代码：

// 时间复杂度：O(N^2) 逆序
// 最好的情况：O(N)  顺序有序
void InsertSort(int* a, int n)
{
	//多趟 升序
	//[0,end] end+1
	for (int i = 0; i < n - 1; i++)
	{
		int end=i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

希尔排序( 缩小增量排序 )

步骤：

1.预排序（接近有序）

2.直接插入排序

void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		//gap = gap / 2;

		gap = gap / 3 + 1;

		for (int j = 0; j < gap; j++)
		{
			for (int i = 0; i < n - gap; i+=gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}
}

版本二：预排序（多组并排），最后直接插入排序

// （平均）时间复杂度：O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1时是预排序，目的让他接近有序
    // gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		//保证最后一次gap=1
		//gap = gap / 2;  //方法一
		gap = gap / 3 + 1;//方法二

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

《数据结构 (C 语言版 ) 》 --- 严蔚敏

《数据结构 - 用面相对象方法与 C++ 描述》 --- 殷人昆

交换排序

冒泡排序

单趟分析：

void BubbleSort(int* a, int n)
{
	//单趟 升序
	for (int i = 1; i < n; i++)
	{
		if (a[i-1] > a[i])
		{
			Swap(&a[i-1], &a[i]);
		}
	}

	//for (int i = 0; i < n-1; i++)
	//{
	//	if (a[i] > a[i + 1])
	//	{
	//		Swap(&a[i], &a[i + 1]);
	//	}
	//}
}

完整（多趟）代码：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

// 时间复杂度：O(N^2)
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
			}
		}
	}
}

//void BubbleSort(int* a, int n)
//{
//	for (int j = 0; j < n; j++)
//	{
//		for (int i = 0; i < n -1-j; i++)
//		{
//			if (a[i] > a[i+1])
//			{
//				Swap(&a[i], &a[i+1]);
//			}
//		}
//	}
//}

优化版本：若数组已经有序，则遍历一次后退出，即最好情况：O(N)

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
				exchange = true;
			}
		}
		if (exchange == false)
			break;
	}
}