JS 算法学习：快速排序

一、感谢原创的指导

lio-mengxiang   # 每天一道前端面试题 #

二、快速排序简介（来自百科）

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法

1. 设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2. 以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3. 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5. 重复第3、4步，直到i=j (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

三、算法实现

        /**
         * 快速排序算法
         *
         * @method quickSort
         * param   array  {Array}    需要排序的数组
         * return  newArray {Array}  排序后的数组
         */
        function quickSort(array) {
            /**
             * 排序过程
             *
             * @method sort
             * param   prev  {Number}    选定的关键数据下标
             * return  numsize {Number}  数组长度
             */
            const sort = (arr, left = 0, right = arr.length - 1) => {
                if (left >= right) {//如果左边的索引大于等于右边的索引说明整理完毕
                    return;
                }
                let i = left;
                let j = right;
                const baseVal = arr[i]; // 取无序数组第一个数为基准值
                while (i < j) {
                    //把所有比基准值小的数放在左边大的数放在右边

                    while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
                        j--;
                    }

                    arr[i] = arr[j]; // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
                    while (i < j && arr[j] <= baseVal) { //找到一个比基准值大的数交换
                        i++;
                    }
                    arr[j] = arr[i]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
                }
                arr[j] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
                sort(arr, left, i) // 将左边的无序数组重复上面的操作
                sort(arr, i+ 1, right) // 将右边的无序数组重复上面的操作
            }
            const newArr = array.concat(); // 为了保证这个函数是纯函数拷贝一次数组
            sort(newArr);
            return newArr;
        }
        
        //调用示例
         var arr = [1, 2, 2, 1, 2, 34, 45, 12, 31, 21, 1];

        console.log(quickSort(arr))   //[1, 1, 1, 2, 2, 2, 12, 21, 31, 34, 45]
复制代码

四、面试题应用

给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数

        function oddEven(array) {
            let i = 0, j = array.length - 1;
            while (i < j) {

                if (array[i] % 2 === 0 && array[j] % 2 !== 0) {// 左偶右奇，直接交换，进入下一次循环
                    [array[i], array[j]] = [array[j], array[i]];
                    i++;
                    j--;
                }
                else if (array[i] % 2 === 0 && array[j] % 2 === 0) {// 左右都偶，不交换， 右边找第一个奇,
                    j--;
                }
                else if (array[i] % 2 !== 0 && array[j] % 2 !== 0) {// 左右都奇，不交换，左边找第一个偶,
                    i++;
                }
                else {
                    i++;
                    j--;
                }
            }
            return array;
        }
        //调用示例
        let arr = [1, 2, 2, 1, 2, 34, 45, 12, 31, 21, 1];
        console.log(oddEven(arr));// [1, 1, 21, 1, 31, 45, 34, 12, 2, 2, 2]
复制代码