快速排序和冒泡排序

目录

前言      

一.冒泡排序

二.快速排序

1.Hoare法

2.填空法

3.双指针法

4.快排优化(三数取中)

5.快排优化(递归优化)

6.快排优化(重复数据)

7.快排非递归

前言      

         排序算法是计算机科学中的基础工具之一，对于数据处理和算法设计有着深远的影响。了解不同排序算法的特性和适用场景，能够帮助程序员在特定情况下选择最合适的算法，从而提高程序的效率和性能。本节我们讲述两种交换排序。

一.冒泡排序

冒泡排序是交换排序的一种,在学习编程最初就接触过,这里不再过多叙述

时间复杂度 O(n^2)

空间复杂度 O(1)

稳定性:稳定

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n ; i++)
	{
		bool temp = true;
		for (int j = 0; j < n - 1-i ; j++)
		{
			if (a[j] > a[j+1])
			{
				Swap(&a[j], &a[j+1]);
				temp = false;
			}
		}
		if (temp)
			break;
	}
}

二.快速排序

        快速排序（Quick Sort）是一种常用的排序算法，它基于分治法的思想，通过将一个数组分成两个子数组，然后递归地对子数组进行排序。快速排序的主要步骤包括：

1. 选择基准元素： 从数组中选择一个元素作为基准（pivot）。通常选择数组中间的元素，但也可以选择第一个或最后一个元素。

2. 划分： 将数组中的其他元素按照比基准元素的大小分成两个部分，比基准元素小的放在左边，比基准元素大的放在右边。

3. 递归排序： 对左右两个子数组递归地应用快速排序算法。

4. 合并： 不需要显式的合并步骤，因为在划分过程中，数组已经被分成了两部分，左边的部分都比基准元素小，右边的部分都比基准元素大。

每趟排序都会将至少一个元素放到正确的位置

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

PartSort返回已经被放到正确位置的基准元素的下标

1.Hoare法

        先选定一个基准元素保存其值,使用两个指针.先从数组右边开始找比基准元素小的数,再从数组左边找比基准元素大的数交换它们，循环重复.直到两个指针相遇，那么这个位置就是这个基准元素最后确定的位置,再将基准元素放进去

int PartSort(int* a, int left, int right)
{
	int keyi = Getmind(a, left, right);
	Swap(&a[left], &a[keyi]);
	keyi = left;
	while (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;
}

2.填空法

        先选定一个基准元素保存其值,然后将其位置空出,先从数组右边开始找比基准元素小的数,将其值放入上个空出的位置,更新空位,再从数组左边找比基准元素大的数放入空位，更新空位,循环重复.直到两个指针相遇，这个位置就是基准元素最终的位置

int PartSort(int* a, int left, int right)
{
	int keyi = Getmind(a, left, right);
	int temp = a[keyi];
	Swap(&a[left], &a[keyi]);
	int bol=left;
	while (left < right)
	{
		while (left < right && a[right] >= temp)
			right--;
		a[bol] = a[right];
		bol = right;
		while (left < right && a[left] <= temp)
			left++;
		a[bol] = a[left];
		bol = left;
	}
	a[left] = temp;
	return left;
}

3.双指针法

         先选定一个基准元素保存其值,定义两个指针,一个从头开始,一个从后一个位置开始,如果当前位置比基准元素小,那么就让prav++,并交换两个指针指向的元素,然后让cur++,如果cur走完整个数组,这时prav的位置就是基准元素最终的位置

int PartSort(int* a, int left, int right)
{
	int keyi = Getmind(a,left,right);
	Swap(&a[left], &a[keyi]);
	keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

4.快排优化(三数取中)

        在选取基准元素时,如果基准元素是数组中最大的元素或者最小的元素,比如数组接近有序,那么快排的时间复杂度就是最坏情况,为了避免这种情况,我们需要选取合适的基准元素,所以就有了三数取中,即就是在数组头尾中选取一个即不是最大的也不是最小的的那个

int Getmind(int* a, int left, int right)
{
	int mind = (left + right) / 2;
	if (a[left] > a[mind]&&a[left]>a[right])
	{
		if (a[mind] > a[right])
			return mind;
		else
			return right;
	}
	if (a[right] > a[mind] && a[right] > a[left])
	{
		if (a[mind] > a[left])
			return mind;
		else
			return left;
	}
	if (a[mind] > a[left] && a[mind] > a[right])
	{
		if (a[left] > a[right])
			return left;
		else
			return right;
	}
}

5.快排优化(递归优化)

        快排是递归实现的,在处理小型数据时递归过多,所以在小型数据时我们使用其他排序如插入排序

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort1(a, begin, end);
	if (end - begin > 10)
	{
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
		InsertSort(a, end - begin + 1);

6.快排优化(重复数据)

        如果选取的基准元素在数组中重复多,这个优化就能将数组分为三个区域,一个区域是小于基准元素的,一个是等于基准元素但,一个是大于基准元素的,减少不必要的操作

void QSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = Getmind(a, begin, end);
	int key = a[keyi];
	int left = begin, right = end;
	int cur = begin + 1;
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			left++;
			cur++;
		}
		else if (a[cur] == key)
		{
			cur++;
		}
		else
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
	}
	if (end - begin > 10)
	{
		QuickSort(a, begin, left-1);
		QuickSort(a, right+1, end);
	}
	else
		InsertSort(a, end - begin + 1);
}

定义三个指针,

        如果当前位置小于基准元素,就交换left和cur指针元素的,left++,cur++,如果当前元素等于基准元素,则只cur++,其他情况就交换cur和righr位置的元素,right--,

通过这个操作使得数组分为三个区间

7.快排非递归

void QuickNonRSort(int* a, int begin, int end)
{
	Stack s;
	StackInit(&s);
	StackPush(&s, end);
	StackPush(&s, begin);
	while (!StackEmpty(&s))
	{
		int begin1 = StackTop(&s);
		StackPop(&s);
		int end1 = StackTop(&s);
		StackPop(&s);
		int keyi = PartSort1(a, begin1, end1);
		if (keyi - 1 > begin1)
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, begin1);
		}
		if (keyi + 1 < end1)
		{
			StackPush(&s, end1);
			StackPush(&s, keyi+1);
		}
	}
	StackDestroy(&s);
}

使用栈来实现,根据条件入区间即可