插入排序

插入排序的前提是未插入时该序列有序。

假如是从小到大排序，插入的数为key，从右向左找小于等于key的值，如果不满足那么原来的向后移动一位进行覆盖，直到满足或者找完进行插入。
重复上面的操作。

void InsertSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n-1; i++)
	{
		int end=i;
		int key = a[end + 1];
		while (end>=0)
		{
			if (a[end] <= key)
				break;
			else
				a[end + 1] = a[end];
			end--;
		}
		a[end + 1] = key;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度O(n*n)
该排序适合接近有序的情况下，在该种情况下时间复杂度接近O(n)

希尔排序

有插入排序演变过来
希尔排序有两个步骤：
1.预排序（尽可能变得有序）
2.插入排序

例：
预排序：把待排序的一组数分为gap组，每一组进行插入排序

把这10组数分成3组：
第1组：2，5，3，0
第2组：4，1，8
第3组：6，9，7

经过预排之后的顺序

最后全部的进行插入排序，就可以得到有序的序列。
上面例子的代码：

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int i = 0; i < n-gap; i++)
	{
		
		int end=i;
		int key = a[end + gap];
		while (end >= 0)
		{
			if (a[end] <= key)
				break;
			else
				a[end + gap] = a[end];
			end -= gap;
		}
		a[end + gap] = key;
	}
	InsertSort(a, n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

希尔排序动态图

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap>1)
	{
		gap = gap / 2;
		for (int i = 0; i < n-gap; i++)
		{
			int end = i;
			int key = a[end + gap];
			while (end >= 0)
			{
				if (a[end] <= key)
					break;
				else
					a[end + gap] = a[end];
				end -= gap;
			}
			a[end + gap] = key;
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

选择排序

选择排序很简单，每一次选出最小的反在前面，选出最大的放在后面。

void SelectSort(int* a, int n)
{
	int min, max;
	int begin = 0, end = n - 1;	
	while (begin < end)
	{
		min = max = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[min] > a[i])
				min = i;
			if (a[max] < a[i])
				max = i;
		}
		swap(&a[min], &a[begin]);
		//注意
		if (begin == max)
			max = min;
		swap(&a[max], &a[end]);
		begin++;
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度O(N)

堆排序

void AdjustDwon(int* a, int n, int root)
{
	int father = root;
	int child = 2 * father + 1;
	while (child <n)
	{
		if (child<n - 1 && a[child]<a[child + 1])
			child++;
		if (a[father] < a[child])
		{
			swap(&a[father], &a[child]);
			father = child;
			child = 2 * father + 1;
		}
		else
			return;
	}
}
void HeapSort(int* a, int n)
{
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}

	for (i = n - 1; i > 0; i--)
	{
		swap(&a[0], &a[i]);
		AdjustDwon(a, i-1, 0);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

冒泡排序

void BubbleSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	for (int i = begin; i < n-1; i++)
	{
		for (int j = begin; j < end; j++)
		{
			if (a[j+1] < a[j])
				swap(&a[j], &a[j+1]);
		}
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

快速排序

快速排序的基本思路就是：选出一个基值，一般是选取最左边的为基值，然后从右边开始进行遍历，假设是按从小到大的顺序，那么从右边找小的，找到小的之后，在从左边开始找最大的，找到之后两者进行交换。然后继续重复上面的过程，直到左边大于等于右边的时候停止，然后和基数进行交换。
这是一轮

int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[keyi] <= a[right])
			right--;
		while (left < right && a[left] <= a[keyi])
			left++;
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[right]);
	keyi = left;
	return keyi;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

坑位法：把基数作为坑位，从右边开始找小（比基数小）的，找到之后填入坑位，该位置变成坑位，然后从左边开始找大，然后再填入坑位，直到找完（左边大于等于右边），把基数填入坑位。

int PartSort2(int* a, int left, int right)
{
	int keyi= left;
	int temp = a[left];
	while (left < right)
	{
		while (left<right&&a[right] >= temp)
		{
			right--;
		}
		a[keyi] = a[right];
		keyi = right;
		while (left < right && a[left] <= temp)
		{
			left++;
		}
		a[keyi] = a[left];
		keyi = left;
	}
	a[keyi] = temp;
	return keyi;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

前后指针法：
前指针从基数前一个位置开始，后指针从基数位置开始。前指针找小，当找到小的时候，后指针加一，然后前后指针指向的数值进行交换，然后前指针继续找小，直到查找完。

int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int front = keyi + 1;
	int back = keyi;
	while (front <= right)
	{
		if (a[front] <= a[keyi])
		{
			back++;
			swap(&a[front], &a[back]);
		}
		front++;
	}
	swap(&a[back], &a[keyi]);
	keyi = back;
	return keyi;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上面描述的是一轮排序，每一轮排好之后，都可以确定好排好序之后基数的位置，基数左边是比它小的，右边是比它大的，左边继续排序，右边在继续排序。当还剩一个需要排序的时候就停止排序了。

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = left;
	//keyi = PartSort1(a, left, right);
	//keyi = PartSort2(a, left, right);
	keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

1
2
3
4
5
6
7
8
9
10
11
12

上面这种排序还不可以，因为他的最坏的时间复杂度为O(N*N)，我们取的基数最好是该组有序数的中间值，但是这个值也不容易在无序中找到，此时我们用3数取中法，把最边的值，最右边的值，还有中间的值，3者进行比较，次大的为基数。为了保证还是上面的方法，我们把基数和最左边的数进行交换。

int ThreeIn(int* a, int left, int right)
{
	int middle = left + (right - left) / 2;
	if (a[middle] < a[left])
	{
		if (a[left] < a[right])
			return left;
		else if (a[middle] < a[right])
			return right;
		else
			return middle;
	}
	else
	{
		if (a[middle] < a[right])
			return middle;
		else if (a[left] < a[right])
			return right;
		else
			return left;
	}
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = left;
	int x = ThreeIn(a, left, right);
	swap(&a[keyi], &a[x]);
	//keyi = PartSort1(a, left, right);
	//keyi = PartSort2(a, left, right);
	keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度O(N*logN)

以最左边为基数，为什么从先右边开始呢？

在L与R交换的过程中没有什么可以讨论的，最主要的是相遇的时候和基数进行交换的情况：
1.R遇见L，此时L为最小的或者是基数，交换之后，左小右大。
2.L遇见R:
(1)L与R没有交换
R所处的位置为小，R右边都是大，左边都是小，可以与基值进行交换。
(2)L与R交换
交换过后R还是会继续移动到小的地方，然后和(1)一样。

我们再讨论选左边为基值，还是讨论相遇的情况
1.L遇见R
(1)没有发生交换就相遇了，无法判断相遇时与基值的大小。
(2)L与R交换过后再相遇，此时相遇的为大，不能和基值进行交换。
2.R遇见L
R遇见L说明R与L交换过，此时基值是小的，可以交换。
综上所述:从左边开始并不能完全保证相遇的地方为小的。
非递归形式的快速排序
1.用栈进行实现
用栈储存一组数的上下界，如果从左开始选基数的话，根据栈的特性，我们先储存左边界，再储存右边界。每次排序都从栈中拿出2个数据。当向栈中储存边界的时候要主要边界直接有没有元素。

void QuickSortNonR1(int* a, int left, int right)
{

	Stack p;
	InitStack(&p);
	StackPush(&p, left);
	StackPush(&p, right);
	while (!StackEmpty(&p))
	{
		right = StackTop(&p);
		StackPop(&p);
		left = StackTop(&p);
		StackPop(&p);
		int keyi = PartSort3(a, left, right);
		if (keyi + 1 < right)
		{
			StackPush(&p, keyi+1);
			StackPush(&p, right);
		}
		if (keyi - 1 > left)
		{
			StackPush(&p, left);
			StackPush(&p, keyi-1);
		}
	}
	StackDestroy(&p);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.用队列实现
根据队列的性质，先储存右边界，再储存左边界。后面的过程和栈类似

void QuickSortNonR2(int* a, int left, int right)
{
	Queue p;
	QueueInit(&p);
	QueuePush(&p, right);
	QueuePush(&p, left);
	while (!QueueEmpty(&p))
	{
		right = QueueFront(&p);
		QueuePop(&p);
		left= QueueFront(&p);
		QueuePop(&p);
		int keyi = PartSort3(a, left, right);
		
		if (keyi - 1 > left)
		{
			
			QueuePush(&p, keyi - 1);
			QueuePush(&p, left);
		}
		if (keyi + 1 < right)
		{
			
			QueuePush(&p, right);
			QueuePush(&p, keyi + 1);
		}
	}
	QueueDestroy(&p);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

归并排序