Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

快速排序

快速排序(Quick Sort)

快速排序,顾名思义是一种非常快的排序算法,该算法之所以非常快,是因为其高度优化的内部循环,目的就是快,效率高,是处理大数据最快的排序算法之一。

基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分小,则可以分别对这两部分继续进行排序,以达到整个序列有序。

算法描述:

  • 从数列中挑出一个元素,称为“基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以放到任意一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准元素的子数列和大于基准值元素的子数列排序。

JS 代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != "number" ? 0 : left,
right = typeof right != "number" ? len - 1 : right;

if (left < right) {
var x = arr[right],
i = left - 1,
temp;
for (var j = left; j <= right; j++) {
if (arr[j] <= x) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
return arr;
}
End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~