【排序】冒泡排序

冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从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);
}

参考：《漫画算法：小灰的算法之旅》