排序算法（二）

冒泡排序—（稳定）

说起冒泡排序，我们可以想象鱼吐泡泡的情形，采用冒泡排序我们每一趟排序下来都至少可以确定一个元素的位置，参考冒泡排序动图来理解：

分析：

待排序的数组：
3 ，44，38，5，47，15，36

接下来我们来分析一下冒泡排序的基本原理：

第一趟排序之后进行第二次排序，同样是从起始位置开始进行相邻元素的比较，可以选出次大元素放到倒数第二个位置，依次类推直到所有元素都放到了正确的位置为止。

代码：

void BubbleSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; ++i)   //排序趟数
	{
		for (int j = 1; j < size - i; ++j) {
			if (arr[j] < arr[j - 1])
				Swap(&arr[j], &arr[j - 1]);    
				//每一趟选出一个最大元素
		}
	}
}


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

时间复杂度：
O（n^2） — 双层循环进行相邻元素比较
空间复杂度：
O（1）--------- 并未使用到辅助空间

快速排序 （重点）----- 不稳定

快速排序：
每次选定一个固定的元素作为排序的基准值，以这个基准值为标准可以将整个待排序的数组分为两个部分，然后以递归形式在对它的左右两个区间进行在划分

由此可见选取的这个基准值是整个快排的核心，每一趟排序之后都可以确定好所选的基准值的正确位置，假如每次选取最后一个元素作为基准值，相应的排序代码为：

void QuickSort(int arr[], int left, int right)
{
	//左闭右开
	if (left < right) {
		//基准值将数组分为左右两个区间
	//div 为最后返回的基准值的位置
		int div = Partion1(arr, left, right);

		//递归对基准值的左右两个区间在进行划分
		QuickSort(arr, left, div);
		QuickSort(arr, div + 1, right);
	}
}

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

对于区间的划分我在这里介绍三种方式：

一、hoare 划分

hoare 划分的基本思路：
选择最后一个元素作为基准值：

int key=arr[right - 1];

分别定义一个 begin 、end 变量记录待排序数组的起始与结束位置，begin 从前往后找第一个大于基准值的位置停止自增，然后 end 从后往前找第一个小于基准值的位置停止自增，交换 begin 与 end 位置元素，实现了小元素往前放，大元素放后方，并依次基础进行循环。

起始位置：

交换过程：

此时，以基准值为 8 将整个数组划分为了左（小于基准值）右（大于基准值的部分）两个部分 ，然后需要采用递归调用形式在对基准值 8 的左右两个区间在进行划分

代码：

