冒泡排序、快速排序的区别与联系

您所在的位置：网站首页 › 冒泡排序怎么排序 › 冒泡排序、快速排序的区别与联系

冒泡排序、快速排序的区别与联系

2024-07-07 12:15| 来源: 网络整理| 查看: 265

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

算法对比冒泡排序快速排序平均时间复制度O(n^2)O(nlogn)最坏情况(时间)O(n^2)O(n^2)最好情况 (时间)O(n)O(nlogn)空间复杂度O(1)O(nlogn)属于稳定算法属于不属于

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

1、冒泡排序

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

vector BubbleSort(vector &list) { int tmp=0; int len = list.size(); for (int i = 0; i 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 &list, int left, int right) { int baseNum = list[left]; while (left

【本文地址】

冒泡排序、快速排序的区别与联系

冒泡排序、快速排序的区别与联系

今日新闻

推荐新闻