十大排序算法之冒泡排序、快速排序的介绍

目录

• 冒泡排序
• 快速排序

冒泡排序

说起来冒泡排序，是我们接触到的最早的一个排序算法了，这次就当进行一个巩固提升了。冒泡排序还被称为交换排序。
冒泡排序：

下面是冒泡排序的动态图：

冒泡排序特点：

冒泡排序代码

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

运行结果如下：

冒泡排序优化

我们知道冒泡排序的时间复杂度最坏情况是O(N^2)，最好情况依然是O(N^2)。所以我们对其进行一个优化：

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

如果我们冒泡完一趟以后，发现数组有序（即一次交换都没有发生），那么我们直接推出循环即可完成排序。
上面改进的冒泡排序最好的情况的时间复杂度是O(N)。

快速排序

快速排序使用的是分治策略把一个序列分为两个子序列。我们现在序列中选取一个元素作为基准值（或者称为关键值key），然后重新排序这个序列，如果是升序的话，所有比基准值大的元素放到基准值的右边，所有比基准值大的元素放在基准值的左边，经过此分区结束之后，然后对左右子序列重复此过程，直到所有元素出现在相对应的位置上。
其实简单来说就是选出一个基准值（一般选最左边或者最右边的），把这个基准值放到它所对应的位置上去。

下面是快速排序的动态图：

上图就是选取最左边的5作为基准值，然后比5大的元素放到5的右边，比5小的元素放到5的左边。最终5就会出现在其所对应的位置上。
举个例子：
现在我们来对数组{6,1,2,7,9,3,4,5,10,8}来进行排序。请看图解：

经过一次单趟排序后，上图中的6已经处于其对应的位置了，所以对于快速排序的单趟排序中，本质也是把一个元素排好。

快速排序代码

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

	int 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[left], &a[keyi]);
	keyi = left;

	//接下来进行递归
	//[begin , keyi - 1]  keyi  [keyi + 1 , end]   
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

运行结果如下：