数据结构：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序(C实现)

个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》

---

前言

排序：使一串数据，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

---

一、插入排序

插入排序的思路：把待排序数组，逐个插入到已经排好序的有序数组中，直到所有待排序数组插入完成，的到一个新的有序数组。

1.直接插入排序

假如要排序为升序数组。
遍历待排序数组，将待排序数组元素与已排序数组元素比较，如果已排序数组元素大于待排序数组元素，已排序数组元素后移，待排序数组再次于前一个已排序数组比较，直到遍历完已排序数组或待排序数组元素大于已排序数组元素。

// 插入排序
//遍历待排序数组，每次选择数组元素 与 已排序数组元素比较，如果该数组元素小于已排序数组元素，已排序元素后移
//直到该数组元素遍历到首或大于已排序数组元素，插入该位置。
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int j = i;
		int tmp = a[i + 1];
		while (j >= 0)
		{
			if (tmp < a[j])
			{
				a[j + 1] = a[j];
			}
			else
			{
				break;
			}

			j--;
		}

		a[j + 1] = tmp;
	}
}
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

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳定

2.希尔排序

我们要知道 待排序数组越接近有序，直接插入排序算法的时间效率越高。
那么我们如果使一个待排序数组快速变成接近有序的数组，再对接近有序的数组进行一次直接插入排序，就是希尔排序。

• 那对于希尔排序的一个问题，如何使待排序数组快速变成接近有序数组？

这就要使用gap(增益变量)，对待排序数组每隔gap的元素进行直接插入排序，再对待排序数组每隔(gap/2)的元素进行直接插入排序，再对待排序数组每隔(gap/2)的元素进行直接插入排序…
直到gap为1时，待排序数组已经接近有序数组。在对待排序数组直接插入排序即可。

如下：对数组{9,1,2,5,7,4,8,6,3,5}进行希尔排序

// 希尔排序
//1、使待排序数组变成接近有序的数组   2、对接近有序的数组直接插入排序  O(n)
//使用gap(增益变量)来使待排序数组快速变成接近有序的数组
void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		gap = gap / 3 + 1; // + 1 保证最后一次排序一定是插入排序 or gap /= 2
		for (int i = 0; i < n - gap; i++)
		{
			int j = i;
			int tmp = a[j + gap];
			while (j >= 0)
			{
				if (a[j] > tmp)
				{
					a[j + gap] = a[j];
				}
				else
				{
					break;
				}

				j -= gap;
			}

			a[j + gap] = tmp;
		}
	}
}
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

• 时间复杂度：O(N^1.3)
• 空间复杂度：O(1)
• 稳定性：不稳定

二、选择排序

选择排序的思想：每次从待排序数组中选择出最大or最小的元素，放入已排序数组后，直到待排序数组中没有元素时，数组完成排序。

1. 选择排序

每次从待排序数组中选择最小的元素，与已排序数组的后一个元素交换，直到待排序数组中没有元素结束。

// 选择排序
//遍历待排序数组，每次选择最小的待排序数组元素，与待排序数组首元素交换。
void SelectSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int minIndex = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[minIndex] > a[j])
			{
				minIndex = j;
			}
		}
		swap(&a[minIndex], &a[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳定

2.堆排序

堆排序详解
堆排序就是将待排序数组，构建为大堆(升序)or小堆(降序)，然后将堆顶元素与待排序数组最后元素交换，删除堆最后的数据，再次选择新的堆顶元素。重复上述操作即可。

如下： 对数组 {16, 72, 31, 94, 53, 23}降序

// 堆排序
//升序建大堆
void AdjustDwon(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (parent < n)
	{
		//选择左右孩子较大值
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}

		if (child < n && a[parent] < a[child])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}
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
37
38
39
40
41
42

• 时间复杂度：O(N*logN)
• 空间复杂度：O(1)
• 稳定性：不稳定

三、交换排序

交换排序思想：根据待排序数组中两个元素的比较结果交换两个元素在待排序数组中的位置。

1.冒泡排序

从待排序数组中每次比较相邻的两个元素，如果前一个元素大于后一个元素，交换两个元素。如果前一个元素小于等于后一个元素，不变。继续向后比较相邻的两个元素。

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

// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 1;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				flag = 0;
				swap(&a[j], &a[j + 1]);
			}
		}
		//如果flag == 1表示这趟比较，并未交换元素，表示数组已经有序
		if (flag == 1)
		{
			break;
		}
	}
}
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

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳定

