如何在JavaScript中实现快速排序?

快速分类

快速排序是javascript中最重要的排序方法之一。它从数组中获取枢轴值(随机值)。数组中的所有其他元素均分为两类,它们可能小于枢轴值且大于枢轴值。

之后,对每个类别(小于枢轴且大于枢轴)进行相同的过程,即选择枢轴,然后将每个类别划分为子类别(小于枢轴且大于枢轴) 。

最终,将子类别划分为这样的方式:如果没有更多要比较的元素,则子类别可以包含一个元素,也可以不包含任何元素。其余值将在以前的某些点处标记为枢轴,并且不会滴入该最低子类别。

示例

<html>
<body>
<script>
   function quickSort(originalArr) {
      if (originalArr.length <= 1) {
         return originalArr;
         } else {
               var leftArr = [];              
               var rightArr = [];
               var newArr = [];
               var pivot = originalArr.pop();      //  Take a pivot value
               var length = originalArr.length;
               for (var i = 0; i < length; i++) {
                  if (originalArr[i] <= pivot) {    // using pivot value start comparing
                     leftArr.push(originalArr[i]);      
               } else {
                       rightArr.push(originalArr[i]);
             }
           }
         return newArr.concat(quickSort(leftArr), pivot, quickSort(rightArr)); // array will be                                                                            //returned untill sorting occurs
      }
   }
   var myArray = [9, 0, 2, 7, -2, 6, 1 ];
   document.write("Original array: " + myArray);
   var sortedArray = quickSort(myArray);
   document.write("Sorted array: " + sortedArray);
</script>
</body>
</html>

输出

Original array: 9,0,2,7,-2,6,1
Sorted array: -2,0,1,2,6,7,9