快速排序算法 Java脚本

什么是快速排序?

快速排序 算法遵循分而治之的方法。它根据某些条件将元素分成更小的部分,然后对分成的较小部分执行排序操作。

快速排序算法是任何编程语言中最常用和最流行的算法之一。但是,如果你是一个 Java脚本开发人员,那么你可能听说过 种类() 现已推出 Java脚本。然后,你可能一直在想这个快速排序算法的必要性是什么。要理解这一点,首先我们需要了解什么是排序,什么是默认排序 Java脚本。

什么是排序?

排序就是按照我们想要的顺序排列元素。你可能在学校或大学时代就遇到过这种事情。就像我们到目前为止所见的从小到大(升序)或从大到小(降序)排列数字一样,这被称为排序。

默认排序 Java脚本

如前面提到的, Java脚本有 种类()。让我们举一个例子,其中有几个元素的数组,如 [5,3,7,6,2,9],并想按升序排列此数组元素。只需调用 种类() 在项目数组上,它按升序对数组元素进行排序。

默认排序 Java脚本

代码:

var items = [5,3,7,6,2,9];
console.log(items.sort());
//prints [2, 3, 5, 6, 7, 9]

为什么选择快速排序而不是默认排序() JavaScript

尽管 sort() 给出了我们想要的结果,但问题在于它对数组元素进行排序的方式。默认的 sort() 在 Java脚本用途 插入排序 by Chrome 的 V8 引擎合并排序 by Mozilla的 FirefoxSafari.

但是,如果你需要对大量元素进行排序,这种方法就不合适了。因此,解决方案是对大型数据集使用快速排序。

因此,为了完全理解,您需要了解快速排序的工作原理,现在让我们详细了解一下。

什么是快速排序?

快速排序如下 分而治之 算法。它根据某些条件将元素划分为较小的部分,并对这些划分的较小部分执行排序操作。因此,它适用于大型数据集。因此,以下是快速排序的简单步骤。

  1. 首先选择一个元素,称为 枢纽 元件。
  2. 接下来,将所有数组元素与选定的枢轴元素进行比较,并按以下方式排列它们:小于枢轴元素的元素在其左侧,大于枢轴元素的元素在其右侧。
  3. 最后对枢轴元素的左右两侧元素进行同样的操作。

这就是快速排序的基本概要。以下是执行快速排序需要逐一遵循的步骤。

快速排序如何工作

  1. 首先找到 “枢” 数组中的元素。
  2. 将左指针置于数组的第一个元素处。
  3. 将右指针置于数组的最后一个元素处。
  4. 比较指向左指针的元素,如果小于枢轴元素,则将左指针向右移动(左侧索引加 1)。继续此操作,直到左侧元素大于或等于枢轴元素。
  5. 将指向元素与右指针进行比较,如果其大于枢轴元素,则将右指针向左移动(右侧索引减 1)。继续此操作,直到右侧元素小于或等于枢轴元素。
  6. 检查左指针是否小于或等于右指针,然后交换这些指针位置上的元素。
  7. 增加左指针并减少右指针。
  8. 如果左指针的索引仍然小于右指针的索引,则重复该过程;否则返回左指针的索引。

快速排序如何工作

那么,让我们通过一个例子来看一下这些步骤。假设我们需要排序的元素数组是 [5,3,7,6,2,9]。

确定枢轴元素

但在进行快速排序之前,选择枢轴元素起着重要作用。如果选择第一个元素作为枢轴元素,那么它在排序数组中的表现最差。因此,始终建议选择中间元素(数组长度除以 2)作为枢轴元素,我们也这样做。

下面是执行快速排序的步骤,以 [5,3,7,6,2,9] 为例。

步骤1: 确定枢轴为中间元素。因此, 7 是枢轴元素。

步骤2: 将左指针和右指针分别作为数组的第一个和最后一个元素。因此,左指针指向 5 在索引 0 处,右指针指向 9 位于索引 5。

步骤3: 将左指针处的元素与枢轴元素进行比较。由于 5 < 6,因此将左指针向右移至索引 1。

步骤4: 现在,仍然 3 < 6,因此将左指针向右移动一个索引。因此现在 7 > 6 停止增加左指针,现在左指针位于索引 2。

步骤5: 现在,将右指针的值与枢轴元素进行比较。由于 9 > 6,因此将右指针向左移动。现在,由于 2 < 6,因此停止移动右指针。

步骤6: 将左指针和右指针处的值相互交换。

步骤7: 将两个指针再移动一步。

步骤8: 由于 6 = 6,将指针再移动一步,并在左指针越过右指针时停止并返回左指针的索引。

因此,基于上述方法,我们需要编写代码来交换元素并对数组进行分区,如上述步骤中所述。

交换两个数字的代码 Java脚本

交换两个数字 Java脚本

function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

按照上述步骤执行分区的代码

执行分区的代码

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

执行递归操作

执行上述步骤后,将返回左指针的索引,我们需要使用该索引来划分数组并对该部分执行快速排序。因此,它被称为分而治之算法。

因此,执行快速排序,直到左数组和右数组上的所有元素都排好序。

请注意: 快速排序在同一个数组上执行,并且在此过程中不会创建新的数组。

因此,我们需要调用这个 划分() 如上所述,并据此划分 排列 分成几部分。下面是使用它的代码,

递归 OperaTION

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var result = quickSort(items, 0, items.length - 1);

完整的快速排序代码

var items = [5,3,7,6,2,9];
function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

快速排序

注意: 快速排序的时间复杂度为 O(nlogn)。