大家好，欢迎来到IT知识分享网。
引言
数组排序是你在 JavaScript 编程过程中经常会遇到的，也是面试中会考察的。那么思考两个问题，数据结构中稳定的排序算法和不稳定的排序算法分别有哪些？时间复杂度和空间复杂度分别代表了什么？
时间复杂度&空间复杂度
关于时间复杂度，说得更多的是通过 O(nlogn) 以及 O(n) 等来衡量。下面是一张时间复杂度的曲线图，图中用颜色区分了最优的、一般的、比较差的时间复杂度。
关于空间复杂度，就是对一个算法在运行过程中临时占用存储空间大小的度量。
各种排序的 JS 实现
数据结构算法中排序有很多种，根据它们的特性，可以大致分为两种类型：
1）比较类排序
通过比较来决定元素间的相对次序，其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
2）非比较类排序
不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
冒泡排序
冒泡排序是最基础的排序，一般在最开始学习数据结构的时候就会接触它。
快速排序
通过排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。
插入排序
插入排序算法描述的是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果。
选择排序
选择排序是一种简单直观的排序算法，首先将最小的元素存放在序列的起始位置，再从剩余未排序的元素中继续寻找最小元素，然后放到已排序的序列后面，以此类推，直到所有元素均排序完毕。
堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子节点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现。
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列，先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为二路归并。
归并排序是一种稳定的排序算法，归并排序的性能不受输入数据的影响，但表现比选择排序好得多，代价是需要额外的内存空间。
总结
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/94840.html
