冒泡排序
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
时间复杂度：O(n2)
排序实现
基础冒泡排序：双循环遍历
//遍历一
function bubbleSort(nums){
for(let i=0;i<nums.length;i++){
for(let j = i+1;j<nums.length;j++){
roll++;
if(nums[i]<nums[j]){
const temp = nums[i];
nums[i]=nums[j];
nums[j] = temp;
}
}
}
console.log(nums);
console.log(roll);
}
//遍历二
function bubbleSort(nums){
for(let i=0;i<nums.length;i++){
//每次遍历完之后右侧的一个数字就渐渐是有序的
for(let j = 0;j<nums.length-i-1;j++){
roll++;
if(nums[j]<nums[j+1]){
const temp = nums[j];
nums[j]=nums[j+1];
nums[j+1] = temp;
}
}
}
console.log(nums);
console.log(roll);
}
优化一：如果一轮循环结束了，没有进行任何交换动作，说明已经完全有序了，不需要再进行后续的循环了。
function bubbleSort(nums){
for(let i=0;i<nums.length;i++){
let isSort = true;
for(let j = 0;j<nums.length-i-1;j++){
roll++;
if(nums[j]<nums[j+1]){
const temp = nums[j];
nums[j]=nums[j+1];
nums[j+1] = temp;
isSort = false;
}
}
if(isSort){
break;
}
}
console.log(nums);
console.log(roll);
}
优化二：排序后判断已经有的有序数列的边界，有序部分数列的边界就是每次循环后，最后一次进行交换的标记。
- 对于像[6,1,3,4,5,6,7]这种后面有序的元素比较多的数列，可以减少循环数量。
function bubbleSort(nums){
let sortSize = nums.length - 1;
let lastSortIndex = 0;
for(let i=0;i<nums.length;i++){
let isSort = true;
for(let j = 0;j<sortSize;j++){
roll++;
if(nums[j]<nums[j+1]){
const temp = nums[j];
nums[j]=nums[j+1];
nums[j+1] = temp;
isSort = false;
lastSortIndex = j;
}
}
sortSize = lastSortIndex;
if(isSort){
break;
}
}
console.log(nums);
console.log(roll);
}
鸡尾酒排序:简单来说就是，每轮比较，从左到右一轮，再从右到左比较一轮。
- 它使用于当数列当中有序的元素数量比较多，可以有效减少循环次数。
function bubbleSort(nums){
let letfBorder = nums.length - 1;
let rightBorder = 0;
let leftSortIndex = 0;
let rightSortIndex = 0;
for(let i=0;i<nums.length/2;i++){
let isSort = true;
for(let j = i;j<letfBorder;j++){
roll++;
if(nums[j]> nums[j+1]){
const temp = nums[j];
nums[j]=nums[j+1];
nums[j+1] = temp;
isSort = false;
leftSortIndex = j;
}
}
if(isSort){
break;
}
letfBorder = leftSortIndex;
isSort = true;
for(let j = nums.length-i-1;j>rightBorder;j--){
roll++;
if(nums[j]< nums[j-1]){
const temp = nums[j];
nums[j]=nums[j-1];
nums[j-1] = temp;
isSort = false;
rightSortIndex = j;
}
}
if(isSort){
break;
}
rightBorder = rightSortIndex;
}
console.log(nums);
console.log(roll);
}
参考：《漫画算法：小灰的算法之旅》
