数据结构知识点总结--排序_数据结构排序知识点概括

#数据结构知识点总结–排序
主要是结合代码和动图总结
目录：

文章目录

• • @[toc]

##插入排序
均以排升序进行解释

###直接插入排序

1.先用动图演示一次插入，以在数组{1，3，4}中插入2为例：
文字描述：

①找到数组末尾，用指针end标记
②2与末尾元素4进行对比，2 < 4，插入
③2与前一个元素3进行对比，2 < 3，插入
④2与前一个元素1进行对比，2 > 1，停止

2.下面动图演示使用插入法进行排序，以数组{2，4，3，1}为例进行排序
文字描述：

①先将第一个元素视作一个数组，再将第二个元素视作待插入元素，进行一次插入；
②一次插入完成后，前两个元素便是有序的，将前两个元素视作一个数组，再将第三个元素视作待插入元素，进行一次插入；
③又一次插入完成后，前三个元素便是有序的，将前三个元素视作一个数组，再将第四个元素视作待插入元素，进行一次插入；
④以此类推，直到将最后一个元素进行一次插入，排序完成。

代码如下：

void InsertSort(int* a,size_t n)//直接插入排序
{
	assert(a != NULL);

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

###希尔排序
是直接插入排序的一种优化，先进行预排序再进行直接插入排序

1.先用动图演示希尔排序的过程，以最坏情况：逆序 为例进行演示
文字描述：

①先将数组分成多个小的数组，图中是每隔两个元素选取一个
②对每个小数组分别进行直接插入排序，整个数组的顺序重新排序后会变得更接近有序
③再对整个数组进行直接插入排序，就可以得到升序的数组

2.再来解释希尔排序的好处，仍以上图数据为例

void ShellSort(int* a, size_t n)//希尔排序
{
	assert(a != NULL);

	//预排序
	int gap = n / 3 + 1;//希尔排序所需要的跨度
	while (gap > 1)
	{
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			while (end >= 0)
			{
				if (a[end] > a[end + gap])
				{
					Swap(&a[end], &a[end + gap]);
					end -= gap;
				}
				else
				{
					break;
				}
			}
		}
		gap = gap / 3 + 1;
	}
	//直接插入排序
	InsertSort(a, n);
}
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

##选择排序

###选择排序
1.最简单的选择排序
文字描述：

①每次遍历选取最小（大）的数，然后与最左（右）边的元素交换位置
②再将从下一个元素开始遍历选取剩下元素中最小（大）的数，然后与最左（右）边的元素交换位置
③重复以上步骤直到剩下最后一个元素。

代码如下：

