摘要：冒泡排序冒泡排序算法的运作如下比较相邻的元素。交换次数比冒泡排序少多了快速排序快速排序算法的运作如下找一个数，对数组进行扫描，小于这个数的放在这个数的左侧，大于它的放在数组右侧在对左右两侧的数组分别进行刚才的操作，直到数组长度为时结束。
1.冒泡排序 1.1 冒泡排序算法的运作如下：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。1.2 javaScript中的实现
var arr = [9,8,7,6,5,4,3,2,1,0];
//交换arr[i]和arr[j]
function swap(arr,i,j){
var temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//冒泡排序
function bubbleSort(arr){
var leap = 0;
if(arr.length==0)
return;
for(var i = 0 ; i < arr.length ; i++){
leap = 0;
for(var j = 1 ; j < arr.length ; j++){
if(arr[j-1] > arr[j]){
swap(arr,j-1,j);
leap = 1;
}
}
//如果没有交换，即排序正确，提前结束
if(leap == 0){
return;
}
}
return arr;
}
console.log(bubbleSort(arr)); // arr = [0,1,2,3,4,5,6,7,8,9]
冒泡排序总的平均时间复杂度为Q(n^2)。
2.选择排序 2.1 选择排序算法的思想：循环arr.length次，从i=0开始，第i次循环将比较得到的最小（或最大）的数与a[i]交换位置，即每次循环拿出最值放到其应该在的位置，并且将其踢出下次循环。2.2 javaScript中的实现
//选择排序
function selectionSort(arr){
var min;
if(arr.length <= 1)
return;
for(var i = 0 ; i < arr.length-1 ; i++){
min=i;
for(var j = i+1 ; j < arr.length ; j++)
{
if(arr[j] < arr[min]){
min = j;
}
}
swap(arr,i,min);
}
return arr;
}
console.log(selectionSort(arr)); // arr = [0,1,2,3,4,5,6,7,8,9]
比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了
3.快速排序 3.1 快速排序算法的运作如下：1.找一个数，对数组进行扫描，小于这个数的放在这个数的左侧，大于它的放在数组右侧 2.在对左右两侧的数组分别进行刚才的操作，直到数组长度为1时结束。3.2 javaScript中的实现
//快速排序
function fastSort(arr,begin,end){
//当end <= begin时结束递归
if(end <= begin){
return ;
}
var t = begin;
var i = begin+1;
var j = end;
var v = arr[begin];
while (i <= j){
//通过选定的轴和其后一个值进行比较，如后一个值比他小则交换并且两个同时加一并且再比较，如比他大则a[i]和a[j]进行交换并且再比较a[begin]和a[i]的值
if (arr[i] <= v){
swap(arr, t++, i++);
}else if(arr[i] > v){
swap(arr, i, j--);
}
}
fastSort(arr, begin, t-1);
fastSort(arr, j+1, end);
}
fastSort(arr,0,arr.length-1);
console.log(arr); //arr = [0,1,2,3,4,5,6,7,8,9]
此快速排序是优化过的，能否再优化以后再试试看。
以上代码有部分是借鉴的,如有不足请指教^_^
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/94736.html
摘要：用冒泡排序快速排序选择排序冒泡排序冒泡排序是比较经典的排序方法，是一种用时间换空间的排序方法。找到并交换的时候，指针位置不变。选择排序没趟都会产生最小值，它不是相邻元素的比较而是在该元素设置一个索引。选择排序循环找到从开始到最后的最小的数 用js冒泡排序,快速排序,选择排序 1.冒泡排序 冒泡排序是比较经典的排序方法，是一种用时间换空间的排序方法。我总结了一下它的特点：（1）它的时间复...
摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。 上一篇：JS数据结构与算法_树 写在前面 这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...
摘要：优化当待排序序列长度时，使用插入排序，可以加速排序。插入排序原理通过构建有序序列，对于未排序元素，在已排序序列中从后向前扫描，找到相应位置并插入。堆排序可通过树形结构保存部分比较结果，可减少比较次数。 前端学习：教程&开发模块化/规范化/工程化/优化&工具/调试&值得关注的博客/Git&面试-前端资源汇总 欢迎提issues斧正：排序算法 JavaScript-排序算法及简易优化 快速...
本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法，文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现，如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读 排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...
摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法为王。 想学好前端，先练好内功，...
阅读 3648·2021-09-30 09:59
阅读 2266·2021-09-13 10:34
阅读 581·2019-08-30 12:58
阅读 1510·2019-08-29 18:42
阅读 2201·2019-08-26 13:44
阅读 2927·2019-08-23 18:12
阅读 3324·2019-08-23 15:10
阅读 1628·2019-08-23 14:37