2.快速排序(递归)

快速排序(递归)思路：任取待排序数组中的某个元素为基准值，以该基准值为标准，将待排序数组分成左右两个子序列，左子序列都小于基准值，右子序列都大于该基准值，然后左右子序列重复该操作，直到左右子序列只有一个元素or没有元素结束，此时数组有序。

//类似于二叉树的先序遍历
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int pivot = PartSort3(a, left, right);
	//int pivot = PartSort2(a, left, right);
	//int pivot = PartSort1(a, left, right);
	//区间[left, pivot - 1]  pivot  [pivot + 1, right]

	QuickSort(a, left, pivot - 1);
	QuickSort(a, pivot + 1, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

那么快排是如何以基准值来区分左右子序列？

a.hoare版(PartSort1)

以待排序数组第一个元素为基准值，定义两个变量(left，right)分别指向待排序数组的左右边界。
先移动right，找到小于基准值的元素，right停止移动。移动left，找到大于基准值的元素，left停止移动，交换left 与 right的元素。重复上述操作，直到left 与 right 指向同一个元素，交换此时基准值 与 left指向的元素。就完成了以基准值为标准，将数组分成左右子数组。

如下：对数组{6,1,2,7,9,3,4,5,10,8}以6为基准值，来划分左右子序列

注意：

如何保证left 与 right 相遇的位置值一定小于基准值？

left 与 right相遇有两种情况：

• left 遇到 right ，此时right已经停止移动，代表right已经找到了小于基准值的元素，left 与 right相遇的值小于基准值
• right 遇到 left，上一次left 与 right 都找到相应元素并交换 or 此时left指向的就是数组最左边，此时left指向元素小于等于基准值，left 与 right相遇的值小于基准值

这是以右边界为基准值为列。如果以左边界为基准值，要保证left 与 right相遇元素小于基准值，要left先移动。

left要不要从基准值的位置开始移动？

• left必须从基准值的位置开始移动，假设对数组{0,2,5,9,1,3}进行快排，如果以0为基准值，left从2的位置开始移动，会导致2到0的左边去，使数组变为{2,0,5,9,1,3}。就不符合快排的划分。

//三数取中  针对已经有序的数组
int GetMiddle(int* a, int left, int right)
{
	int mid = (right - left) / 2 + left;

	if (a[mid] > a[left])
	{	
		if (a[mid] < a[right])
		{
			//left < mid < right
			return mid;
		}
		else if(a[left] > a[right])
		{
			//right < left < mid
			return left;
		}
		else
		{
			//left < right = mid
			return right;
		}
	}
	else
	{
		if (a[right] > a[left])
		{
			//mid < left < right
			return left;
		}
		else if (a[mid] < a[right])
		{
			//mid < right < left
			return right;
		}
		else
		{
			//right <= mid <= left
			return mid;
		}
	}
}

// 快速排序hoare版本
//注意1. 如何保证每次left == right时的值，小于等于keyi的值
//结束时两种情况  a.right遇left停，上一次循环结束时，right 与 left的值互换，此时left的值为小于等于keyi的值
//                b.left遇right停，这次循环right结束时，此时right的值小于等于keyi的值
//注意2. left开始要从keyi的位置起步
//如果left从keyi+1的位置起步，假如数组所有元素大于keyi的值，循环结束交换left与keyi的值，回造成keyi左右的值都大于keyi
int PartSort1(int* a, int left, int right)
{
	int keyi = GetMiddle(a, left, right);
	swap(&a[keyi], &a[left]);
	keyi = left;

	while (left < right)
	{
		while (left < right && a[right] > a[keyi])
		{
			right--;
		}

		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[left]);

	return left;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

b.挖坑法(PartSort2)

挖坑法与hoare的思路类似，保存基准值位置的元素(key)，使right找小于等于key的元素，left找大于key的元素，只不过left 与 right每次找到元素时，直接赋值到hole(坑位)处。不需要等left 与 right 都找到元素，才进行操作。

//三数取中
int GetMiddle(int* a, int left, int right)
{
	int mid = (right - left) / 2 + left;

	if (a[mid] > a[left])
	{	
		if (a[mid] < a[right])
		{
			//left < mid < right
			return mid;
		}
		else if(a[left] > a[right])
		{
			//right < left < mid
			return left;
		}
		else
		{
			//left < right = mid
			return right;
		}
	}
	else
	{
		if (a[right] > a[left])
		{
			//mid < left < right
			return left;
		}
		else if (a[mid] < a[right])
		{
			//mid < right < left
			return right;
		}
		else
		{
			//right <= mid <= left
			return mid;
		}
	}
}


// 快速排序挖坑法  
//每找到一个不符合要求的数，交换
int PartSort2(int* a, int left, int right)
{
	int keyi = GetMiddle(a, left, right);
	swap(&a[keyi], &a[left]);

	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] > key)
		{
			right--;
		}
		swap(&a[hole], &a[right]);
		hole = right;

		while (left < right && a[left] <= key)
		{
			left++;
		}
		swap(&a[hole], &a[left]);
		hole = left;
	}

	a[hole] = key;
	return hole;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

