首页 > 代码库 > 冒泡排序之算法
冒泡排序之算法
一、定义
冒泡排序是一种基于比较的排序算法，每次比较，小数字在左，大数字在右。比较是相邻的两个元素比较，交换也发生在这两个元素之间，大数字经过交换会慢慢“浮”到最后面。
二、算法思想
依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍比较下来，能够保证最大（或最小）的数排在最后一位。
再对最后一位以外的数组，重复前面的过程，直至全部排序完成。
三、具体实现
因为有2层循环，所以有4种实现方式。
//交换元素function swap(arr,i,j){ var temp = arr[j]; arr[j] = arr[i]; arr[i] = temp;}
1、外循环正序遍历，内循环正序遍历，结果靠后的元素位置先确定。
function bubbleSort1(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0,stop = len - 1 - i; j < stop; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } } return arr;}console.log(bubbleSort1([3,5,9,2,11,6,3,5]));
2、外循环正序遍历，内循环逆序遍历，结果靠前的元素位置先确定。
function bubbleSort2(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = len - 1; j >= i+1; j--) { if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); } } } return arr;}console.log(bubbleSort2([3,5,9,2,11,6,3,5]));
3、外循环逆序遍历，内循环正序遍历，结果靠后的元素位置先确定。
function bubbleSort3(arr) { var len = arr.length; for (var i = len - 1; i >= 0; i--) { for (var j = 0; j < i; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } } return arr;}console.log(bubbleSort3([3,5,9,2,11,6,3,5]));
4、外循环逆序遍历，内循环逆序遍历，结果靠前的元素位置先确定。
function bubbleSort4(arr) { var len = arr.length; for (var i = len - 1; i >= 0; i--) { for (var j = len - 1; j >= len - 1 - i; j--) { if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); } } } return arr;}console.log(bubbleSort4([3,5,9,2,11,6,3,5]));
5、双向冒泡排序,鸡尾酒排序，内循环逆序遍历，结果靠前的元素位置先确定。
function bubbleSort5(arr) { var tail = arr.length -1; for (var i = 0; i < tail; tail--) { for (var j = tail; j > i; j--) {//第一轮, 先将最小的数据冒泡到前面 if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); } } i++; for (var j = i; j < tail; j++) {//第二轮, 将最大的数据冒泡到后面 if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } } return arr;}console.log(bubbleSort5([3,5,9,2,11,6,3,5]));
四、效率分析
由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
1、时间复杂度
最坏的情况：每次都需要交换,，共需遍历并交换将近n²/2次,，时间复杂度为O(n²)；
最佳的情况：内循环遍历一次后发现排序是对的， 因此退出循环，时间复杂度为O(n)；
平均来讲, 时间复杂度为O(n²)。
2、空间复杂度
由于冒泡排序中只有缓存的temp变量需要内存空间， 因此空间复杂度为常量O(1)。
冒泡排序之算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。