关于JavaScript中的排序问题
前言
本篇文章将总结常用的几种排序算法,并对其进行详细分析理解,以解决问题为驱动,分析其的各个应用场景,为之后排序类算法刷题打下基础,达到能根据各排序算法的特性,结合题目场景能迅速选择相应排序方法的效果。着重强调——最后的的归并排序和快速排序非常重要。
1. 先出一道排序题
题目:leetcode:912. 排序数组
难度:中等
描述:给你一个整数数组 nums
,请你将该数组升序排列。
示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]
示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]
提示:1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
在第三章将用各种排序方法解题,对比分析。
2.分析指标简单介绍
a. 时间复杂度分析
一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。把算法中基本操作重复执行的次数(频度)作为算法的时间复杂度。
简单理解的说,就是没有循环语句,记作O(1)
,也称为常数阶。只有一重循环(循环的次数不确定),则算法的基本操作的执行频度与问题规模n
呈线性增大关系,记作O(n)
,也叫线性阶
常见的时间复杂度有:O(1)
: 常量级时间复杂度
//示例
let i=1;
let j==2;
let sum=i+j;//就算有三行依旧是O(1)
O(log n)
: 对数阶时间复杂度,O(nlog n)
: 线性对数阶时间复杂度
i=1;
while (i <= n)
{
i = i * 2;//ax =N(a>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN
//不管以什么数为底,时间复杂度都是O(logN)
}
如果一段代码的时间复杂度是 O(logn),我们循环执行 n 遍,时间复杂度就是 O(nlogn) 了。O(nlogn) 也是一种非常常见的算法时间复杂度。比如,归并排序、快速排序的时间复杂度都是 O(nlogn)。
O(n)
:线性阶时间复杂度,O(n^2)
: 平⽅阶时间复杂度,O(n^3)
: 立方阶时间复杂度,O(n^k)
: k次方阶时间复杂度
简单的说就算,一重循环就算O(n),二重循环就算O(n^2),以此类推,这样理解
O(2^n)
:指数阶时间复杂度O(n!)
:阶乘阶时间复杂度
时间复杂度不用了解太多,我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )。
b. 空间复杂度分析
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。
let arr=new Array(n);//空间复杂度为O(n)
一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
c. 稳定性分析
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。
简单例子:条件nums[i]<nums[j]时换位置排序是稳定的,条件变为nums[i]<=nums[j]就不是稳定的了。
一般情况下只是对于某个数值属性进行排序,相同属性的两个其顺序是否改变,没有任何意义,对时间复杂度的影响也不会很大。(灵魂拷问)
稳定性的主要意义在于:
举个例子:一个班的学生已经按照学号大小排好序了,我现在要求按照年龄从小到大再排个序,如果年龄相同的,必须按照学号从小到大的顺序排列。那么问题来了,你选择的年龄排序方法如果是不稳定的,是不是排序完了后年龄相同的一组学生学号就乱了,你就得把这组年龄相同的学生再按照学号排一遍。如果是稳定的排序算法,我就只需要按照年龄排一遍就好了。
从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。要排序的内容是一个复杂对象的多个数字属性,且其原本的初始顺序存在意义,那么我们需要在二次排序的基础上保持原有排序的意义,才需要使用到稳定性的算法。
场景:淘宝网的商品进行排序,按照销量,价格等条件进行排序,它的数据服务器中的数据非常多,因此,当时用一个稳定性效果不好的排序算法,如堆排序、shell排序,当遇到最坏情形,会使得排序的效果非常差,严重影响服务器的性能,影响到用户的体验。
3. 各排序方法解题
a. 插入排序
上代码:
//使用插入排序 双for o(n^2)
var sortArray = function(nums) {
for(let i=1;i<nums.length;i++){//从第二张牌开始,向左比较
let target=i;
for(let j=i-1;j>=0;j--){//i在j前,j是当前nums[i]的左边待比较插入部分
if(nums[target]<nums[j]){//符合规则,当前元素向前插入。
[nums[target],nums[j]]= [nums[j],nums[target]];
//解构赋值,快速换位置
target=j;
}else{
//因为左边部分是排好序的,所以遇到比自己小的后,
//再左也是比自己小的,当前元素找到自己位置,可以退出,进行下一元素插入
break;
}
}
}
return nums;
};
排序流程介绍:
我举一个例子,插入排序就像是玩扑克牌,展开一副牌,为其排序,从第二张开始,将其从右向左逐步进行比对,直到找到它该处于的符合排序规则的位置,然后插入。
插入排序就是这样,如上面代码描述,每个数值都向左比较,当遇到比起小的就互换位置,然后继续向左比较,符合规律互换位置,直到最左,这就保证了当前元素的左边一直都是排序好的,那么当元素比较到比自己小的位置时就可以停止比较,进行下一数值的插入排序。总结就是:通过正确地定位当前元素在有序序列里的位置、不断扩大有序数组的范围,最终达到完全排序的目的
。
leetcode提交结果分析:
排序分析:
时间复杂度:O(n2)
空间复杂度:O(1)
稳定性: 稳定
b. 冒泡排序
上代码:
var sortArray = function(nums) {
let len=nums.length;
// 缓存数组长度,避免一直计算,浪费性能
for(let i=0;i<len;i++){
//冒泡是进行len次,每次都是从第一个开始往右冒泡。
for(let j=0;j<len-1;j++){
if(nums[j]>nums[j+1]){
[nums[j],nums[j+1]]=[nums[j+1],nums[j]];
}
}
}
return nums;
};
排序流程介绍:冒泡算法非常容易理解,代码也是很易懂,就是数组有多少个元素就冒多少个泡,每次都都是从最左的那个冒泡,一直往右比较。比右边的元素大,就交换位置,相当于冒泡了一个距离,遇到比自己大的元素,就由右边的大元素接下接力棒,继续往右冒泡,直到最右。
leetcode提交结果分析:
想一想,如果一个数组长度为5,其冒了3次泡后就把序排好了,它还继续冒剩下的两次泡,是不是很多余?非常多余,我们应该优化一下。
// 优化代码,提前排好序就不再冒泡
var sortArray = function(nums) {
let len=nums.length;
// 缓存数组长度,避免一直计算,浪费性能
for(let i=0;i<len;i++){
let complete=true;
//优化,用于判断上一次是否发生过交换顺序,以判断是否排好序
//冒泡是进行len次,每次都是从第一个开始往右冒泡。
for(let j=0;j<len-1;j++){
if(nums[j]>nums[j+1]){
[nums[j],nums[j+1]]=[nums[j+1],nums[j]];
complete=false;
}
}
//提前排好序就退出循环,提前结束
if(complete){
break;
}
}
return nums;
};
再想一想,每冒一次泡,最大的就会靠到最右边,冒第二次泡,第二大的就会排到右边第二的位置,这右边的n个就算排好序的了,那么后面冒泡还有必要再管这几个吗?没有必要了。我们再优化一次吧!
// 优化代码,提前排好序就不再冒泡,且不再管排好序的后n个
var sortArray = function(nums) {
let len=nums.length;
// 缓存数组长度,避免一直计算,浪费性能
for(let i=0;i<len;i++){
let complete=true;
//优化,用于判断上一次是否发生过交换顺序,以判断是否排好序
//冒泡是进行len次,每次都是从第一个开始往右冒泡。
for(let j=0;j<len-1-i;j++){
//这里的内循环里条件改变,即完成了忽略后面排好序的i个元素,不再去比较
if(nums[j]>nums[j+1]){
[nums[j],nums[j+1]]=[nums[j+1],nums[j]];
complete=false;
}
}
//提前排好序就退出循环,提前结束
if(complete){
break;
}
}
return nums;
};
经过两次优化,可以发现花费时间少了很多。
排序分析:
时间复杂度:O(n2)
空间复杂度:O(1)
稳定性: 稳定
c. 选择排序
上代码:
//选择排序
var sortArray = function(nums) {
let len=nums.length;
for(let i=0;i<len-1;i++){
//外循环决定着范围的变化,范围由[0,len]到[1,len]到...再到[len-1,len]
//范围逐步缩小,每次都是找出最小的放在当前范围的头部
let minIndex=i;
for(let j=i+1;j<len;j++){
//找出最小值的位置
if(nums[minIndex]>nums[j]){
minIndex=j;
}
}
[nums[i],nums[minIndex]]=[nums[minIndex],nums[i]];
}
return nums;
};
排序流程介绍:选择排序的关键字是最小值
:循环遍历数组,每次都找出当前范围(范围由[0,array.length]到[1,array.length]到[2,array.length]...直到最小范围[array.length-1,array.length],就这样的规律一直缩小范围
)内的最小值,把它放在当前范围的头部;然后缩小排序范围(范围外的就是排好序的数),继续重复以上操作,直至数组完全有序为止。
leetcode提交结果分析:
排序分析:
时间复杂度:O(n2)
空间复杂度:O(1)
稳定性: 不稳定(举个例子,序列6 8 6 2 9,我们知道第一遍选择第1个元素6会和2交换,那么原序列中2个6的相对前后顺序就被破坏了,故不稳定)
上面的a,b,c三种排序的时间效率很低,但不要失望,就认为两个排序算法都是对“分治”思想的应用其无用,以上是属于基本排序,必须掌握,接下来讲的归并和快排将会是进阶!
下面两个排序算法都是对分治
思想的应用(分治即分而治之,其思想就是将一个大问题分解为若干个子问题,针对子问题分别求解后,再将子问题的解整合为大问题的解)
。
分治三步走:
- 分解子问题
- 求解每个子问题
- 合并子问题的解,得出大问题的解
接下来就通过归并排序和快速排序来结合随便理解学习分治吧!
d. 归并排序
上代码:
//归并排序 使用递归的思想
var sortArray = function(nums) {
const len=nums.length;
if(len<=1){
return nums;
//如果只是一个值或空的数组就没必要排序了
//也作为递归的最底层返回条件,即分割到只有一个元素
}
//计算分割点
const mid=Math.floor(nums.length/2);
// 递归分割左子数组,然后合并为有序数组
const numsLeft=sortArray(nums.slice(0,mid));
// 递归分割右子数组,然后合并为有序数组
const numsRight=sortArray(nums.slice(mid));
//合并两个有序数组
nums=mergeArr(numsLeft,numsRight);
return nums;
};
//合并两个有序数组
var mergeArr=function(arr1,arr2){
let i=0;
let j=0;
let arr=[];//初始化一个数组,用于装来自两个有序数组的值
const len1=arr1.length;
const len2=arr2.length;
while(i<len1&&j<len2){
if(arr1[i]<arr2[j]){
arr.push(arr1[i]);
i++;
}else{
arr.push(arr2[j]);
j++;
}
}
//这里是遗留问题
//两个数组的长度可能不一样,那么其中有个数组全部都加入到了arr容器中后
//另一个更长的数组还有剩下的有序元素还未加入容器,则直接拼接该数组的剩余部分进容器
if(i<len1){
return arr.concat(arr1.slice(i));
}else{
return arr.concat(arr2.slice(j));
}
}
排序流程介绍:归并排序就是利用分治思想,将大问题分割成小问题,解决小问题,再将小问题的解合并,以获得大问题的解。
排序具体过程:
- 利用递归,一步一步分割数组,使数组对半分,形成两个小数组,递归下去,直到一个小数组只有一个元素。
- 把每个数组重新拼接,最小数组只有一个元素,本就算有序的,那么使用两个有序数组相加的算法合并得到的也是有序数组,一步一步合并,直到得到原来大数组的规模,这时已经是排好序的数组了。
leetcode提交结果分析:
这性能比基础排序好了很多。但也有个缺点,空间复杂度略高,需要复制多个数组
排序分析:
时间复杂度:O(nlogn)
空间复杂度:O(n)
稳定性: 稳定
这上面有一个步骤就是合并两个有序数组,leetcode位置
题目:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。
解题思路
:用双指针法。
- 因为 nums1 的空间都集中在后面,所以从后向前处理排序的数据会更好,节省空间,一边遍历一边将值填充进去j
- 设置指针 i 和 j 分别指向 nums1 和 nums2 的有数字尾部,从尾部值开始比较遍历,同时设置指针 k 指向 nums1 的最末尾,每次遍历比较值大小之后,则进行填充
- 当 i<0 时遍历结束,此时 nums2 中还有数据未拷贝完全,将其直接拷贝到 nums1 的前面,最后得到结果数组
这里给下代码:
var merge = function(nums1, m, nums2, n) {
// 初始化两个指针的指向,初始化 nums1 尾部索引k
let i=m-1;
let j=n-1;
let k=m+n-1;
// 当两个数组都没遍历完时,指针同步移动
while(i>=0&&j>=0){
//两个数组从后往前比较
//最大的放到最后
if(nums1[i]>=nums2[j]){
nums1[k]=nums1[i];
i--;
k--;
//通过i指针可以知道nums1哪些位置的元素已经放到了后面
//放到后面的元素其原来的位置虽然有值,但是可以被nums2里的值覆盖
}else{
nums1[k]=nums2[j];
j--;
k--;
}
}
// nums1 的有效部分和 nums2 并不一定是一样长的。
// 我们还需要考虑其中一个提前到头的这种情况:
// 所以有nums2 还有元素留下未加入的情况,特殊处理一下
while(j>=0){
nums1[k]=nums2[j];
j--;
k--;
}
};
e. 快速排序(重要)
排序流程介绍:快速排序在基本思想上和归并排序是一致的,依旧遵循着分治思想。区别在于,快速排序并不会把真的数组分割开来再合并到一个新数组中去,而是直接在原有的数组内部进行排序。
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数组变成有序序列。
步骤:
- 选择一个基准元素target(
一般选择第一个数,但都一样,这里以最左元素为基准介绍
) - 目的是将比target小的元素移动到数组左边,比target大的元素移动到数组右边(
这一步以两个指针实现,第一个指针在最左,第二个在最右
) - 因为左指针在基准值target的后一个位置,记住要完成目的,左指针就是要找比基准值target大的数,没找到就一直往右移动,找到了就停住,然后移动右指针,右指针要找到比基准值target小的数,没找到就向左移动,找到了也停住,与左指针找到的数交换位置,接着指针继续移动,直到右指针的下标大于左指针下标。这时就代表左边都是小于基准值target了,右边都大于基准值target了。
- 这时,就把基准值target与
右指针
指向的元素进行互换(下面有图,自己画画就能理解了),接着以基准值target所在的位置分成左右两侧。 - 再分别对基准值target左侧和右侧的元素进行快速排序
- 重复(可
递归
实现),直到左右侧只剩一个元素时结束
代码实现:
function sortArray(array, start, end) {
if (end - start < 1) {
return;//递归返回条件
}
const target = array[start];//基准值为最左边
//初始化左(l)右(r)指针
let l = start;
let r = end;
while (l < r) {
//满足左指针大于右指针,并且遍历的值大于基准值
while (l < r && array[r] >= target) {
r--;//移动
}//跳出说明找到了
array[l] = array[r];
//满足右指针大于左指针,并且遍历的值小于基准值
while (l < r && array[l] < target) {
l++;//移动
}//跳出说明找到了
array[r] = array[l];
}
//
array[r] = target;
sortArray(array, start, r - 1);
sortArray(array, r + 1, end);
return array;
}
如果觉得不好理解,也可以先学学下面得写法,更符合大众思维(但浪费大量存储空间)。
单独开辟两个存储空间left和right来存储每次递归比target小和大的序列,每次递归直接返回left、target、right拼接后的数组
//快速排序 好理解版
function sortArray(array) {
if (array.length <=1) {
//少于两个元素没必要排序
return array;
}
const target = array[0];//基准值为最左那个
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < target) {
left.push(array[i]);//比基准值小的放在左边
} else {
right.push(array[i]);//比基准值大的放在右边
}
}
//递归
return sortArray(left).concat([target], sortArray(right));
}
而且根据基准值的位置不同有很多种写法。下面给个以中间位置
为基准值的写法。
接着上代码:
function sortArray(arr, left = 0, right = arr.length - 1) {
// 定义递归边界,若数组只有一个元素,则没有排序必要
if(arr.length > 1) {
// lineIndex表示下一次划分左右子数组的索引位
const lineIndex = partition(arr, left, right)
// 如果左边子数组的长度不小于1,则递归快排这个子数组
if(left < lineIndex-1) {
// 左子数组以 lineIndex-1 为右边界
sortArray(arr, left, lineIndex-1)
}
// 如果右边子数组的长度不小于1,则递归快排这个子数组
if(lineIndex<right) {
// 右子数组以 lineIndex 为左边界
sortArray(arr, lineIndex, right)
}
}
return arr
}
// 以基准值为轴心,划分左右子数组的过程
function partition(arr, left, right) {
// 基准值默认取中间位置的元素
let pivotValue = arr[Math.floor(left + (right-left)/2)]
// 初始化左右指针
let i = left
let j = right
// 当左右指针不越界时,循环执行以下逻辑
while(i<=j) {
// 左指针所指元素若小于基准值,则右移左指针
while(arr[i] < pivotValue) {
i++
}
// 右指针所指元素大于基准值,则左移右指针
while(arr[j] > pivotValue) {
j--
}
// 若i<=j,则意味着基准值左边存在较大元素或右边存在较小元素,交换两个元素确保左右两侧有序
if(i<=j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++
j--
}
}
// 返回左指针索引作为下一次划分左右子数组的依据
return i
}
leetcode提交结果分析(看看其的效率):
排序分析:
时间复杂度:O(nlogn),实际上大多数情况下小于O(nlogn)
空间复杂度:O(nlogn)
稳定性: 不稳定(递归调用消耗)
最后说说sort排序
幸运的是JavaScript中有自带的方法能够进行排序,这里也给出代码。使用sort非常简单。
//普通解法,使用sort排序
//sort的底层是
var sortArray = function(nums) {
return nums.sort((a,b)=>{
return a-b;
})
};
leetcode提交结果:sort非常优秀
知道为什么sort这么优秀吗?因为其血统?
V8 引擎 sort 函数只给出了两种排序 InsertionSort 和 QuickSort,数组长度小于等于 22 的用插入排序 InsertionSort,比22大的数组则使用快速排序 QuickSort。
源码中这样写道:
// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.
此外,其他引擎的sort实现方式如下:
Mozilla/Firefox : 归并排序(jsarray.c 源码)
Webkit :底层实现用了 C++ 库中的 qsort() 方法(JSArray.cpp 源码)
感谢阅读,希望大佬提出学习建议,本人也准备在四五月找实习当中,希望有大佬捞捞,想一起学习的小伙伴也可以加我微信一起学习?
微信号:xieHB-frontend-178
参考文章:
ConardLi的blog-快速排序
排序算法稳定性的意义
前端算法与数据结构面试