快速排序算法 Java脚本
什么是快速排序?
快速排序 算法遵循分而治之的方法。它根据某些条件将元素分成更小的部分,然后对分成的较小部分执行排序操作。
快速排序算法是任何编程语言中最常用和最流行的算法之一。但是,如果你是一个 Java脚本开发人员,那么你可能听说过 种类() 现已推出 Java脚本。然后,你可能一直在想这个快速排序算法的必要性是什么。要理解这一点,首先我们需要了解什么是排序,什么是默认排序 Java脚本。
什么是排序?
排序就是按照我们想要的顺序排列元素。你可能在学校或大学时代就遇到过这种事情。就像我们到目前为止所见的从小到大(升序)或从大到小(降序)排列数字一样,这被称为排序。
默认排序 Java脚本
如前面提到的, Java脚本有 种类()。让我们举一个例子,其中有几个元素的数组,如 [5,3,7,6,2,9],并想按升序排列此数组元素。只需调用 种类() 在项目数组上,它按升序对数组元素进行排序。
代码:
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的 Firefox 和 Safari.
但是,如果你需要对大量元素进行排序,这种方法就不合适了。因此,解决方案是对大型数据集使用快速排序。
因此,为了完全理解,您需要了解快速排序的工作原理,现在让我们详细了解一下。
什么是快速排序?
快速排序如下 分而治之 算法。它根据某些条件将元素划分为较小的部分,并对这些划分的较小部分执行排序操作。因此,它适用于大型数据集。因此,以下是快速排序的简单步骤。
- 首先选择一个元素,称为 枢纽 元件。
- 接下来,将所有数组元素与选定的枢轴元素进行比较,并按以下方式排列它们:小于枢轴元素的元素在其左侧,大于枢轴元素的元素在其右侧。
- 最后对枢轴元素的左右两侧元素进行同样的操作。
这就是快速排序的基本概要。以下是执行快速排序需要逐一遵循的步骤。
快速排序如何工作
- 首先找到 “枢” 数组中的元素。
- 将左指针置于数组的第一个元素处。
- 将右指针置于数组的最后一个元素处。
- 比较指向左指针的元素,如果小于枢轴元素,则将左指针向右移动(左侧索引加 1)。继续此操作,直到左侧元素大于或等于枢轴元素。
- 将指向元素与右指针进行比较,如果其大于枢轴元素,则将右指针向左移动(右侧索引减 1)。继续此操作,直到右侧元素小于或等于枢轴元素。
- 检查左指针是否小于或等于右指针,然后交换这些指针位置上的元素。
- 增加左指针并减少右指针。
- 如果左指针的索引仍然小于右指针的索引,则重复该过程;否则返回左指针的索引。
那么,让我们通过一个例子来看一下这些步骤。假设我们需要排序的元素数组是 [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脚本
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; }
执行递归操作
执行上述步骤后,将返回左指针的索引,我们需要使用该索引来划分数组并对该部分执行快速排序。因此,它被称为分而治之算法。
因此,执行快速排序,直到左数组和右数组上的所有元素都排好序。
请注意: 快速排序在同一个数组上执行,并且在此过程中不会创建新的数组。
因此,我们需要调用这个 划分() 如上所述,并据此划分 排列 分成几部分。下面是使用它的代码,
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)。