[数据结构与算法]冒泡排序、快速排序的区别与联系

? ? 在数据结构中，冒泡排序和快速排序，都属于交换排序，即两两比较待排序的关键字，交换不满足次序的那些偶对，直到整个序列满足从小到大或从大到小的次序为止。其时间复杂度、空间复制度、稳定性的对比如下：

? ? 当初始数据越接近有序时，推荐使用冒泡排序，这时候的时间复度接近于O(n)；当初始数据越接近无序时，推荐使用快速排序，这时候的时间复制度接近于O(nlogn)。

1、冒泡排序

? ? 基本思路：通过无序区中相邻关键字的比较与位置交换，使得关键字较小的记录如同气泡一般逐渐往上"漂浮"，直到"水面"。整个算法是从最下面的记录开始，对每两个相邻记录的关键字进行比较，让关键字较小的记录换到关键字较大的记录位置之上，使得经过一趟冒泡排序后，关键字最小的记录换到最顶端位置。接着，在剩下的记录中寻找次小的记录，把它换到第二个位置上，依次类推，直到该数组变成有序为止。冒泡排序的平均时间复制度为O(n^2)。
//冒泡排序代码BubbleSort:

vector<int> BubbleSort(vector<int> &list) {
	int tmp=0;
	int len = list.size();
	for (int i = 0; i < len; i++){
		for (int j = len - 1; j > i; j--) {
			if (list[j-1] > list[j]) {
				tmp = list[j - 1];
				list[j - 1] = list[j];
				list[j] = tmp;
			}
		}
	}

	return list;
}

2、快速排序

? ? 基本思路：快速是一种改进的冒泡排序，采用了分而治之的思想。它从待排序的n个记录中任取一记录(通常为第一个记录)作为基准，把该记录放入最终位置后，整个数据区间被基准分隔为2个子区间。比基准小的数据，都放在左子区间；比基准大的数据，都放在右子区间，称为一趟快排。之后，对这2个子区间，重复之前的分隔操作，直到每个区间只剩一个数据为止。在快速排序中，每一趟排序，都有一个元素找到自己的最终位置，即n个数据，最多进行n趟快排，就可以实现有序。快排的平均时间复制度为O(nlogn)。
//快排源码

/------------ quick sort -------
int division(vector<int> &list, int left, int right) {
	int baseNum = list[left];
	while (left < right)
	{
		while (left < right && list[right] >= baseNum) //从右往左找，找到第一个小于baseNum的值
			right = right - 1;
		list[left] = list[right];

		while (left < right && list[left] <= baseNum) //从左往右找，找到第一个大于baseNum的值
			left = left + 1;
		list[right] = list[left];
	}

	//找到baseNum存放的位置
	list[left] = baseNum;

	return left;
}

void QuickSort(vector<int> &list, int left, int right) {
	if (left < right)
	{
		int i = division(list, left, right);
		QuickSort(list, left, i - 1);
		QuickSort(list, i + 1, right);
	}
}

3、完整代码

//swapsort.cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> BubbleSort(vector<int> &list) {
	int tmp=0;
	int len = list.size();
	for (int i = 0; i < len; i++){
		for (int j = len - 1; j > i; j--) {
			if (list[j-1] > list[j]) {
				tmp = list[j - 1];
				list[j - 1] = list[j];
				list[j] = tmp;
			}
		}
	}

	return list;
}

//------------ quick sort -------
int division(vector<int> &list, int left, int right) {
	int baseNum = list[left];
	while (left < right)
	{
		while (left < right && list[right] >= baseNum) //从右往左找，找到第一个小于baseNum的值
			right = right - 1;
		list[left] = list[right];

		while (left < right && list[left] <= baseNum) //从左往右找，找到第一个大于baseNum的值
			left = left + 1;
		list[right] = list[left];
	}

	//找到baseNum存放的位置
	list[left] = baseNum;

	return left;
}

void QuickSort(vector<int> &list, int left, int right) {
	if (left < right)
	{
		int i = division(list, left, right);
		QuickSort(list, left, i - 1);
		QuickSort(list, i + 1, right);
	}
}


void printList(vector<int> list){
	for (int i = 0; i < list.size(); i++){
		printf("%d ", list[i]);
		if ((i + 1) % 5 == 0)
			printf("\n");
	}
	printf("\n");
}

int main() {
	int arry[5] = { 20, 40, 50, 10, 60 };
	vector<int> dataVec(arry, arry + 5);
	//vector<int> data2 = BubbleSort(dataVec);
	//printList(data2);

	//1)冒泡排序
	//BubbleSort(dataVec);
	//printList(dataVec);

	//2)快速排序
	QuickSort(dataVec, 0, dataVec.size() - 1);
	printList(dataVec);

	system("pause");
	return 0;
}

4、 参考文献

? ? 李春葆.数据结构习题与解析B级.2006
? ? 一线码农.算法系列.七大经典排序.2011