void SelectSort(int* a,size_t n)//选择排序
{
	assert(a != NULL);
	
	for (int i = 0; i < n; i++)
	{
		int min = i;
		for (int j = i+1; j < n; j++)
		{
			if (a[min] > a[j])
			{
				min = j;
			}
		}
		Swap(&a[min], &a[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.优化的选择排序
文字描述：

每次遍历要选取出当前数组中最大和最小的数，采用两个指针，从最左和最右同时开始排序

代码如下：

void SelectSort(int* a, size_t n)//选择排序
{
	assert(a != NULL);

	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int min = left;
		int max = left;
		for (int i = left; i <= right;i++)
		{
			if (a[min] > a[i])
			{
				min = i;
			}
			if (a[max] < a[i])
			{
				max = i;
			}
		}
		Swap(&a[left],&a[min]);
		if (left != max)
		//防止出现max在最左，min在最右，min与left交换后,max的值被改变的情况
		{
			Swap(&a[right],&a[max]);
		}
		left++;
		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

###堆排序

1.先将数组建堆，如果要排升序，就建大堆；排降序，就建小堆
文字说明：

①先找到第一个非叶子结点，下标为(n-2)/2;
②找出该结点中左右孩子中较大的值，与之交换；
③交换完毕后，下标减一，即找第二个非叶子结点，重复以上操作
④直到找到根结点，建堆完毕

2.建堆完毕后，使用替换法进行排序
文字说明：

①先将建大堆之后的首尾交换，则最大的数在最末尾，将末尾向前移动一个位置
②再从首到尾进行建大堆，找出数组中第二大的数，再进行首尾交换，再将末尾向前移动一个位置
③重复以上操作，直到找到根结点，排序完毕。

void AdjustDown(DataType* a, size_t n, int root)//建大堆
{
	int parent = root;
	int child = parent * 2 + 1;

	while (child < n)
	{
		if ((child+1)<n && a[child] < a[child+1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			DataType tmp = a[parent];
			a[parent] = a[child];
			a[child] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void MakeHeap(DataType* a, size_t n)//建堆
{
	int i = (n - 1) >> 1;
	for (; i >= 0; --i)
	{
		AdjustDown(a,n,i);
	}
}

void HeapSort(DataType* a, size_t n)
{
	MakeHeap(a,n);
	int end = n-1;
	while (end > 0)
	{
		DataType tmp = a[end];
		a[end] = a[0];
		a[0] = tmp;
		AdjustDown(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
43
44
45
46
47
48
49
50

##交换排序

###冒泡排序
冒泡排序比较简单，直接上代码：

void Bubble(DataType* a,size_t n)
{
	assert(a != NULL && n > 0);
	for(int end = n;end > 0;--end)
	{
		int flag = 0;
		for(int i = 1;i < end;++i)
		{
			if(a[i-1] > a[i])
			{
				Swap(&a[i-1],&a[i]);
				flag=1;
			}
		}
		if(flag == 0)
		{
			break;
		}
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

###快速排序
####快排的三种方法
1.左右指针法

文字描述：
①首先选取数组最右（或最左）的元素为key，下标begin=left；end=right；
②begin从左往右寻找比key大的元素，找到就停下来；end从右往左寻找比key小的元素，找到就停下来；然后交换下标begin和end对应的元素
③重复 ① 和 ② 步骤，直到不再满足begin < end
④将下标begin对应的元素与数组最右边的元素交换，注意：不是和key交换，key只是保存最右元素的值的临时变量

⑤至此，最右元素一定被交换到了属于自己顺序序号的位置，而其左右两边可看作被分成两个新的数组，即划分子问题，进行递归，递归停止条件是left >= right，即只有一个元素

代码如下：

int LeftRightPointer(int* a,int left,int right)//左右指针快排
{
	int begin = left;
	int end = right;
	
	//选key的优化
	int mid = Mid(a, left, right);
	Swap(&a[mid], &a[right]);

	int key = a[right];
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[right]);
	return begin;
}

void QuickSort(int* a,int left,int right)//快排
{
	assert(a != NULL);

	if (left >= right)
	{
		return;
	}

	int div = LeftRightPointer(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 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
37
38
39

2.挖坑法
文字描述：

①与左右指针法类似，稍微有点区别的是挖坑法需要一个额外的下标index记录位置
②不再是a[begin]和a[end]交换,而是a[index]=a[begin];index=begin;以及a[index]=a[end];index=end;
③其他部分基本没什么变化

代码如下：

int Digging(int* a, int left, int right)//挖坑快排
{
	int begin = left;
	int end = right;
	int key = a[right];
	int index = right;
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[index] = a[begin];
		index = begin;

		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[index] = a[end];
		index = end;
	}
	a[index] = key;
	return index;
}

void QuickSort(int* a,int left,int right)//快排
{
	assert(a != NULL);

	if (left >= right)
	{
		return;
	}

	int div = Digging(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 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
37
38
39

3.前后指针法
文字描述：

①与上两种算法思路也类似，区别在于不再是从两端向中间出发，而是定义两个指针，int prev=left;int post=prev-1;
②主要算法：
1.a[prev] < key,prev停下来，post++，如果prev != post，则交换两位置的数值；
2.a[prev] >= key，prev++
③其他部分基本没什么变化

代码如下：

int PrevPostPointer(int* a, int left, int right)//前后指针法
{
	int prev = left;
	int post = prev - 1;
	int key = a[right];
	while (prev < right)
	{
		if (a[prev] < key)
		{
			post++;
			if (post != prev)
			{
				Swap(&a[post], &a[prev]);
			}
		}
		prev++;
	}
	post++;
	Swap(&a[prev], &a[post]);
	return post;
}

void QuickSort(int* a,int left,int right)//快排
{
	assert(a != NULL);

	if (left >= right)
	{
		return;
	}
	
	int div = PrevPostPointer(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 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

####快排的优化
快排只有进行优化之后才能达到O（n*log n ）的时间复杂度

1.选key的优化

以排升序为例，如果当前顺序比较接近降序，即最小的值在最右边，如数组{7，8，5，4，2，3，1，0}，对它进行划分子问题时，很容易出现数据集中在右边，而左边要么没有元素或者只有一个元素的情况，这样的话效率就会变低，因此为了防止这种情况出现，进行选key的优化。

方法：三数取中法

取数组最左、最右和中间三个数，再取这三个数中的第二小的数，即中间值，作为key；这样最起码能保证，就算是最坏的情况，取到的也是整个数组中第二小的数值。

代码如下：

//以左右指针法为例
int Mid(int* a,int left,int right)//三数取中,返回中间值的下标
{
	int mid = left + ((right - left) >> 1);
	if (a[left] > a[right])
	{
		if (a[left] < a[mid])
		{
			return left;
		}
		else if (a[right] < a[mid])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else//a[left] <= a[right]
	{
		if (a[right] < a[mid])
		{
			return right;
		}
		else if (a[left] < a[mid])
		{
			return mid;
		}
		else
		{
			return left;
		}
	}
}

int LeftRightPointer(int* a,int left,int right)//左右指针快排
{
	int begin = left;
	int end = right;
	
	//选key的优化
	int mid = Mid(a, left, right);
	Swap(&a[mid], &a[right]);

	int key = a[right];
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[right]);
	return begin;
}
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

2.小区间优化

当数组的区间比较小的时候，如果还用快排的话，效率反而不高，因为有栈帧的消耗会降低效率，因此当区间达到一定范围的时候，换成别的效率高的排序算法会更高效一些

代码如下：

void QuickSort(int* a,int left,int right)//快排
{
	assert(a != NULL);

	if (left >= right)
	{
		return;
	}

	//小区间优化
	if (right - left > 10)//当数组区间大于10时，使用快排
	{
		//int div = LeftRightPointer(a, left, right);
		//int div = Digging(a, left, right);
		int div = PrevPostPointer(a, left, right);
		QuickSort(a, left, div - 1);
		QuickSort(a, div + 1, right);
	}
	else//小于10时，使用直插排序
	{
		InsertSort(a, right - left + 1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

####非递归的快排

使用栈来存储下标

代码如下：

void QuickSortNR(int* a, int left, int right)//快排，非递归
{
	assert(a != NULL);
	Stack s;
	StackInit(&s);
	StackPush(&s, left);
	StackPush(&s, right);
	while (StackEmpty(&s) != 0)//栈不为空
	{
		int end = StackTop(&s);
		StackPop(&s);
		int begin = StackTop(&s);
		StackPop(&s);

		//int div = LeftRightPointer(a, begin, end);
		//int div = Digging(a, begin, end);
		int div = PrevPostPointer(a, begin, end);

		if (begin < div-1)
		{
			StackPush(&s, begin);
			StackPush(&s, div - 1);
		}
		if (end > div + 1)
		{
			StackPush(&s, div + 1);
			StackPush(&s, 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

##归并排序
文字描述：

①与快速排序类似，但是归并排序不使用key，而是将数组进行递归二分
②当二分为只剩下两个或一个元素的时候，比较大小排序
③递归回溯时，将数组两两进行合并，并且合并后保持有序
④回溯完毕后，整个数组就有序了
注意：和“单链表的合并”不同的是，归并排序是对数组进行操纵，因此需要额外创建一个数组保存数据
如图：
1.递归二分

2.排序后回溯

3.回溯时进行合并，并保持合并后的数组依然有序

4.递归回溯完毕后，整个数组有序

##计数排序
文字描述：
原理跟哈希表的K-V模型比较相似
①遍历一遍数组，得出数组的范围range，创建一个大小为range的数组，即哈希表，初始化为全0
②再从头开始遍历数组，数字重复出现一次，在其相应的位置对应的数值加一
③从左到右开始遍历哈希表，将数值不为0的位置的下标存储到原数组中，且数值是多少就存储多少个

#对比