冒泡排序的时间复杂度:最好情况是“O(n)”,最坏情况是“O(n2)”。快速排序的的时间复杂度:最好情况是“O(nlogn)”,最坏情况是“O(n2)”。堆排序的时间复杂度是“O(nlogn)”。

本教程操作环境:windows7系统、Dell G3电脑。
冒泡排序(Bubble Sort)
时间复杂度
最好的情况:数组本身是顺序的,外层循环遍历一次就完成O(n)
最坏的情况:数组本身是逆序的,内外层遍历O(n2)
空间复杂度
开辟一个空间交换顺序O(1)
稳定性
稳定
,因为if判断不成立,就不会交换顺序,不会交换相同元素
冒泡排序它在所有排序算法中最简单。然而, 从运行时间的角度来看,冒泡排序是最差的一个,它的复杂度是O(n2)。
冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。
交换时,我们用一个中间值来存储某一交换项的值。其他排序法也会用到这个方法,因此我 们声明一个方法放置这段交换代码以便重用。使用ES6(ECMAScript 2015)**增强的对象属性——对象数组的解构赋值语法,**这个函数可以写成下面 这样:
1 | [ array [index1], array [index2]] = [ array [index2], array [index1]];
|
登录后复制
具体实现:
1 2 3 4 5 6 7 8 9 10 | function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
|
登录后复制
快速排序
时间复杂度
最好的情况:每一次base值都刚好平分整个数组,O(nlogn)
最坏的情况:每一次base值都是数组中的最大/最小值,O(n2)
空间复杂度
快速排序是递归的,需要借助栈来保存每一层递归的调用信息,所以空间复杂度和递归树的深度一致
最好的情况:每一次base值都刚好平分整个数组,递归树的深度O(logn)
最坏的情况:每一次base值都是数组中的最大/最小值,递归树的深度O(n)
稳定性
快速排序是不稳定
的,因为可能会交换相同的关键字。
快速排序是递归的,
特殊情况:left>right,直接退出。
步骤:
(1) 首先,从数组中选择中间一项作为主元base,一般取第一个值。
(2) 创建两个指针,左边一个指向数组第一个项,右边一个指向数组最后一个项。移动右指针直到找到一个比主元小的元素,接着,移动左指 针直到我们找到一个比主元大的元素,然后交 换它们,重复这个过程,直到左指针遇见了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。这一步叫作划分操作。
(3)然后交换主元和指针停下来的位置的元素(等于说是把这个元素归位,这个元素左边的都比他小,右边的都比他大,这个位置就是他最终的位置)
(4) 接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的 子数组)重复之前的两个步骤(递归方法),
递归的出口为left/right=i
,也就是:
此时,子数组数组已排序完成。
归位示意图:

具体实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | function quicksort(arr, left, right) {
if (left > right) {
return ;
}
var i = left,
j = right,
base = arr[left];
while (i != j) {
while (i < j && arr[j] >= base) {
j--;
}
while (i < j && arr[i] <= base) {
i++;
}
if (i < j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[left], arr[j]] = [arr[j], arr[left]];
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);
return arr;
}
|
登录后复制
参考:https://www.cnblogs.com/venoral/p/5180439.html
堆排序
堆的概念
- 堆是一个完全二叉树。
- 完全二叉树: 二叉树除开最后一层,其他层结点数都达到最大,最后一层的所有结点都集中在左边(左边结点排列满的情况下,右边才能缺失结点)。
- 大顶堆:根结点为最大值,每个结点的值大于或等于其孩子结点的值。
- 小顶堆:根结点为最小值,每个结点的值小于或等于其孩子结点的值。
- 堆的存储: 堆由数组来实现,相当于对二叉树做层序遍历。如下图:


