快速排序 javascript实现

时间：2022-12-29 22:10:57

Quicksort（快速排序）

是由 东尼·霍尔 所发展的一种排序。

它比其他的Ο(n log n)算法更快，

因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。当然，本文是JavaScript实现。

算法

排序算法使用分治法 （Divide and conquer） 把一个序列（list）分为两个子序列（sub-lists）。

快速排序 javascript实现

步骤

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

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次迭代（iteration）中，它至少会把一个元素摆放到它最后的位置去。

代码

配合实现交换的swap的代码

 function swap(items,firstIndex,secondIndex){

     var temp = items[firstIndex];

     items[firstIndex] = items[secondIndex];

     items[secondIndex] = temp;

 }

分区（partition）操作

 function partition(items,left,right){

     var pivot = items[Math.floor((right+left) / 2)],

         i     = left,

         j     = right;

     while (i < j) {

         while(items[i] < pivot) {

             i++;

         }

         while (items[j] > pivot) {

             j--;

         }

         if (i <= j) {

             swap(items,i,j);

             i++;

             j--;

         }

     }

     return i;

 }

快排（使用递归）

 function quickSort(items,left,right) {

     var index;

     if (items.length > 1) {

         index = partition(items, left, right);

         if (left <index - 1) {

             quickSort(items, left, index - 1);

         }

         if (index < right) {

             quickSort(items, index, right);

         }

     }

     return items;

 }

小结一下

使用了快排，改变了原数组。如果你使用了上方的代码，要记得这点啊。。

解决的办法？

复制原数组？

是是是是（ 

相关文章