int Partion1(int arr[], int left, int right)
{
	int key = arr[right - 1];  //基准选取最右元素

	int begin = left;
	int end = right - 1;

	while (begin < end) {

		while (begin < end && arr[begin] <= key)
			++begin;
		while (begin < end && arr[end] >= key)
			--end;

		if (begin < end) {
			Swap(&arr[begin], &arr[end]);
		}
	}
	if (begin != right - 1)
		Swap(&arr[begin], &arr[right - 1]);
	return end;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、挖坑法划分

选定基准值：

int key=arr[right-1];

begin、end 分别定义为待排序数组的起始与末尾位置。

由于选定了基准值为最后一个元素的位置，因此改位置可以看作一个坑位，需要从前往后找第一个大于基准值的位置 begin，并将元素填坑，则此时的 begin 为坑，需要从 end 向前找第一个小于基准值的位置，进行填坑，依次循环，直到 begin==end 循环停止。

起始位置：

进行填坑：

直到最后，begin 与 end 相遇，则将基准值放置在 begin（或 end ,，此时两者相等） 位置

此时 ，以基准值 8 将数组划分为了左右两个区间，再次递归进行划分。

代码：

int Partion2(int arr[], int left,int right)
{
	int begin = left;
	int end = right - 1;
	int key = arr[end];

	while (begin < end) {
		while (begin < end && arr[begin] <= key)
			++begin;
		if (begin < end)
		{
			arr[end] = arr[begin];
			--end;
		}

		while (begin < end && arr[end] >= key)
			--end;
		if (begin < end) {
			arr[begin] = arr[end];
			++begin;
		}
	}
	arr[begin] = key;
	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

三、前后指针法划分（难理解）

起始位置：

cur 记录当前元素，pre 记录 cur 前一个位置元素
cur 从前向后寻找大于 基准值的位置，当pre++ 等于 cur 时，不进行交换操作，cur++，即 pre 记录了第一个大于基准值的位置：

cur++，pre 不变，但此时 arr[cur]

再次进行循环：

前后指针的方法进行划分不是很好理解，读者可以参考代码自己画画来帮助理解哦~~

代码：

//当 prev 与 cur 是一前一后的关系时，说明 cur 从前往后暂未遇到大于基准值的元素
//当 prev 与 cur 中间有间隔，说明 prev 的下一个元素开始到cur 之间的元素都是大于 基准值的元素

int Partion3(int arr[], int left, int right)
{
	int cur = left;
	int prev = cur - 1;

	int key = arr[right - 1];

	while (cur < right) {
		if (arr[cur] < key && ++prev != cur) {
			Swap(&arr[prev], &arr[cur]);
		}
		++cur;
	}
	if (++prev != right - 1)
		Swap(&arr[prev], &arr[right - 1]);
	return prev;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

排序算法的改进

改进1

针对上述三种划分方法，我们每次都是采用最后一个元素作为基准值进行的划分，倘若最后一个元素为当前待排序数组的最大元素，则此时算法效率最低，是不合理的

例如：
1，5，0，8，3，6，2，9；此时 key=9，则其他元素全部都小于当前的基准值，导致循环结束之后，基准值的右侧没有划分成功的区间存在。

改进方法---------三数取中法
选取 首位值、末尾值、中间值三个数中间的那个作为划分的基准效率会更好一些：

//三数取中
int GetMiddleIndex(int arr[], int left, int right)
{
	int mid = left + ((right - left) >> 1);
	
	if (arr[left] < arr[right - 1]) {
		if (arr[mid] < arr[left])
			return left;
		else if (arr[mid] > arr[right - 1])
			return right - 1;
		else
			return mid;
	}
	else {
		if (arr[mid] > arr[left])
			return left;
		else if (arr[mid] < arr[right - 1])
			return right - 1;
		else
			return mid;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

则划分算法的改进：

将找到的中间大小的元素与末尾位置进行交换，则算法的使用跟前边的思路就保持一致了。

int key = GetMiddleIndex(arr, left, right);
	Swap(&arr[right - 1], &arr[key]);       //将基准值换到最后一个元素的位置
1
2

改进2

倘若我们选取了一个很不错的基准值来进行划分，则整个划分过程会如下图所示：

每一次选定基准值之后会将数列进行二划分，一直递归调用快排方法，倘若当前要排序的数列中元素特别多，则会发生递归调用栈溢出的现象出现，则会发生错误，因此我们要考虑调用栈溢出现象来对算法进行相应的优化。

优化一：

倘若当前待排序元素小于 16 时我们可以调用插入排序来完成元素的排序，算法的效率会有一定提升，避免了元素递归过深导致调用栈溢出问题。

void QuickSortOP(int arr[], int left, int right)
{
	//左闭右开
	if (right - left <= 16) {
		InsertSort(arr + left, right - left);    //元素较少时采用插入排序
	} 
	else {
		//基准值将数组分为左右两个区间
		//hoare 方法
		//int div = Partion1(arr, left, right);

		//挖坑法
		//int div = Partion2(arr, left, right);

		//前后指针法
		int div = Partion3(arr, left, right);

		//递归对基准值的左右两个区间在进行划分
		QuickSort(arr, left, div);
		QuickSort(arr, 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

优化二：

倘若要排序元素太多，会产生大量递归从而导致递归调用栈溢出，我们可以设置一个阈值，当递归调用栈超过这个阈值时，则停止递归，其实是可以采用堆的思想来进行改进-------------------堆排序

非递归形式实现快排—循环

可以采用 stack栈 来保存每一次需要进行排序的区间，并对待排序区间进行基准值的划分。

void QuickSortNot(int arr[], int size)
{
	Stack s;     //调用栈
	StackInit(&s);

	StackPush(&s, size);//右边界入栈
	StackPush(&s, 0);      //左边界入栈

	while (!StackEmpty(&s)) {
	//获取区间边界值
		int left = StackTop(&s);
		StackPop(&s);
		int right = StackTop(&s);
		StackPop(&s);

		if (right - left <= 1)
			continue;
//获取划分区间的基准值位置
		int div = Partion1(arr, left, right);

		StackPush(&s, right);
		StackPush(&s, div + 1);   //先保存右区间
		StackPush(&s, div);
		StackPush(&s, left);   //后保存左区间
	}

	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

时间复杂度：
O（NlongN）~ O（n^2）-------- 递归深度*元素比较次数
空间复杂度：
O（1）------- 并未使用辅助空间

归并排序-------稳定

归并排序主要分为两个部分----分割 、 合并
归并排序的基本思路如下图所示：

采用归并排序时，我们需要先对区间进行递归划分：

void _MergeSort(int arr[], int left, int right, int *tmp)
{
	if (right - left <= 1)
		return;

	int mid = left + ((right - left) >> 1);    //区间中点位置
	//划分左区间
	_MergeSort(arr, left, mid, tmp);
	//划分右区间
	_MergeSort(arr, mid, right, tmp);
	
	//对划分之后的区间进行合并
	MergeData(arr, left, mid, right, tmp);

	//辅助空间的数据拷贝到原空间
	memcpy(arr + left, tmp + left, (right - left) * sizeof(int));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

合并两个区间时，我们需要使得两个区间中元素在合并之后形成有序的一个区间，操作方法类似与我们的两个链表的合并操作：

void MergeData(int arr[], int left, int mid, int right, int* tmp)
{
	//左半侧 ---------- 左闭右开区间
	int begin1 = left;
	int end1 = mid;

	//右半侧
	int begin2 = mid;
	int end2 = right;

	int k = left;   //************************
	while (begin1 < end1 && begin2 < end2)
	{
		if (arr[begin1] <= arr[begin2]) 
			tmp[k++] = arr[begin1++];
		else
			tmp[k++] = arr[begin2++];
	}

	while (begin1 < end1)
		tmp[k++] = arr[begin1++];
	while (begin2 < end2)
		tmp[k++] = arr[begin2++];
}

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

最终使用归并排序算法：

void MergeSort(int arr[], int size)
{
	//需要借助辅助空间
	int* tmp = (int*)malloc(sizeof(int)*size);
	if (NULL == tmp)
		return;

	_MergeSort(arr, 0, size, tmp);      //划分子区间
	free(tmp);   //辅助空间使用结束一定要释放空间
}

1
2
3
4
5
6
7
8
9
10
11

归并排序的改进

由上述分析可知，我们的归并排序采用的也是递归形式的划分方式，倘若数据过大会导致递归调用栈过多而导致栈溢出，所有我们考虑采用循环的方式来进行优化区间的划分操作：

待排序的数组中有N个元素，我们可以将这 N 个元素起初就看作是N个单独的分组，然后进行两两的合并操作：

void MergeSortNot(int arr[], int size)
{
	//n 个元素，假设起初一个元素是一个分组-----n 个分组
	int *tmp = (int*)malloc(sizeof(int));
	if (NULL == tmp)
		return;

	int gap = 1;           //最初的合并步长为 1 
	while (gap < size) {
		for (int i = 0; i < size; i+=2*gap) {
			int left = i;
			int mid = left + gap;  //可能会越界
			int right = mid + gap;  //可能会越界
			if (mid > size)
				mid = size;         
			if (right > size)
				right = size;
			MergeData(arr, left, mid, right, tmp);    //区间合并
		}
		memcpy(arr, tmp, sizeof(int)*size);
		gap << 1;       //gap*=2;  步长增大 
	}
	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

时间复杂度：
O（NlongN）---------- 递归深度*元素比较次数

空间复杂度：
O（N）-------- 借助辅助空间来完成

非比较排序---------计数排序

该排序算法不会用带比较的方式来进行排序，而是需要采用一个计数器来实现：

遍历整个待排序的数组，记录从小到大数组中每个数出现的次数，因此该算法适用于所有数字都在一个固定大小的区间内的取值

void CountSort(int arr[], int size)
{
	//假设没有告诉区间中数据的范围
	int minVal = arr[0];
	int maxVal = arr[0];
	for (int i = 0; i < size; ++i)
	{
		if (arr[i] < minVal)
			minVal = arr[i];
		if (arr[i] > maxVal)
			maxVal = arr[i];
	}


	//统计计数空间
	int range = maxVal - minVal + 1;
//定义辅助空间，calloc 将空间初始化为全 0 
	int* countArray = (int*)calloc(range, sizeof(int));
	
	//统计每个元素出现个数
	for (int i = 0; i < size; ++i) {
		countArray[arr[i] - minVal]++;
//定义的赋值空间大小为 range = maxVal-minVal+1
//因此在数组中采用 arr[i]-minVal 是为了确保数组下标合法，表示记录值为 arr[i] 的元素出现的次数
//这种方式保存在 countArray 数组中的数字是从小到大开始进行存储的，数组空间内存储的是当前数字出现的次数
	}

	//数据回收,从小到大进行回收
	int index = 0;
	for (int i = 0; i < range; ++i) {
		while (countArray[i] > 0) {
			arr[index] = i + minVal;
			countArray[i]--;
			index++;
		}
	}

	free(countArray);             //释放辅助空间
}
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

测试：

	int tmp[] = { 1,2,1,1,2,2,6,9,8,7,7,9,9,4,5,6,2,4,5,0,4,5,5,8,3,5 };
	PrintArr(tmp, sizeof(tmp) / sizeof(tmp[0]));    //打印数组中元素
	//计数排序
	CountSort(tmp, sizeof(tmp) / sizeof(tmp[0]));
	PrintArr(tmp, sizeof(tmp) / sizeof(tmp[0]));
1
2
3
4
5

ps：
博文内容为原创，可能会有许多不足，欢迎读者们评论留言哦~~~