摘要：基本排序算法在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。毕竟他们的效率都不太理想在实际应用中，应该选择高级排序算法快速排序在随机生成数据测试的时候，发现很多时候，插入排序要快于冒泡排序以及选择排序。
基本排序算法
在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。
这里简单的介绍三种最基本的排序，分别是：冒泡排序、选择排序以及插入排序
排序的过程中，经常要用到交换元素位置，故抽离为公共函数 swap。// 交换位置
export function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
冒泡排序
冒泡排序是最简单的排序，一一对比相邻的两个数，顺序不对就交换过来，这样子，每一轮最大的值总会慢慢的被交换到最右侧。所以才会叫冒泡排序
描述假设数组长度为 n
比较相邻的两个数，如果第 1 个大于第 2 个，就交换位置
重复第 1 步，一轮下来最大值被交换到第 n 个位置，也就是最右侧
开启新一轮，重复 1~2 步，最大值会被冒泡到第 n-1 个位置
重复上述步骤，直到所有都排序好
例子：对 3, 1, 5, 2, 4 进行排序
1,3,5,2,4 3 > 1 ,交换位置 1,3,5,2,4 3 < 5 ,不变 1,3,2,5,4 5 > 2 ,交换位置 1,3,2,4,5 5 > 4 ,交换位置,第一轮结束 1,3,2,4,5 1 < 3 ,不变 1,2,3,4,5 3 > 2 ,交换位置 1,2,3,4,5 ...依次对比 1,2,3,4,5 ... 1,2,3,4,5 ... 结束代码实现
// 冒泡排序
export function bubbleSort(array) {
for (let i = array.length - 1; i >= 1; i--) {
let hasSwap = false;
for (let j = 0; j <= i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
hasSwap = true;
}
}
if (!hasSwap) {
// 这里用于优化，如果某一轮之后，没有进行任何交换，说明已经排序完成了，所以退出循环
break;
}
}
}
效果演示
https://global.chen4342024.co...
注意打开开发者工具，切换到移动端模式小结
冒泡算法是比较慢的排序之一，也是最容易实现的算法之一。
稳定性：稳定
时间复杂度： 平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)
额外空间复杂度 O(1)
选择排序选择排序是指每一轮从数组中取出最小值，然后跟第一个元素交换位置。然后再找出第二个最小值，跟第二个元素交换位置，。。。以此类推。直到倒数第二个位置
例子对 3, 1, 5, 2, 4 进行排序
// 这里只展示每一轮的结果 3 1 5 2 4 //开始 1 3 5 2 4 //第 1 轮 1 2 5 3 4 //第 2 轮 1 2 3 5 4 //第 3 轮 1 2 3 4 5 //第 4 轮代码实现
// 选择排序从开头开始，找出最小的值，放在第一个位置
// 有点类似打扑克拍的时候，抽取每一张最小的放在最左边
export function selectSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
let min = array[i];
for (let j = i + 1; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
效果演示
https://global.chen4342024.co...
注意打开开发者工具，切换到移动端模式
稳定性：不稳定
时间复杂度： O(n^2)
额外空间复杂度 O(1)
插入排序插入排序的思想是，依次从数组中未排序的部分，取出数据，然后插入到已排序的部分。直到清空未排序的部分
描述假设数组长度为 n , 从第 2 项开始
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。
代码实现export function insertSort(array) {
for (let i = 0; i < array.length; i++) {
let temp = array[i];
let j = i;
while (j > 0 && array[j - 1] > temp) {
// 将所有大于temp的往右移
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
}
效果演示
https://global.chen4342024.co...
注意打开开发者工具，切换到移动端模式
稳定性：稳定
时间复杂度：平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)
额外空间复杂度 O(1)
效果演示（汇总）https://global.chen4342024.co...
注意打开开发者工具，切换到移动端模式总结
这三种最基本的排序算法的复杂度非常相似，从理论上来说，它们的执行效率也应该差不多。
在实际使用中，如果需要排序的数据比较多，是不推荐使用这 3 种排序的。毕竟他们的效率都不太理想
在实际应用中，应该选择高级排序算法： 快速排序 ...
在随机生成数据测试的时候，发现很多时候，插入排序要快于冒泡排序以及选择排序。大概是冒泡/选择排序的快 1 倍
这是因为 插入排序需要比较的次数是 1+2+3+..+n = n * (n-1) /2,这是最坏的情况，大部分时候并不需要全部比较，所以平均下来只需要 n*(n-1)/4
而冒泡/选择排序都需要n * (n-1)/2,所以平均下来，插入排序大概是冒泡/选择排序的快 1 倍
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/100206.html
摘要：介绍排序算法是算法中最常见的算法之一，我这里要介绍的是排序算法中的三种基本算法冒泡排序选择排序插入排序，在文章的后面我会对三种算法的速度进行对比。 1.介绍 排序算法是算法中最常见的算法之一，我这里要介绍的是排序算法中的三种基本算法：冒泡排序、选择排序、插入排序，在文章的后面我会对三种算法的速度进行对比。 2.冒泡排序 冒泡排序其名来源与其算法实现，会使得数组中的元素一个个从数组一端漂...
摘要：本篇主要实现九八大排序算法，分别是冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序计数排序。希尔排序是非稳定排序算法。归并排序算法依赖归并操作。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。 本篇主要实现九(八）大排序算法，分别是冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序,计数排序。希望大家回顾知识的时候也能从我的这...
摘要：数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象，称为结点。 本文涉及更多的是概念，代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念，可能部分地方会涉及更高级的算法和算法，具体内容以...
摘要：基本排序算法总结前言随着的兴起将推向的一个前所未有的高度作为为建立高性能的服务端而创建的运行平台随着时间的推移和生态链的完善已经不再局部于服务端包括前端后端桌面这篇文章介绍的传统的散打排序方法并用实现其功能如有需要可以对其封装在随后会介绍高 基本排序算法总结 前言 随着node的兴起, 将javascript推向的一个前所未有的高度, node作为为建立高性能的服务端而创建的js运行平...
摘要：由于排序的算法有很多，在本次算法系列的分享当中，我们先从简单易上手的选择排序法开始，其它的排序算法会随后陆续跟大家一起分享。 HTML5学堂-码匠：数据快速的计算与排序，与前端页面性能有直接的关系。由于排序的算法有很多，在本次算法系列的分享当中，我们先从简单易上手的选择排序法开始，其它的排序算法会随后陆续跟大家一起分享。 算法的基本概念 算法是什么，它有何作用 为解决一个问题而采取的方...
阅读 3076·2023-04-26 00:53
阅读 3521·2021-11-19 09:58
阅读 1693·2021-09-29 09:35
阅读 3277·2021-09-28 09:46
阅读 3850·2021-09-22 15:38
阅读 2691·2019-08-30 15:55
阅读 3005·2019-08-23 14:10
阅读 3820·2019-08-22 18:17
