快速排序

1.每一轮排序选择一个基准点进行分区
1.1 让小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区
1.2 当分区完成时，基准点元素的位置就是最终位置
2.在子分区内重置以上过程，直至子分区元素个数小于等于1。该算法提现的是分而治之的思想

一、单边循环快排（lomuto洛穆托分区方案）
1.选择最右边元素作为基准点元素
2.j指针负责找到比基准点小的元素，一旦找到则与i进行交换
3.i指针维护小于基准点元素的边界，也是每次交换的目标索引
4.最后基准点与i交换，i即为分区位置

         window.onload = function() {
              var arr = [2,4,9,1,7,3,6,8,5]
              // 快速排序
              quickSort(arr)
         }

        // 单边快排
        function partition1(arr, left, right) {
            var tmp = arr[right] // 取最右侧的为基准值
            var i = left

            for (let j = i; j < right; j++) {
                
                if (arr[j] < tmp) {
                    if (i != j) {
                        swap(arr, i, j)
                    }
                    i++
                }
                
            }

            if (i != right) {
                swap(arr, right, i)
            }

            return i
        }
      // 递归循环
        function quickSort1(arr, left, right){
            var start = left || 0
            var end = right != undefined ? right : arr.length - 1
            if (start < end) {
                // 进行一轮后基准值所在位置的索引
                var index = partition1(arr, start, end)
                // 进行左侧分区范围确定
                quickSort1(arr, start, index - 1)
                // 进行右侧分区范围确定
                quickSort1(arr, index + 1, end)
            }
        }
      // 交换两个值
        function swap(arr, i, j) {
            var tmp = arr[i]
            arr[i] = arr[j]
            arr[j] = tmp
        }

二、双边循环快排
1.选择最左边作为基准点元素
2.j指针负责从右向左找到比基准点小的元素，i指针负责从左向右找到比基准点大的元素，一旦找到二者交换，直到i、j相交
3.最后基准点与i（此时i与j相等）交换，i即为分区位置

         window.onload = function() {
              var arr = [2,4,9,1,7,3,6,8,5]
              // 快速排序
              quickSort(arr)
         }
        // 双边快速排序
        function partition(arr, left, right) {
            var tmp = arr[left] // 取左侧为基准值
            var i = left
            var j = right

            while (i < j) {
                // 先从右向左找小的
                while (i < j && arr[j] > tmp) {
                    j--
                }
                // 从右向左找大的
                while (i < j && arr[i] <= tmp) {
                    i++
                }
                // 交换大小值的位置,将小的放在左边,大的放在右边
                swap(arr, i, j)
            }
            // 将基准值填入坑里
            swap(arr, left, i)
            return i
        }

        function quickSort(arr, left, right) {
            var start = left || 0
            var end = right !== undefined ? right : arr.length - 1
            if (start < end) {
                // 进行一轮后基准值所在位置的索引
                var index = partition(arr, start, end)
                // 进行左侧分区范围确定
                quickSort(arr, start, index - 1)
                // 进行右侧分区范围确定
                quickSort(arr, index + 1, end)
            }
            console.log(arr)
            return arr
        }
        // 交换两个值
        function swap(arr, i, j) {
            var tmp = arr[i]
            arr[i] = arr[j]
            arr[j] = tmp
        }

双边循环的要点：
1.基准点取左边的值，并且要先右后左
2.while (i < j && arr[j] > tmp) j--
3.while (i < j && arr[i] <= tmp) i++