用js实现快排

栏目: JavaScript · 发布时间: 5年前

内容简介:Quicksort通过从数组中选取一个元素并将其表示为基准点,把数组中的所有其他元素分为两类 - 它们小于或大于此基准点。然后把作为这一轮排序结果的两个数组(数组元素都小于基准点的数组和数组元素都大于基准点的数组)再进行相同的排序。即分别再选个基准点,然后基于基准点分成两个数组元素分别小于和大于基准点的数组。最终,由于最后数组中没有元素或只有一个元素,因此不用再比较了。剩下的值都已经基于基准点排好序了。

Quicksort通过从数组中选取一个元素并将其表示为基准点,把数组中的所有其他元素分为两类 - 它们小于或大于此基准点。

然后把作为这一轮 排序 结果的两个数组(数组元素都小于基准点的数组和数组元素都大于基准点的数组)再进行相同的排序。即分别再选个基准点,然后基于基准点分成两个数组元素分别小于和大于基准点的数组。

最终,由于最后数组中没有元素或只有一个元素,因此不用再比较了。剩下的值都已经基于基准点排好序了。

(译者:内容有删减,说的有些啰嗦)

如何实现

js的Array原型的sort方法使用另外一种方法实现排序的,我们不用这个实现快排。我们自己创建一个方法,待排序的数组作为参数,输出排好序的数组。

const quickSort = (unsortedArray) => {
  const sortedArray = TODO(unsortedArray);
  return sortedArray;
};
复制代码

由于数组中项的“值”可能不是很明显,我们应该为 排序算法 提供一个可选参数。在js中,字符串和数字会排好序的,但是对象不会。我们要根据user对象的age字段给数组排序。

const defaultSortingAlgorithm = (a, b) => {
  if (a < b) {
    return -1;
  }
  if (b > a) {
    return 1;
  }
  return 0;
};

const quickSort = (
  unsortedArray,
  sortingAlgorithm = defaultSortingAlgorithm
) => {
  const sortedArray = TODO(unsortedArray);
  return sortedArray;
};
复制代码

由于我们是不断地重复找基准点,然后输出全小于基准点和全大于基准点的数组的这个步骤。我们希望用递归来实现,这样可以少写代码。

你可以随便找个基准点:第一个、中间、最后一个、随机一个。为了简单起见,我们假设基准点的选取对时间复杂度没有影响。我在本文中总是使用最后一个元素作为基准点,因为要配合下图的演示(图中用的是最后一个元素,来源维基百科)。

用js实现快排

数组基于基准点分成两个数组:小于基准点的数组放前面,大于基准点的数组放后面。最终,把基准点放在两个数组的中间,重复以上步骤。

为了不改变原数据,我们创建了新数组。这不是必要的,但是是个好的习惯。

我们创建recursiveSort作为递归函数,它将递归子数组(从起始索引到结束索引),中途改变sortedArray数组的数据。整个数组是第一个传递给此递归函数的数组。

最后,返回排好序的数组。

recursiveSort函数有一个pivotValue变量来表示我们的基准点,还有一个splitIndex变量来表示分隔小于和大于数组的索引。从概念上讲,所有小于基准点的值都将小于splitIndex,而所有大于基准点的值都将大于splitIndex。splitIndex被初始化为子数组的开头,但是当我们发现小于基准点时,我们将相应地调整splitIndex。

我们将循环遍历所有值,将小于基准点的值移动到起始索引之前。

const quickSort = (
  unsortedArray,
  sortingAlgorithm = defaultSortingAlgorithm
) => {

  // Create a sortable array to return.
  const sortedArray = [ ...unsortedArray ];

  // Recursively sort sub-arrays.
  const recursiveSort = (start, end) => {

    // If this sub-array contains less than 2 elements, it's sorted.
    if (end - start < 2) {
      return;
    }

    const pivotValue = sortedArray[end];
    let splitIndex = start;
    for (let i = start; i < end; i++) {
      const sort = sortingAlgorithm(sortedArray[i], pivotValue);

      // This value is less than the pivot value.
      if (sort === -1) {

        // If the element just to the right of the split index,
        //   isn't this element, swap them.
        if (splitIndex !== i) {
          const temp = sortedArray[splitIndex];
          sortedArray[splitIndex] = sortedArray[i];
          sortedArray[i] = temp;
        }

        // Move the split index to the right by one,
        //   denoting an increase in the less-than sub-array size.
        splitIndex++;
      }

      // Leave values that are greater than or equal to
      //   the pivot value where they are.
    }

    // Move the pivot value to between the split.
    sortedArray[end] = sortedArray[splitIndex];
    sortedArray[splitIndex] = pivotValue;

    // Recursively sort the less-than and greater-than arrays.
    recursiveSort(start, splitIndex - 1);
    recursiveSort(splitIndex + 1, end);
  };

  // Sort the entire array.
  recursiveSort(0, unsortedArray.length - 1);
  return sortedArray;
};
复制代码

我们将所有小于基准点的值移动到splitIndex指向的位置,其他的值不动(默认情况下,大于splitIndex,因为splitIndex从子数组的开头开始)。

一旦子数组被排序好后,我们将基准点放在中间,因为排序就是基于基准点排的,我们知道它的位置。

左边的所有值(从start到splitIndex - 1)都会被递归排序,并且右边的所有值(从splitIndex + 1到end)也都会被递归排序。 splitIndex本身现在是基准点,不再需要对其进行排序。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法小时代

算法小时代

Serge Abiteboul、Gilles Dowek / 任铁 / 人民邮电出版社 / 2017-10-1 / 39.00元

算法与人工智能是当下最热门的话题之一,技术大发展的同时也引发了令人忧心的技术和社会问题。本书生动介绍了算法的数学原理和性质,描述了算法单纯、本质的功能,分析了算法和人工智能对人类社会现状及未来发展的影响力及其成因。一起来看看 《算法小时代》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具