Open toFrankie opened 1 year ago
冒泡排序,是一个相对较为简单易于理解的排序算法。下面以升序为例。
array.length - 1
array.length - 1 - 1
array[length - 1 - 1]
// 冒泡排序(升序) function bubbleSort(arr) { for (let i = 0; i < arr.length - 1; i++) { for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] } } } return arr } const array = [8, 12, 4, 0, 22, 8, 21, 3, 56] console.log(bubbleSort(array)) // [0, 3, 4, 8, 8, 12, 21, 22, 56]
可知冒泡排序执行次数是 (n-1) + (n-2) + ... + 2 + 1 = (n^2 - n)/2,根据时间复杂度推导方式,可得到 O(n^2)。
(n-1) + (n-2) + ... + 2 + 1
(n^2 - n)/2
O(n^2)
冒泡排序,是一个相对较为简单易于理解的排序算法。下面以升序为例。
原理
array.length - 1
,一轮循环结束,数组最后一项应该是最大数。array.length - 1 - 1
,同样把本次循环的最大项互换到array[length - 1 - 1]
的位置上。图示
实现
时间复杂度
可知冒泡排序执行次数是
(n-1) + (n-2) + ... + 2 + 1
=(n^2 - n)/2
,根据时间复杂度推导方式,可得到O(n^2)
。