用js实现快排
栏目: JavaScript · 发布时间: 6年前
内容简介: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; }; 复制代码
由于我们是不断地重复找基准点,然后输出全小于基准点和全大于基准点的数组的这个步骤。我们希望用递归来实现,这样可以少写代码。
你可以随便找个基准点:第一个、中间、最后一个、随机一个。为了简单起见,我们假设基准点的选取对时间复杂度没有影响。我在本文中总是使用最后一个元素作为基准点,因为要配合下图的演示(图中用的是最后一个元素,来源维基百科)。
数组基于基准点分成两个数组:小于基准点的数组放前面,大于基准点的数组放后面。最终,把基准点放在两个数组的中间,重复以上步骤。
为了不改变原数据,我们创建了新数组。这不是必要的,但是是个好的习惯。
我们创建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本身现在是基准点,不再需要对其进行排序。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- php如何实现session,自己实现session,laravel如何实现session
- AOP如何实现及实现原理
- webpack 实现 HMR 及其实现原理
- Docker实现原理之 - OverlayFS实现原理
- 为什么实现 .NET 的 ICollection 集合时需要实现 SyncRoot 属性?如何正确实现这个属性?
- 自己实现集合框架(十):顺序栈的实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
C Primer Plus(第6版)中文版
普拉达 (Stephen Prata) / 姜佑 / 人民邮电出版社 / 2016-4-1 / CNY 89.00
《C Primer Plus(第6版)中文版》详细讲解了C语言的基本概念和编程技巧。 《C Primer Plus(第6版)中文版》共17章。第1、2章介绍了C语言编程的预备知识。第3~15章详细讲解了C语言的相关知识,包括数据类型、格式化输入/输出、运算符、表达式、语句、循环、字符输入和输出、函数、数组和指针、字符和字符串函数、内存管理、文件输入输出、结构、位操作等。第16章、17章介绍C......一起来看看 《C Primer Plus(第6版)中文版》 这本书的介绍吧!