首页 > 代码库 > javascript实现快排

javascript实现快排

它的基本思想应该是将待排记录分成独立的两个部分,找出枢轴,实现枢轴左边的值都小于枢轴的值,枢轴右边都大于枢轴的值。这样子不断递归下去


function quicksort(arr,low,high){
        var pivot;
        if(low < high){
            pivot = partition(arr,low,high);
            quicksort(arr,low,pivot-1);
            quicksort(arr,pivot+1,high);
        }
        return arr;
    }

这个就是快排的入口函数,出现了partition方法。它的作用就是找出记录中的关键字,也就是枢轴


 function partition(arr,low,high){
 1.       var pivot = arr[low];
 2.       while(low <= high){
 3.           while(low <= high && arr[high] >= pivot){
 4.               high--;
 5.           }
 6.           swap(arr,low,high);
 7.           while(low <= high && arr[low] < pivot){
 8.               low++;
 9.           }
 10           swap(arr,low,high);
 11       }
 12       return low;
 13   }

其实它的思想也是挺简单的,比如你有这样一系列数字:5 1 9 3 7 4 8 6 2。我们这里只计算第一趟快排,其他只是递归下去,思路是一致的。

  1. 代码行1把数字列的第一个元素5作为为枢轴,跟最后一个元素2比较;
  2. 一比较不符合代码行3 arr[high] >= pivot。所以就执行交换两个位置的值;
  3. 现在的数字列为2 1 9 3 7 4 8 6 5
  4. 执行代码行7得出2 1都小于枢轴5继续循环,但是到了9时就不满足条件退出了循环。
  5. 执行交换后数字列为2 1 5 3 7 4 8 6 9
  6. 这个时候low为3 high为9 满足代码行2的循环条件继续按照前面步骤1~5执行
  7. 最后第一趟数字列为2 1 4 3 5 7 8 6 9
  8. 枢轴5的左边的值2 1 4 3都比它小,右边的值7 8 6 9都比它大

最后有一个函数就是交换函数的


 function swap(arr,low,high){
        var temp;
        temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

这个函数实现起来还是比较简单的

如果不太了解快排方法的人可以去看《大话数据结构》,写得浅显易懂。还有就是其实可以用闭包的方法封装partition和swap方法,就暴露出quicksort方法接口给外界就行了