c.前后指针法(PartSort3)

前后指针法也就是双指针法，一个指针cur遍历待排序数组，一个指针prev指向小于等于基准值(key)的最后一个元素。如果cur指向元素小于等于key，使prev先移动，在交换cur 与 prev指向的元素。如果cur指向元素大于key，cur移动，prev不动。直到cur遍历完数组，交换prev指向元素 与
key.。即可将数组分成小于key key 大于key的三部分。

//三数取中
int GetMiddle(int* a, int left, int right)
{
	int mid = (right - left) / 2 + left;

	if (a[mid] > a[left])
	{	
		if (a[mid] < a[right])
		{
			//left < mid < right
			return mid;
		}
		else if(a[left] > a[right])
		{
			//right < left < mid
			return left;
		}
		else
		{
			//left < right = mid
			return right;
		}
	}
	else
	{
		if (a[right] > a[left])
		{
			//mid < left < right
			return left;
		}
		else if (a[mid] < a[right])
		{
			//mid < right < left
			return right;
		}
		else
		{
			//right <= mid <= left
			return mid;
		}
	}
}

//思路类似于，在数组中删除val的值。
int PartSort3(int* a, int left, int right)
{
	int keyi = GetMiddle(a, left, right);
	swap(&a[keyi], &a[left]);

	keyi = left;
	int prev = left;
	for (int cur = left + 1; cur <= right; cur++)
	{
		//不能判断为 prev + 1 != cur 如果9,1,2,3,4,5,6。此时keyi的值为9。cur遍历到2时，会使9与2交换，使keyi的值发生改变
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			//prev++;
			swap(&a[prev], &a[cur]);
		}
	}

	swap(&a[prev], &a[keyi]);
	return prev;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

3.快速排序(非递归)

用栈的先进后出模拟递归。
先将此时数组元素范围[0,sz]压栈，然后将栈顶数据出栈，定为start 与 end。在以start 与 end为区间，选取基准值(key)，划分左子序列，右子序列。再将左子序列，右子序列的区间分别入栈。重复上述过程，如果左右子区间不存在就不入栈，直到栈中没有数据，此时数组已完成排序。

如下：

栈的代码在这里

//三数取中
int GetMiddle(int* a, int left, int right)
{
	int mid = (right - left) / 2 + left;

	if (a[mid] > a[left])
	{	
		if (a[mid] < a[right])
		{
			//left < mid < right
			return mid;
		}
		else if(a[left] > a[right])
		{
			//right < left < mid
			return left;
		}
		else
		{
			//left < right = mid
			return right;
		}
	}
	else
	{
		if (a[right] > a[left])
		{
			//mid < left < right
			return left;
		}
		else if (a[mid] < a[right])
		{
			//mid < right < left
			return right;
		}
		else
		{
			//right <= mid <= left
			return mid;
		}
	}
}

//思路类似于，在数组中删除val的值。
int PartSort3(int* a, int left, int right)
{
	int keyi = GetMiddle(a, left, right);
	swap(&a[keyi], &a[left]);

	keyi = left;
	int prev = left;
	for (int cur = left + 1; cur <= right; cur++)
	{
		//不能判断为 prev + 1 != cur 如果9,1,2,3,4,5,6。此时keyi的值为9。cur遍历到2时，会使9与2交换，使keyi的值发生改变
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			//prev++;
			swap(&a[prev], &a[cur]);
		}
	}

	swap(&a[prev], &a[keyi]);
	return prev;
}


