快速排序是效率较快,也是最常用的排序算法,其原理也非常的简单
(1)先在数组中找到一个比较值,一般采用中间值.
(2)此时,先定义一个一左一右的数组,遍历比较时如果比中间值小,就添加到左数组,比中间值大则添加到右数组.
(3)遍历数组,与中间值比较
(4)然后,再对左右两边的数组重复以上操作
(5)一直到不断被细分的数组的长度≤1的时候就返回数组
1.定义方法
function QuickSort(arr){
}
2.找到中间值,并且取出来,要做比较
function QuickSort(arr){
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//splice返回的是数组,用[0]返回值
}
3.再定义一左一右的数组,开始遍历
function QuickSort(arr){
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
var left=[],right=[];
for(var i=0;i<arr.length;i++){
}
}
4.如果比中间值小,就添加到左数组,比中间值大则添加到右数组.
function QuickSort(arr){
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
var left=[],right=[];
for(var i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
}
5.使用递归,再对左右两边的数组重复以上操作
function QuickSort(arr){
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
var left=[],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));
}
6.直到数组长度≤1的时候返回数组!注意!要在函数一开始就写上!
function QuickSort(arr){
if(arr.length≤1){return arr};
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
var left=[],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));
}
完工!
