排序算法

一、冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”

        let arr = [1, 2, 4, 5, 1, 2, 7, 8, 10, 115, 111, 4, 8];
        
        let len = arr.length;

        //  第一个循环确定要排几次
        for (let i = 0; i < len - 1; i++) {
            //  第二个循环确定每一排交换的次数
            //  大于是升序，小于是降序
            for (let j = len - 1; j > i; j--) {
                if (arr[j] > arr[j - 1]) {
                    [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
                }
            } 
        }

        console.log(arr);

冒泡排序算法的原理如下：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

二、选择排序

          let arr = [5, 3, 45, 78, 2, 84, 110, 548, 45, 54, 1, 3, 5];
        /*
            未排序
            [3, 1, 45, 78, 4, 84, 110, 548, 45, 54, 1, 3, 5];

        */
        for (let i = 0; i < arr.length - 1; i++) {

            //  第一次循环已排序默认第一个，以此跟该数后面进行比较，如果有最小值就替换当前数字
            let minIndex = i;
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            //  交换位置，最小值排在该数组的最后面
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
        }

        console.log(arr)

三、插入排序

举个生活中的例子，我们平时打扑克牌的时候，习惯性的按照点数的大小进行排序，我们先看到一个牌，然后需要把这个牌和这个牌所在位置的前面所有位置的牌进行一个对比，插入到他能插入的最前面位置。

位置n需要和0~n-1位置的所有的元素进行比较，比较的方式是倒序，也就是先和n-1比较，如果n比n-1小，则互换位置，来到n-1的位置，然后n-1和n-2比，一直比到大于等于即可。（因为前面的元素是排序好的，所以比较一遍即可）

插入算法是初始默认已排序是第一个，每次都是后面未排序的跟已排序的进行比较，如果符合条件就

        let arr = [3, 5, 1, 78, 78, 84, 110, 548, 45, 54, 1, 3, 5];

        for (var i = 1; i < arr.length; i++) {  //  未排序
            let value = arr[i];
            for (var j = i - 1; j >= 0; j--) {  //  已排序
                //  已排序 > 未排序 
                if (arr[j] > value) {
                    //  后移一位
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = value;
        }
        console.log(arr)
 

四、随机排序

        let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let len = arr.length;

        let random = (first, second, self) => {
            //  获取区间
            let num = Math.floor(Math.random() * (second - first + 1) + first);

            //  随机的值跟随机区间值相同 再随机一次，否则，输出随机区间值
            return self === num ? random(first, second, self) : num;
        }

        for (let i = 0; i < len * 3; i++) {
            //  随机的序号
            let idx = i % len;

            //  除了idx之外的随机序号
            let a = random(0, len - 1, idx);

            //  交换位置
            [arr[idx], arr[a]] = [arr[a], arr[idx]];
        }
        
        console.log(arr)

        let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let len = arr.length;

        let random = (first, second, self) => {
            //  获取区间
            let num = Math.floor(Math.random() * (second - first + 1) + first);
            
            //  随机的值跟随机区间值相同 再随机一次，否则，输出随机区间值
            return self === num ? random(first, second, self) : num;
        }

        for (let i = 0; i < len * 3; i++) {
            //  随机的序号
            let idx = i % len;

            //  除了idx之外的随机序号
            let a = random(0, len - 1, idx);

            //  交换位置
            [arr[idx], arr[a]] = [arr[a], arr[idx]];

            let b = len - 1 - idx;

            [arr[b], arr[a]] = [arr[a], arr[b]];

        }

        /*
            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

            0       0, len - 1 - 0  
            1       0, len - 1 - 1  
            2       0, len - 1 - 0  
        */
        console.log(arr)