不积跬步之冒泡排序及优化

冒泡排序

一句话描述：
相邻的两个元素相比较，大的那个移动到右侧，然后进行数组长度-1轮后，就排好序了。

//第一版：冒泡排序
function BubbleSort(array) {
        //第一个循环用来控制好轮数--n-1轮
        for (let i = 0; i < array.length - 1; i++) {
                
                for (let j = 0; j < array.length - i - 1; j++) {
                        let tmp = 0;
                        if (array[j] > array[j + 1]) {
                                tmp = array[j];
                                array[j] = array[j + 1];
                                array[j + 1] = tmp;
                        }
                }
                
        }
}

冒泡排序的优化一

有时候数组会有提前排好序的情况，而我们的程序还是按照既定的要求，进行了array.length-1次。

所以我们这次加了一个标识。来告诉我们，一旦程序已经提前排好，就结束轮回。

//第二版：冒泡排序--可以通过有序的标记来判断是否已经提前排好
function BubbleSort(array) {
        //第一个循环用来控制好轮数--n-1轮
        for (let i = 0; i < array.length - 1; i++) {
                //有序的标记，每一轮的初始值都是true
                let isSorted = true;
                for (let j = 0; j < array.length - i - 1; j++) {
                        let tmp = 0;
                        if (array[j] > array[j + 1]) {
                                tmp = array[j];
                                array[j] = array[j + 1];
                                array[j + 1] = tmp;
                                isSorted = false;
                        }
                }
                if (isSorted) {
                        break;
                }
        }
}

冒泡排序优化二

还有的数组是这种情况

[5,3,4,2,1,6,7,8,9]

可以看到我们的程序的后半段是有序的，但是程序并没有识别出来。所以我们需要给它做一个识别。

//第三版：冒泡排序--如果数组已经有一部分数组是排好序的，但是还是会轮训那么多次。

function BubbleSort(array){
        //记录最后一次交换的位置
        let lastExchangeIndex = 0;
        //无序数列的边界，每次比较只需要比到这里为止
        let sortBorder = array.length - 1;
        
        for(let i = 0; i<array.length - 1;i++){
                //有序标记，每一轮的初始值都是true
                let isSorted = true;
                for( let j = 0; j<sortBorder; j++){
                     let tmp = 0;
                     //判断是否大于下一位
                     if(array[j]>array[j+1]){
                          tmp = array[j];
                          array[j] = array[j+1];
                          array[j+1] = tmp;
                          
                          //因为有元素交换，所以不是有序的，标记变为false.
                          isSorted = false;
                          //更新为最后一次交换元素的位置
                          lastExchangeIndex = j;
                     }
                }
                //有序的边界更新
                sortBorder = lastExchangeIndex;
                if(isSorted){
                    break;
                }
        }
}

link