【数据结构】八大排序（二）

目录

前言：

冒泡排序

冒泡排序代码实现

冒泡排序特性总结

快速排序

单趟排序hoare版本

单趟排序挖坑法

单趟排序快慢指针法

 快速排序整体概览

快排的优化

三数取中法选key

小区间优化

前言：

上文介绍了直接插入排序，希尔排序，选择排序，堆排序并对四种排序进行了详尽的探讨，本文将以排序的基本思想，代码实现和各种排序的特性总结三个角度继续分析冒泡排序，快速排序

冒泡排序

冒泡排序的基本思想：

将待排序的序列从前向后依次比较相邻元素的值，如果逆序则交换；

升序：将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大，则交换，一趟下来后最大元素就在数组的末尾；

降序：将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素小，则交换，一趟下来后最小元素就在数组的末尾；

具体步骤如下：

1. 比较待排序序列中相邻的两个元素，如果发现左边的元素比右边的元素大，则交换这两个元素；
2. 每一对相邻的两个元素重复第一步的动作，从左至右依次执行，最后的元素一定是最大的元素；
3. 由于最大的元素位于数组尾元素的位置，下一趟两两比较的范围为待排序序列的首元素到 倒数第二个元素所处的位置，这段范围成为新的待排序序列，重复步骤1，步骤2；
4. 持续以上步骤 1， 步骤 2， 步骤 3 的工作，每重复一次需要排序的序列中少一个最右边的元素，直到没有任何一对数字需要比较排序；

......

冒泡排序代码实现

void bubblesort(int arr[], int n)
{
	// 外层循环控制冒泡排序的趟数
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		//内层循环控制要比较元素的个数
		int j = 0;
		for (j = 0; j < n - i - 1; j++)
		{
			int temp = 0;
			if (arr[j]>arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

冒泡排序特性总结

1.时间复杂度

冒泡排序的平均 时间复杂度是O(n^2)，最好时间复杂度是O(n)，最坏时间复杂度是O(n^2)；

2. 空间复杂度

额外开辟的空间为常数个，所以空间复杂度为O(1)；

3.算法稳定性

冒泡排序是一种稳定的排序算法，即相等元素的相对位置在排序前后不会发生改变；

快速排序

快速排序的基本思想：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列分别递归地进行快速排序，直到所有元素都排列在相应位置上为止；

单趟排序hoare版本

思路如下：

1. 选取待排序序列最左边元素作为基准值key，定义两个指针left和right分别指向待排序序列的最左侧和最右侧，right从右向左走，left 从左向右走；

2.right先走，right指针找比基准值key小的数；left后走， left找比基准值key大的数；找到后将两个数交换位置；

3. 当left指针与right指针相遇时，将相遇位置的值与基准值key进行交换；

void swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
//单趟排序hoare版本
int PartSort(int* a, int left, int right)
{
	int keyi = left;//选取左边作为基准值，则右边先走
	while (left < right)//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;
}

思考: 为什么left与right相遇位置处的数值比key要小？

left与right相遇有如下俩种情形：

相遇的第一种情形：right动left不动,相遇位置为left位置,left位置与前一个right位置进行了交换,交换之后left位置比key小；

相遇的第二种情形：right不动left动,相遇位置为right位置,此时left找大没有找到与right相遇,而right位置一定比key小；

思考：为什么左边取基准值key,右边先走？

保证当left与right相遇时，相遇位置小于基准值

1. right 停下时，left 与 right 相遇，由于right 找比 key小的值，所以此时 right 的位置一定比key小；
2. left 停下时，right 与 left 进行交换，交换后 left 指向的值比 key 小，此时 right 遇到 left 的位置一定比key小；

单趟排序挖坑法

思路如下：

1. 选择数组第一个数作为基准数,基准数的位置形成一个坑位；
2. 定义两个指针left与right分别指向待排序序列的第一个数和最后一个数；
3. 从right开始向前遍历,找到第一个小于基准数的数a[right]，将其赋值给a[left],a[right]成为一个新的坑位；
4. 从left开始向后遍历,找到第一个大于基准数的数a[left]，将其赋值给a[right],a[left]成为一个新的坑位；
5. 重复步骤3和4，直到left > right；
6. 将基准数填入最后一个坑中,a[left]=key；

//单趟排序挖坑法
int PartSort(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边先走
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole]=a[right];
		hole = right;
		//左边再走
		while (left < right&&a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;
	return hole;
}

单趟排序快慢指针法

思路如下：

1. 选取待排序序列的第一个元素作为基准值key；
2. 定义两个指针prev和cur,prev指针指向序列开头,cur指针指向prev指针的后一个位置；
3. 从cur开始向前遍历，如果遇到比key小的元素，就将prev指针向后移动一位，并交换prev和cur指向的元素；
4. 遍历结束后，将key与prev指向的元素交换位置，此时prev指向的位置就是key的最终位置；

//单趟排序前后指针法
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//(++prev)!=cur为了防止++prev与cur指向相同数值,此时交换毫无意义;
		if (a[cur] < a[keyi]&&(++prev)!=cur)
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[keyi], &a[prev]);
	return prev;
}

 快速排序整体概览

快速排序首先选取基准值key，将待排序序列分为两个子序列，左子序列放比基准值小的数，右子序列放比基准值大的数，然后再将子序列以以上方式同样分割，直到数组有序，下图单趟排序采取hoare版本

• 经过一趟hoare排序，区间被划分为[begin, keyi-1] U keyi U [keyi+1, end] ，单趟排序一次就会唯一确定一个元素来到最终排序所确定的位置；

• 先递归排序左子序列[begin, keyi-1] , 再递归排序右子序列[keyi+1, end]，类似二叉树前序遍历；

• 根据上图可得出递归终止条件为区间不存在(begin>end)或者只有一个元素(begin=end)

void QuickSort(int*a, int begin, int end)
{
	//递归终止的条件
	//1.区间不存在(begin>end)或者只有一个元素(begin=end)
	if (begin >= end)
		return;
	int keyi = PartSort3(a, begin, end);
	// 一趟排序原排序区间划分为如下三部分
	//[begin keyi-1]U[keyi]U[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

快排的优化

三数取中法选key

若选取的基准值key是序列中最大或最小的数值，则快速排序的递归深度会非常深，排序效率会很低；若是一个有序数组使用快速排序，则递归深度为n，单趟排序也为n，时间复杂度为O(n^2)；

假定待排序序列的左下标left , 右下标right，左右下标所对应的中间下标 midi=(left+right)/2,取三个下标所对应的值的中间值为基准值key，可以防止快排出现最差情形；

//三数取中法选keyi keyi为中间值的下标
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		//mid为最小值
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		//mid为最大值
		else if (a[left]>a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

小区间优化

由于快速排序是递归实现的，而每一次函数调用，均需要开辟函数栈帧，当递归到最后几层时，此时数组中的值其实已经接近有序，最后几层的函数调用会极大占用函数栈帧所开辟的空间；

假设数组大小N=10，即二叉树节点个数N=10；

10个数值，递归了3~4层，而最后三层占据比例为87.5%，调用函数的次数就越多，开辟函数栈帧的消耗越大，导致效率下降，代价太大，在递归分割过程中，当区间较小时，不再递归分割排序，序列在递归分割过程中，子序列已经接近有序，插入排序每一次单趟排序都只向前遍历到最大值之后，一共执行n次，若数组有序，则总共只执行n次，最差情况下每次都只是从i遍历到0下标，综合考虑是执行次数最优，故选择直接插入排序进行优化；

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// 小区间优化，小区间不再递归分割排序，降低递归次数
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}