冒泡排序
它重復(fù)地走訪過要排序的元素列火脉，依次比較兩個(gè)相鄰的元素挥萌，如果順序（如從大到小叫胁、首字母從從Z到A）錯(cuò)誤就把他們交換過來斑响。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換菱属，也就是說該元素列已經(jīng)排序完成。
時(shí)間復(fù)雜度：O(n2)
排序?qū)崿F(xiàn)
基礎(chǔ)冒泡排序：雙循環(huán)遍歷
//遍歷一
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++){
//每次遍歷完之后右側(cè)的一個(gè)數(shù)字就漸漸是有序的
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);
}
優(yōu)化一：如果一輪循環(huán)結(jié)束了舰罚，沒有進(jìn)行任何交換動(dòng)作纽门，說明已經(jīng)完全有序了，不需要再進(jìn)行后續(xù)的循環(huán)了营罢。
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);
}
優(yōu)化二：排序后判斷已經(jīng)有的有序數(shù)列的邊界赏陵，有序部分?jǐn)?shù)列的邊界就是每次循環(huán)后，最后一次進(jìn)行交換的標(biāo)記饲漾。
- 對(duì)于像[6,1,3,4,5,6,7]這種后面有序的元素比較多的數(shù)列瘟滨，可以減少循環(huán)數(shù)量。
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);
}
雞尾酒排序:簡(jiǎn)單來說就是能颁，每輪比較杂瘸，從左到右一輪，再?gòu)挠业阶蟊容^一輪伙菊。
- 它使用于當(dāng)數(shù)列當(dāng)中有序的元素?cái)?shù)量比較多败玉，可以有效減少循環(huán)次數(shù)敌土。
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);
}
參考：《漫畫算法：小灰的算法之旅》
