快速排序算法
// 快速遍历
times = 0
function quickSort(array) {
function sort(prev, numsize) {
var nonius = prev;
var j = numsize - 1;
var flag = array[prev];
if ((numsize - prev) > 1) {
while (nonius < j) {
console.log('foreach time is :',++times);
for (; nonius < j; j--) {
if (array[j] < flag) {
array[nonius++] = array[j]; //a[i] = a[j]; i += 1;
break;
};
}
for (; nonius < j; nonius++) {
if (array[nonius] > flag) {
array[j--] = array[nonius];
break;
}
}
}
array[nonius] = flag;
sort(0, nonius);
sort(nonius + 1, numsize);
}
}
sort(0, array.length);
console.log(array)
return array;
}
var quickSort2=function(arr){
//如果数组长度小于等于1无需判断直接返回即可
if(arr.length<=1){
return arr;
}
var midIndex=Math.floor(arr.length/2);//取基准点
var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]
var left=[];//存放比基准点小的数组
var right=[];//存放比基准点大的数组
//遍历数组,进行判断分配
for(var i=0;i<arr.length;i++){
if(arr[i]<midIndexVal){
left.push(arr[i]);//比基准点小的放在左边数组
}
else{
right.push(arr[i]);//比基准点大的放在右边数组
}
console.log("第"+(++times)+"次排序后:"+arr);
}
//递归执行以上操作,对左右两个数组进行操作,直到数组长度为<=1;
return quickSort2(left).concat(midIndexVal,quickSort2(right));
};
dataArray = [2,5,4,1,7,3,8,6,9,0];
// quickSort(dataArray) // 循环85次,不浪费空间,但是遍历次数多,速度稍慢
console.log(quickSort2(dataArray)) //浪费空间,遍历次数少,速度快;