校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 快速排序
题目

使用js实现数组的快速排序

解答

快速排序使用了冒泡+分治的思路。

每轮从数组中取出一个数作为基准;在排序过程中,小于或等于基准数的全部放到基准的左边,大于基准的全部放右边;再对左边和右边依次进行上面两步,直到间距为1function partition(arr,low,high){

    var key = arr[low];  //使用第一个元素作为分类依据
while(low < high){
while(low < high && arr[high] >= arr[key])
high--;
if(low > high){
arr[low] = arr[high]; low++;
}
while(low < high && arr[low] <= arr[key])
low++;
if(low < high){
arr[high] = arr[low]; right--;}
}
arr[low] = key;
return low;
}
function qSort(arr,low,high){
if(low < high){
var partKey = partition(arr,low,high);
qSort(arr,low, partKey - 1);
qSort(arr,partKey + 1,high);
}
}


C 1条回复 评论
假期

排序快速快速

发表于 2021-02-06 23:49:59
0 0