交换排序（冒泡/快排）

2024-11-04 07:01:30

一 . 交换排序

交换排序基本思想 :

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换序列的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

1.1 冒泡排序

在前面中， 介绍了冒泡排序的思路了 ， 冒泡排序是一种最基础的交换排序。 之所以叫做冒泡排序，因为每个元素都可以像小气泡一样，根据自身大小一点一点移动到对应的位置。其本质就是两两数值进行比较。

//冒泡排序
void BubbleSort(int* arr, int n)
{
	//比较的趟数
	for (int i = 0; i < n-1; i++)
	{
		int exchange = 0;
		//一趟中比较的次数
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

时间复杂度 : O（ n ^ 2 )

空间复杂度 : O （ 1 ）

1.2 快速排序

快速排序是Hoare 于1962 年提出的一种二叉树的交换排序方法， 其基本思想为：任取待排序元素中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列到相应的位置上。

快速排序实现的主框架：

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//找基准值
	int keyi = _QuickSort(arr, left, right);

	//二分查找
	// [0 , keyi -1 ]      keyi     [ keyi + 1 , right]
	QuickSort(arr, 0, keyi - 1);
	QuickSort(arr, keyi + 1 ,right);
}

将区域中的元素进行划分的 _QuickSort方法主要有以下几种实现方式 :

1.2.1 Hoare 版本

基本思路 :

1 ) 创建左右指针，以确定基准值

2 ) 左指针从左往右找比基准值要大的数据，右指针从右往左找比基准值要小的数据，然后左右指针数据交换，继续循环，直到左指针的下标值比右指针的大

3 ）当左指针的下标值比右指针的大时，基准值与右指针的数值交换

例如对数组 a [ ] = { 6 , 1 , 2 , 7 , 9 , 3 } 进行快速排序：

问题一：为什么跳出循环后right 位置的值一定不大于 key ?

因为在 left > right 时， right 走到了 left 的左侧，而再次之前 left 已经把最大的值找到并且与 right 交换 ( left 扫描过的数据均不大于key ) ;

相遇点的值有三种情况 :

问题二：为什么 left 和 right 指定的数据和 key 值相等时候也交换 ? （也就是以下代码加个 " = " 为啥不行）

相等的值参与交换确实会有一定额外的消耗。实际还有各种复杂的场景，假设数组中的数据大量重复的时候无法进行有效的分割排序！时间复杂度会变高！

时间复杂度分析 :

递归算法的时间复杂度的计算：递归次数 * 单次递归的时间复杂度

$\log_{2}n$ * n

快速排序的时间复杂度为： O(n*logn )

如果数组为有序 : 快排的时间复杂度为 O（n^2)

1.2.2 挖坑法

思路 :

创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入到左边坑中，当前位置变为新 “坑” ，然后从左向右找出比基准大的数据，找到后立即放入到右边坑中，当前位置变为新的 “坑” ，结束循环后将最开始存储的分界值放入到当前的 "坑“ 中，返回当前 ” 坑“ 下标（即分界值的下标）

//挖坑法
int _QuickSort1(int* arr, int left, int right)
{
	int key = arr[left];
	int hole = 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;
}

1.2.3 lomuto指针

创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

//双指针法
int _QuickSort2(int* arr, int left, int right)
{
	int prev = left, cur = prev + 1;
	int key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++prev !=cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[key]);
	return prev;
}

快速排序特性总结 :

1 . 时间复杂度 : O(n * logn)

2 . 空间复杂度：O（logn)

1.2.4 非递归版本

非递归版本的快速排序需要借助数据结构：栈

void QuickSortNonR(int* arr, int left, int right)
{
	ST st;
	STInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st))
	{
		//取栈顶元素——两次
		int begin = STTop(&st);
		StackPop(&st);

		int end = STTop(&st);
		StackPop(&st);

		//对区间[begin,end]找基准值---双指针法
		int prev = begin, cur = prev + 1;
		int keyi = begin;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)
			{
				Swap(&arr[prev], &arr[cur]);
			}
			++cur;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;
		//此时基准值的下标：keyi
		//划分左右序列:[begin,keyi-1] [keyi+1,end]
		if (keyi + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}

		if (keyi - 1 > begin)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}

	STDestory(&st);
}

码农公寓