数据结构初阶--排序2

前言

本篇文章将继续介绍快排，归并等排序算法以及其变式。

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

思路

其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
这里我们讲解三种方法：

hoare版本

hoare版本就是hoare这位大佬经过不断总结得出的方法，但这个方法存在很多需要注意的点，稍不注意就会出现bug。
首先，我们在找比key大或者小的数时，要保证left必须要小于right，因为完全有可能出现极端情况，所有数都比key小或者比key大,如果我们不添加这样的限制条件，就可能出现越界访问的情况。而且我们还需要注意书写的顺序，我们看下面这两个代码书写

while (left<right && arr[right]>=arr[keyi])
while (arr[right]>=arr[keyi]&& left<right)
1
2

显然，第一种书写才是正确的，因为我们要先判断再访问，这个顺序不能乱。
其次，我们还要特别注意的是，如果keyi在左边，那么右边就要先走，反之如果keyi在右边，那么左边就要先走，因为我们最后在交换keyi和左右相遇点的值时，要保证keyi的值大于相遇点的值，这时候我们就要注意，如果是左边先走，那么最后一次走是left走向right停下，这时候相遇的点是right，而right指向的值此时是比keyi大的，如果再交换，那么这个大的值就会跑到keyi的位置，这与我们的想得到的结果是背道而驰的，所以我们需要先让右先走，最后一次走就是right走left，这样再交换就对了。

这两个顺序不能换!（假设左边为keyi的情况下)
这是一趟找key将大于key和小于key分到左右两边的过程，接下来我们再递归key左边和右边直到begin和end相等为截止条件。

代码实现

hoare版本的代码实现如下