时间复杂度
总时间为建堆时间
+n次调整堆
—— O(n)+O(nlogn)=O(nlogn)
建堆时间
:从最后一个非叶子节点遍历到根节点,复杂度为O(n)
n次调整堆
:每一次调整堆最长的路径是从树的根节点到叶子结点,也就是树的高度logn
,所以每一次调整时间复杂度是O(logn)
,一共是O(nlogn)
空间复杂度
堆排序只需要在交换元素的时候申请一个空间暂存元素,其他操作都是在原数组操作,空间复杂度为O(1)
稳定性
堆排序是不稳定
的,因为可能会交换相同的子结点。
步骤一:建堆
- 以升序遍历为例子,需要先将将初始二叉树转换成大顶堆,要求满足:
树中任一非叶子结点大于其左右孩子
。 - 实质上是调整数组元素的位置,不断比较,做交换操作。
- 找到第一个非叶子结点——
Math.floor(arr.length / 2 - 1)
,从后往前依次遍历 - 对每一个结点,检查结点和子结点的大小关系,调整成大根堆
1 2 3 4 5 6 7 | function buildHeap(arr) {
for (let i = Math. floor (arr.length / 2 - 1); i >= 0; i--) {
headAdjust(arr, i, arr.length);
}
}
|
登录后复制
步骤二:调整指定结点形成大根堆
- 建立
childMax
指针指向child最大值节点,初始值为2 * cur + 1
,指向左节点 - 当左节点存在时(左节点索引小于数组
length
),进入循环,递归调整所有节点位置,直到没有左节点
为止(cur
指向一个叶结点为止),跳出循环,遍历结束 - 每次循环,先判断右节点存在时,右节点是否大于左节点,是则改变childMax的指向
- 然后判断cur根节点是否大于childMax,
- 大于的话,说明满足大顶堆规律,不需要再调整,跳出循环,结束遍历
- 小于的话,说明不满足大顶堆规律,交换根节点和子结点,
- 因为交换了节点位置,子结点可能会不满足大顶堆顺序,所以还要判断子结点然后,改变
cur
和childMax
指向子结点,继续循环判断。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | function headAdjust(arr, cur, len) {
let intialCur = arr[cur];
let childMax = 2 * cur + 1;
while (childMax < len) {
if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
if (arr[childMax] < arr[cur]) break ;
swap(arr, childMax, cur);
cur = childMax;
childMax = 2 * cur + 1;
}
}
|
登录后复制
步骤三:利用堆进行排序
- 从后往前遍历大顶堆(数组),交换堆顶元素
a[0]
和当前元素a[i]
的位置,将最大值依次放入数组末尾。 - 每交换一次,就要重新调整一下堆,从根节点开始,调整
根节点~i-1
个节点(数组长度为i
),重新生成大顶堆


1 2 3 4 5 6 7 8 9 10 11 12 | function heapSort(arr) {
if (arr.length <= 1) return arr;
buildHeap(arr);
for (let i = arr.length - 1; i >= 0; i--) {
swap(arr, i, 0);
headAdjust(arr, 0, i);
}
return arr;
}
|
登录后复制
完整代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | function swap(a, i, j) {
[a[i], a[j]] = [a[j], a[i]];
}
function headAdjust(arr, cur, len) {
let intialCur = arr[cur];
let childMax = 2 * cur + 1;
while (childMax < len) {
if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
if (arr[childMax] < arr[cur]) break ;
swap(arr, childMax, cur);
cur = childMax;
childMax = 2 * cur + 1;
}
}
function buildHeap(arr) {
for (let i = Math. floor (arr.length / 2 - 1); i >= 0; i--) {
headAdjust(arr, i, arr.length);
}
}
function heapSort(arr) {
if (arr.length <= 1) return arr;
buildHeap(arr);
for (let i = arr.length - 1; i >= 0; i--) {
swap(arr, i, 0);
headAdjust(arr, 0, i);
}
return arr;
}
|
登录后复制
更多编程相关知识,请访问:编程视频!!
以上是冒泡排序、快速排序和堆排序的时间复杂度是多少的详细内容。更多信息请关注PHP中文网其他相关文章!