冒泡排序算法是一种通过比较两个相邻元素来对数组进行排序的算法,如果它们没有按预期的顺序排列,则交换它们。这里的顺序可以是任何顺序,比如递增顺序或递减顺序。
冒泡排序原理
我们手上有一个未排序的数组 arr = [1, 4, 2, 5, -2, 3],任务是使用冒泡排序来对数组进行排序。
冒泡排序从索引 0 开始对比元素,如果第 0 个元素比第 1 个元素大则二者交换,否则什么都不做。
然后第 1 个索引对比第 2 个,第 2 个对比第 3 个,以此类推……
让我们看一个例子,每一步都会展示出来
每次迭代后,数组中最大的值会成为数组中的最后位置的元素。每次迭代中,对比过程会在到达最后未排序的元素时终止。
迭代和元素对比完成之后,我们就得到了一个排序后的数组。
句法
BubbleSort(array){
for i -> 0 to arrayLength
for j -> 0 to (arrayLength - i - 1)
if arr[j] > arr[j + 1]
swap(arr[j], arr[j + 1])
}
实现
// Bubble sort Implementation using Javascript
// Creating the bblSort function
function bblSort(arr) {
for(var i = 0; i < arr.length; i++) {
// Last i elements are already in place
for(var j = 0; j < ( arr.length - i -1 ); j++) {
// Checking if the item at present iteration
// is greater than the next iteration
if(arr[j] > arr[j+1]) {
// If the condition is true then swap them
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j+1] = temp
}
}
}
// Print the sorted array
console.log(arr);
}
// This is our unsorted array
var arr = [234, 43, 55, 63, 5, 6, 235, 547];
// Now pass this array to the bblSort() function
bblSort(arr);
//Output
//Sorted array :
//[5, 6, 43, 55, 63, 234, 235, 547]
注意:这种实现方式未经优化。接下来我们看一下优化后的版本。
优化后的方案
我们上面讨论的冒泡排序方案是未经优化的。即使数组是排序后的,代码的运行时间仍然是 �(�2) 复杂度。我们看一下如何在 JavaScript 中实现优化后的方案。
优化后的句法
BubbleSort(array){
for i -> 0 to arrayLength
isSwapped <- false
for j -> 0 to (arrayLength - i - 1)
if arr[j] > arr[j + 1]
swap(arr[j], arr[j + 1])
isSwapped -> true
}
具体实现
// Optimized implementation of bubble sort Algorithm
function bubbleSort(arr) {
var i, j;
var len = arr.length;
var isSwapped = false;
for(i =0; i < len; i++){
isSwapped = false;
for(j = 0; j < len; j++){
if(arr[j] > arr[j + 1]){
var temp = arr[j]
arr[j] = arr[j+1];
arr[j+1] = temp;
isSwapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if(!isSwapped){
break;
}
}
// Print the array
console.log(arr)
}
var arr = [243, 45, 23, 356, 3, 5346, 35, 5];
// calling the bubbleSort Function
bubbleSort(arr)
//Output
//Sorted Array :
//[3, 5, 23, 35, 45, 243, 356, 5346]