//hoare
int PartSort1(int arr[],int left,int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left<right && arr[right]>=arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}

		Swap(&arr[right], &arr[left]);
	}
	Swap(&arr[keyi], &arr[left]);
	return left;
}
void QuickSort(int arr[],int begin,int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort1(arr,begin,end);

	QuickSort(arr,begin,keyi-1);
	QuickSort(arr,keyi+1,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

挖坑法

挖坑法在hoare版本上做出了一定的优化，它可以有效避免我们需要考虑选左边为key时右边先走，右边为key时左边先走，因为我们在左边挖坑，肯定要右边找数来填，右边挖坑，肯定也要左边找数来填，我们通过图来分析

我们先将最左端下标赋值给hole，然后用key把最左端的值储存起来，避免被覆盖，然后右边先开始找小，找到了就把值放到左边的坑中，这样就形成了新坑（相当于把hole移到了新的位置），如此反复，直到左右相遇，再将我们一开始保存的key值放到hole中，整个流程就走完了。

代码实现

挖坑法的代码实现如下

int PartSort2(int arr[], int left, int right)
{
	int midi = GetMidiIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);

	int hole = left;
	int key = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;

	}
	arr[hole] = key;
	return hole;
}
void QuickSort(int arr[],int begin,int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort2(arr,begin,end);

	QuickSort(arr,begin,keyi-1);
	QuickSort(arr,keyi+1,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

前后指针法

前后指针的方法思路就是定义cur和prev两个指针，cur在left+1的位置，而prev就在left的位置，cur不停往右走，走到right时停止，在走的过程中，遇到比key小的值就把该值与prev对调,同时prev也往后走，相当于prev和cur指针之间的值一直是大于key的，在对调的过程中交替着往后走，这样最终大于key的都在右边，小于key的都在做变了，我们再通过下面这幅图来分析。

代码实现

前后指针法的代码实现如下

int PartSort3(int arr[], int left, int right)
{
	int midi = GetMidiIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSort(int arr[],int begin,int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort3(arr,begin,end);

	QuickSort(arr,begin,keyi-1);
	QuickSort(arr,keyi+1,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

快排优化

快排在大部分情况下性能都十分的优越，但数组难免会有一些极端的情况，比如我们在取key的值时，通常都是直接取最左或者最右的值，但是不排除最左或最右的值一直或大部分时候都是当前这段数列中最大或最小的，那么在排序的时候需要移动数据的次数就会大大增加，这是得不偿失的。还有一种情况，整组数据中与key相等的值占绝大部分，我们在前面三种方法中都没有单独考虑这种情况，这样移动数据的次数同样会增加很多，而且完全没有必要。接下来我们就通过三项取中和三指针法对以上两种特殊情况进行优化。

三项取中法

首先是三项取中，我们可以考虑从最左，最右和中间的三个数中取第二大的值作为key值。这样就可以得到一个较平均的值。

代码实现

三项取中的代码如下，我们单独写一个函数，再将返回值与最左边/最右边的值互换（因为key还是取最左边或最右边的值）。

int GetMidiIndex(int arr[], int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[mid] < arr[left])
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else if (arr[right] < arr[mid])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else if (arr[right] > arr[mid])
		{
			return mid;
		}
		else
		{
			return 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

三指针

我们来看力扣里的一道题
力扣–排序数组
题目描述如下

描述很简单，就是让你排序数组，但是当我们把快排代码书写进去，发现居然显示超出时间限制了,我们来看未通过的测试用例：

我们发现这个测试用例的值全部都是2，这就是刚刚提到的大部分或全部和key值相等的情况，所以我们要采用hoare和前后指针结合的新方法–三指针来解决这类特殊情况。
三指针的基本思路是：创建left，right和cur三个指针，其中left到right之间放置和key值相等的值，cur用来从左往右遍历当前范围内的数据.
1，arr[cur]<key,交换arr[cur]和arr[left]的值，left++,cur++.
2，
3，

代码实现

三指针代码实现如下

void QuickSort(int arr[],int begin,int end)
{
	//三指针
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int cur = left + 1;

	int midi = GetMidiIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);
	int key = arr[midi];

	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			Swap(&arr[left], &arr[cur]);
			++left;
			++cur;
		}
		if (arr[cur] > key)
		{
			Swap(&arr[cur], &arr[right]);
			--right;
		}
		else
		{
			cur++;
		}
	}

	QuickSort(arr, begin, left - 1);
	QuickSort(arr, right + 1, 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

快排非递归

在学习完快排的递归操作后，我们现在来学习快排的非递归实现。
要实现快排非递归，我们需要借助栈这个数据结构，每次将左右端值压栈，然后再取出进行单趟排序，再修改左右端值再压栈，再取出，直到栈为空截止。
和递归时的区间一样，此时数组被分为了[left,mid-1]mid[mid+1,right]三个部分，和递归终止条件begin>=end类似，只有当left<mid-1和mid+1<right才会继续进行压栈操作，否则不用再往里放入数据了。
还要注意栈后进先出的原则，如果先放左再放右，那么取的时候取出来的顺序就是先右后左！

代码实现

快排非递归的代码实现如下(栈的操作就没有具体写出了 可以参照栈的实现：栈的实现（C语言）)

int PartSort1(int arr[],int left,int right)
{
	int midi = GetMidiIndex(arr, left, right);
	Swap(&arr[left], &arr[midi]);

	int keyi = left;
	while (left < right)
	{
		while (left<right && arr[right]>=arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}

		Swap(&arr[right], &arr[left]);
	}
	Swap(&arr[keyi], &arr[left]);
	return left;

}
void QuickSortNonR(int arr[], int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, left);
	STPush(&st, right);

	while (!STEmpty(&st))
	{
		int right = STTop(&st);
		STPop(&st);
		int left = STTop(&st);
		STPop(&st);
		int mid = PartSort1(arr, left, right);

		if (right > mid + 1)
		{
			STPush(&st, mid + 1);
			STPush(&st, right);
		}

		if (left < mid - 1)
		{
			STPush(&st, left);
			STPush(&st, mid - 1);

		}
	}
	
	STDestroy(&st);
}
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

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

思路

归并的递归思路和二叉树的后序遍历操作思想类似，这个是有别于快排的，快排是前序操作思想，每次选出一个key值，将比key大的放右边，比key小的放左边，再在小区间里选出key，再重复操作，而归并排序思想和这个完全相反，我们要先保证最后的数组是有序的，再两两归并，四四归并，八八归并，直到整个数组都有序。所以我们要把递归操作写在归并操作前面，下面来讲归并操作：
归并操作和力扣一道合并两个有序数组类似，我们要能进行归并操作也是首先要保证两个子序列有序，感兴趣的读者可以去做一下这道题：
力扣–合并两个有序数组
我们归并的主体思路是：
1，再动态开辟一个数组temp。
2，分别用begin1和begin2作为下标遍历两个数组，依次比较，将较小值尾插。
3，设定end1和end2分别作为两个数组的截止条件，当某一个数组走到尾后，另一个数组剩余的值一定大于走完这个数组的所有值，所以直接把剩余数值依次拷贝到temp数组即可。
4，最后再将temp数组拷贝回arr进行递归。

代码实现

归并排序的代码实现如下：

void _MergeSort(int arr[],int temp[],int begin,int end)
{
	if (begin == end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(arr, temp, begin, mid);
	_MergeSort(arr, temp, mid + 1, end);
	
	int begin1 = begin, end1 = mid;
	int begin2 = mid+1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[i++] = arr[begin1++];
		}
		else
		{
			temp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = arr[begin2++];
	}

	memcpy(arr + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int arr[], int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(arr,temp,0,n-1);
	free(temp);
}
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

归并非递归

在学完归并排序的递归操作后，我们再来学习归并操作非递归实现。
我们要想实现非递归，其实就相当于从递归操作最深处开始利用循环逐步往浅走即我们首先要两两归并（一个数据我们默认可以看作有序），再四四归并，再八八归并，直到全部有序，但我们会发现一个问题，只有当数据个数为2的整数倍次方时，才能保证每次归并都不会发生越界，否则无法保证。
可能有些抽象，我们通过画图来理解：
假设我们有10个数据。

我们定义gap为间隔，第一次是1，第二次是2，以此类推，我们再用i来每次遍历数组归并（每次往后走2gap）,每两组需要归并的数组（比如图中第一次归并的2和3）左右区间分别为 i i+gap-1 i+gap i+2gap-1.,因为i我们添加了限制条件，是恒小于长度的，所以不会越界，但剩下三个边界都有可能超出范围，我们依据图来分析

我们可以把这三种情况的修正分为两类
1，第一种和第二种情况，有一个区间根本不存在，所以我们直接break。
2，第三种情况，两个区间都存在，我们只需要将右区间的右边界修改为n-1即可。

如果我们在最后才拷贝数据，数组最后可能会有随机值出现，所以我们归并一次，就拷贝一次。

代码实现

归并排序非递归代码实现如下

void MergeSortNonR(int arr[], int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap < n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = arr[begin2++];
			}
			memcpy(arr + i, temp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(temp);
}
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

计数排序

计数排序是一种非比较排序，计数排序又称为鸽巢原理，是一种对哈希表的变形应用。

思路

计数排序的思路比较简单，先遍历一遍数组，确定最大和最小值，作为我们创建哈希表的边界依据，我们把最小的数作为基准。然后我们再遍历一遍数组，统计相同元素出现的次数，即在对应的位置++（每个位置最初的值都为0）.
然后再遍历一遍哈希表将统计的结果放回到原数组中即可。
我们不难发现，当数据很集中时，它的时间复杂度为0（N）,是比堆排，希尔排序甚至比快排（O(N*logN)）还要快的，但我们也就可以发现它的劣势，那就是当数据非常分散时，它的效果是很不好的。

代码实现

计数排序的代码实现如下;

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}

		if (a[i] > max)
		{
			max = a[i];
		}
	}

	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, sizeof(int) * range);

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}

	// 排序
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
		{
			a[k++] = j + min;
		}
	}
}
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

到这里，六大排序的全部内容就讲完了，如有出入，欢迎指正。