快速排序(一)
文章目录
对数组进行快速排序
中心思想:
假定以数组的第一个值为中心值,将数组中比中心值小的数值放在中心值左边,将数组中比中心值大的数值放在中心值右边,这样就将数组分成了两个部分,再将这两部分分别套进前面的逻辑中,完成递归操作,这样确保左边的值一定比右边的值小(或者相等),完成排序。
二分partation 算法:(将数组分为两部分)
`
function partation(arr){
let midValue = arr[0];//设定数组第一个值为中心值
let leftIndex = 0;//左边值索引
let rightIndex = arr.length-1;//右边值索引
let leftValue = arr[leftIndex];//左边值
let rightVlaue = arr[rightIndex];//右边值
while(leftIndex < rightIndex){
leftValue = arr[leftIndex];
rightValue = arr[rightIndex];
while(rightValue >= midValue && rightIndex > leftIndex){
rightIndex--;
rigthValue = arr[rightIndex];
}//找出右边比中间值小的数
while(leftValue <= midValue && leftIndex < rightIndex){
leftIndex++;
leftValue = arr[leftIndex];
}//找出左边比中间值大的数
//对找出的数进行交换
let temp = arr[rightIndex];
arr[rightIndex] = arr[leftIndex];
arr[leftIndex] = temp;
}
//交换过一轮之后,将最后rightIndex所指向的值与中间值(数组第一个值)进行交换
let temp = arr[0];
arr[0] = arr[rightIndex];
arr[rightIndex] = temp;
return rightIndex;//返回中间值最后交换后所在的位置
}
`
通过递归调用partation算法,完成排序
`
function quicksort(arr){
if(arr.length<2){
return arr;//如果数组长度小于2 无需排序直接返回
}else{
let midIndex=partation(arr);
return quicksort(arr.slice(0,midIndex)).concat(arr[midIndex]).concat(quicksort(arr.slice(midIndex+1)));
}
}
`
执行:
`
console.log(quicksort(list));
`
排序完成后,会返回一个新的完成排序的数组
缺点:在排序过程中会生成很多新的数组,占用空间
在本数组中进行排序,节省空间
`
function partation(arr, start, end){
let midValue = arr[start];//确定中间值
let rightIndex = start;//左边索引
let rightIndex = end;//右边索引
let leftValue = arr[leftIndex];//左边值
let rightValue = arr[rightIndex];//右边值
while(rightIndex > rightIndex){
leftValue = arr[rightIndex];
rightValue = arr[rightIndex];
while(rightValue >= midValue && rightIndex > leftIndex){
rightIndex--; rightValue = arr[rightIndex];
}
while(leftValue <= midValue && leftIndex<rightIndex){
leftIndex++; leftValue = arr[leftIndex];
}
let temp = arr[leftIndex];
arr[leftIndex] = arr[rightIndex];
arr[rightIndex] = temp;
}
let temp = arr[rightIndex];
arr[rightIndex] = arr[start];
arr[start] = temp;
//console.log(arr);
return rightIndex;
}
`
通过递归对本数组进行操作
`
function quicksort(list, start, end){
if(end-start < 2){
return ;
}else{
let midIndex = partation(list, start, end);
quicksort(list, start, midIndex);
quicksort(list, midIndex+1, end);
}
}
`
执行:
`
quicksort(list,0,list.length-1);
console.log(list);
`
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论