如何在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