乐趣区

关于javascript:几种快速排序方法

// 100 万数据 在 260 ~ 270 ms 之间
function MySort(arr1) {
    // write code here
    function qsort(arr=[],l=0,r=arr.length-1){if(l<r){
            let pivot = l;
            let p = l+1;
            for(let i=l+1;i<=r;i++){if(arr[i]<arr[pivot]){[arr[i],arr[p]] = [arr[p],arr[i]];
                    p+=1;
                }
            }
            [arr[pivot],arr[p-1]] = [arr[p-1],arr[pivot]];
            qsort(arr,l,p-2);
            qsort(arr,p,r);
        }
        return arr;
    }
    return qsort(arr1);
}
// 100 万数据 在 280 ~ 330 ms 之间
var devide_Xin = function (array, start, end) {if(start >= end) return array;
        var baseIndex = Math.floor((start + end) / 2), // 基数索引
             i = start,
             j = end;

        while (i <= j) {while (array[i] < array[baseIndex]) {i++;}
            while (array[j] > array[baseIndex])  {j--;}

            if(i <= j) {var temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
        return i;
    }

    var quickSort_Xin = function (array, start, end) {if(array.length < 1) {return array;}
        var index = devide_Xin(array, start, end);
        if(start < index -1) {quickSort_Xin(array, start, index - 1);
        }
        if(end > index) {quickSort_Xin(array, index, end);
        }

        return array;
    }
// 100 万数据 在 430 ~ 450 ms 之间
arr.sort((a,b)=> a-b )
// 100 万数据 在 470 ~ 530 ms 之间
var quickSort = function(arr) {if (arr.length <= 1) {return arr;}
 
  var pivotIndex = Math.floor(arr.length / 2);
 
  var pivot = arr.splice(pivotIndex, 1)[0];
 
  var left = [];
 
  var right = [];
 
  for (var i = 0; i < arr.length; i++){if (arr[i] < pivot) {left.push(arr[i]);
 
    } else {right.push(arr[i]);
 
    }
 
  }
 
  return quickSort(left).concat([pivot], quickSort(right));
 
};
退出移动版