// 快速排序 非递归实现
//借助栈的先进后出，先进左区间，再进右区间。
void QuickSortNonR(int* a, int left, int right)
{
	Stack s;
	StackInit(&s);

	StackPush(&s, left);
	StackPush(&s, right);
	while (!StackEmpty(&s))
	{
		int end = StackTop(&s);
		StackPop(&s);
		int stark = StackTop(&s);
		StackPop(&s);

		int pivot = PartSort3(a, stark, end);
		// [start, pivot - 1]  pivot  [pivot + 1, end]
		//左区间
		if (stark < pivot - 1)
		{
			StackPush(&s, stark);
			StackPush(&s, pivot - 1);
		}
		//右区间
		if (pivot + 1 < end)
		{
			StackPush(&s, pivot + 1);
			StackPush(&s, end);
		}
	}

	StackDestroy(&s);
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

---

• 快排的时间复杂度：O(NlogN)
• 快排的空间复杂度：O(logN)
• 稳定性：不稳定
• 如果是对一组元素相同的数据处理，那么快排的时间复杂度就退化为O(N^2)，三路划分可以解决这类问题。

四、归并排序

归并排序思路：先将待排序数组分解为有序数组，再两两合并有序数组。

归并排序(递归)

如上图，我们对数组{10,6,7,1,3,9,4,3}进行分解，直到每个区间只有一个元素时(保证每个区间都是有序的)，再两两合并区间(需要借助额外的数组tmp来保存合并的数组，再将tmp数组copy置原数组中)。[类似于二叉树的后序遍历]

// 归并排序递归实现
void _MergeSort(int* a, int start, int end, int* tmp)
{
	if (start == end)
		return;

	int mid = (end - start) / 2 + start;
	//[start, mid] [mid + 1, end]
	_MergeSort(a, start, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//合并有序数组
	int begin1 = start, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//要注意每次copy数组的起始位置
	memcpy(a + start, tmp + start, sizeof(int)*(end - start + 1));
}


//类似于二叉树的后序遍历
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * (n + 1));
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

归并排序(非递归)

归并排序的非递归实现并不需要借助栈或队列，只用循环即可完成。
我们先对待排序数组中一个元素与一个元素两两合并，再对数组中两个元素与两个元素两两合并，再对数组中四个元素与四个元素两两合并，直到要合并的元素个数大于数组元素结束，此时数组有序。

如果在合并最后一组有序数组时，有一下情况要注意：

• 情况1：end2 > begin2 > end1 > sz(数组元素个数 - 1)，begin1 < sz。
• 情况2：end2 > begin2 > sz(数组元素个数 - 1), begin1 < end1 = sz
• 情况3：end2 > sz，begin1 < end1 < begin2 < sz
  
  对于情况1，情况2而言，我们只需要结束这次合并即可，因为begin1 到 sz的区间内数组是有序的
  对于情况3而言，我们只需要改变end2即可，使end2 = sz。

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * (n + 1));
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	
	for (int gap = 1; gap < n; gap *= 2)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = begin2 + gap - 1;

			if (end1 >= n || begin2 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;

			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}//for (int i = 0; i < n; i += 2 * gap)
	}//for (int gap = 1; gap <= n / 2; gap++)

	free(tmp);
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

• 时间复杂度：O(NlogN)
• 空间复杂度：O(N)
• 稳定性：稳定
• 归并排序思路更多解决的是外排序问题

五、计数排序

计数排序也就是建立一个映射关系，来进行排序。
我们先在待排序数组中查找最大值(max) 与 最小值(min)，再创建一个空间(tmp)大小为(max - min + 1)的数组，将次tmp置0，遍历待排序数组，将每个元素 - min所对应在tmp的位置+1。再遍历tmp空间，如果tmp中元素不为0的，将其加上min，放入待排序数组并将tmp中元素减一。

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (min > a[i])
			min = a[i];
		if (max < a[i])
			max = a[i];
	}

	int* tmp = (int*)malloc(sizeof(int) * (max - min + 1));
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	memset(tmp, 0, sizeof(int) * (max - min + 1));

	for (int i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}

	int k = 0;
	int i = 0;
	while (i < (max - min + 1))
	{
		if (tmp[i] != 0)
		{
			a[k++] = i + min;
			tmp[i] -= 1;
		}
		else
		{
			i++;
		}
	}

	free(tmp);
}
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
37
38
39
40
41
42

• 时间复杂度：O(N)
• 对于数组元素并不是集中的，会造成空间浪费

---

总结

以上就是我对于直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序的理解。感谢支持！！！