JS-几大排序算法(更新中...)

关于排序都会讲的名词:(我自己的理解)

  时间复杂度:  指排序过程中,程序消耗的时间。

  空间复杂度:  指排序过程中,程序所消耗内存的大小。

     稳定:  如果两个值相等,a和b,a=b且a在b位置的左边,排序后依旧在左边(或者上下排列的话,可以理解为前边)。

    不稳定:  两个相等的值在一起,排序会让其互换位置。

关于稳定和不稳定,有图说明:

如上图一:北京成都、上海广州,这两对,值相等,分别都是90和50,北京在成都的前边吧,

如上图二:排序后,按大小顺序排列,但是之前成都在后边,现在跑到北京的前边了。

如上图三:再次点击排序按钮,西安和呼和浩特分别是最大最小没有动,但是北京成都、上海广州这两对互换了位置

这就是不稳定。

如果不互换,按照图一的位置,最终的排序应该是:西、北、成、上、广、呼。且无论后期点多少次排序,都将是这个顺序才是。

一、冒泡排序

源代码:

var arrData=[12,35,23,18,95,2,67,9,56];
sortArr(arrData);

function sortArr(arr){
     for(i=0;i<arr.length-1;i++){
         for(j=0;j<arr.length-1-i;j++){
           if(arr[j]>arr[j+1]){
               var temp=arr[j];
               arr[j]=arr[j+1];
               arr[j+1]=temp;
            }
         }
    }
    return arr;
} 

分析用的代码:

 1 var arrData=[12,35,23,18,95,2,67,9,56];
 2 sortArr(arrData);
 3 
 4 function sortArr(arr){
 5             for(i=0;i<arr.length-1;i++){
 6                 console.log("i="+i+",下标对应数为"+arr[i]+",大循环 "+(i+1));
 7                 for(j=0;j<arr.length-1-i;j++){
 8                         console.log("j="+j+",下标对应数为"+arr[j]+",小循环"+(i+1)+"-"+(j+1));
 9                         console.log("j+1对应的数是"+arr[j+1]);
10                         console.log(arr[j]+"和"+arr[j+1]+"比");
11                     if(arr[j]>arr[j+1]){
12                             console.log(arr[j]+"大于"+arr[j+1]+",互换位置");
13                         var temp=arr[j];
14                         console.log("先把"+arr[j]+"存到temp中");
15                         arr[j]=arr[j+1];
16                         console.log("再让"+arr[j]+"等于后边比他小的"+arr[j+1]);
17                         arr[j+1]=temp;
18                         console.log("最后把存在temp中前边较大的值"+temp+"给了后边的arr[j+1]");
19                     }else{
20                         console.log(arr[j]+"小于"+arr[j+1]+",跳过本次循环");
21                     }
22                 }
23             }
24             return arr;
25         }

排序过程中,文字描述 

输出结果:[2, 9, 12, 18, 23, 35, 56, 67, 95]; 初始值对比:[12,35,23,18,95,2,67,9,56];

  1 i=0,下标对应数为12,大循环 1
  2 j=0,下标对应数为12,小循环1-1
  3 j+1对应的数是35
  4 12和35比
  5 12小于35,跳过本次循环
  6 j=1,下标对应数为35,小循环1-2
  7 j+1对应的数是23
  8 35和23比
  9 35大于23,互换位置
 10 先把35存到temp中
 11 再让前边的大值35等于后边比他小的23
 12 最后把存在temp中前边较大的值35给了后边的arr[j+1]
 13 调换23与35的顺序完成
 14 j=2,下标对应数为35,小循环1-3
 15 j+1对应的数是18
 16 35和18比
 17 35大于18,互换位置
 18 先把35存到temp中
 19 再让前边的大值35等于后边比他小的18
 20 最后把存在temp中前边较大的值35给了后边的arr[j+1]
 21 调换18与35的顺序完成
 22 j=3,下标对应数为35,小循环1-4
 23 j+1对应的数是95
 24 35和95比
 25 35小于95,跳过本次循环
 26 j=4,下标对应数为95,小循环1-5
 27 j+1对应的数是2
 28 95和2比
 29 95大于2,互换位置
 30 先把95存到temp中
 31 再让前边的大值95等于后边比他小的2
 32 最后把存在temp中前边较大的值95给了后边的arr[j+1]
 33 调换2与95的顺序完成
 34 j=5,下标对应数为95,小循环1-6
 35 j+1对应的数是67
 36 95和67比
 37 95大于67,互换位置
 38 先把95存到temp中
 39 再让前边的大值95等于后边比他小的67
 40 最后把存在temp中前边较大的值95给了后边的arr[j+1]
 41 调换67与95的顺序完成
 42 j=6,下标对应数为95,小循环1-7
 43 j+1对应的数是9
 44 95和9比
 45 95大于9,互换位置
 46 先把95存到temp中
 47 再让前边的大值95等于后边比他小的9
 48 最后把存在temp中前边较大的值95给了后边的arr[j+1]
 49 调换9与95的顺序完成
 50 j=7,下标对应数为95,小循环1-8
 51 j+1对应的数是56
 52 95和56比
 53 95大于56,互换位置
 54 先把95存到temp中
 55 再让前边的大值95等于后边比他小的56
 56 最后把存在temp中前边较大的值95给了后边的arr[j+1]
 57 调换56与95的顺序完成
 58 i=1,下标对应数为23,大循环 2
 59 j=0,下标对应数为12,小循环2-1
 60 j+1对应的数是23
 61 12和23比
 62 12小于23,跳过本次循环
 63 j=1,下标对应数为23,小循环2-2
 64 j+1对应的数是18
 65 23和18比
 66 23大于18,互换位置
 67 先把23存到temp中
 68 再让前边的大值23等于后边比他小的18
 69 最后把存在temp中前边较大的值23给了后边的arr[j+1]
 70 调换18与23的顺序完成
 71 j=2,下标对应数为23,小循环2-3
 72 j+1对应的数是35
 73 23和35比
 74 23小于35,跳过本次循环
 75 j=3,下标对应数为35,小循环2-4
 76 j+1对应的数是2
 77 35和2比
 78 35大于2,互换位置
 79 先把35存到temp中
 80 再让前边的大值35等于后边比他小的2
 81 最后把存在temp中前边较大的值35给了后边的arr[j+1]
 82 调换2与35的顺序完成
 83 j=4,下标对应数为35,小循环2-5
 84 j+1对应的数是67
 85 35和67比
 86 35小于67,跳过本次循环
 87 j=5,下标对应数为67,小循环2-6
 88 j+1对应的数是9
 89 67和9比
 90 67大于9,互换位置
 91 先把67存到temp中
 92 再让前边的大值67等于后边比他小的9
 93 最后把存在temp中前边较大的值67给了后边的arr[j+1]
 94 调换9与67的顺序完成
 95 j=6,下标对应数为67,小循环2-7
 96 j+1对应的数是56
 97 67和56比
 98 67大于56,互换位置
 99 先把67存到temp中
100 再让前边的大值67等于后边比他小的56
101 最后把存在temp中前边较大的值67给了后边的arr[j+1]
102 调换56与67的顺序完成
103 i=2,下标对应数为23,大循环 3
104 j=0,下标对应数为12,小循环3-1
105 j+1对应的数是18
106 12和18比
107 12小于18,跳过本次循环
108 j=1,下标对应数为18,小循环3-2
109 j+1对应的数是23
110 18和23比
111 18小于23,跳过本次循环
112 j=2,下标对应数为23,小循环3-3
113 j+1对应的数是2
114 23和2比
115 23大于2,互换位置
116 先把23存到temp中
117 再让前边的大值23等于后边比他小的2
118 最后把存在temp中前边较大的值23给了后边的arr[j+1]
119 调换2与23的顺序完成
120 j=3,下标对应数为23,小循环3-4
121 j+1对应的数是35
122 23和35比
123 23小于35,跳过本次循环
124 j=4,下标对应数为35,小循环3-5
125 j+1对应的数是9
126 35和9比
127 35大于9,互换位置
128 先把35存到temp中
129 再让前边的大值35等于后边比他小的9
130 最后把存在temp中前边较大的值35给了后边的arr[j+1]
131 调换9与35的顺序完成
132 j=5,下标对应数为35,小循环3-6
133 j+1对应的数是56
134 35和56比
135 35小于56,跳过本次循环
136 i=3,下标对应数为23,大循环 4
137 j=0,下标对应数为12,小循环4-1
138 j+1对应的数是18
139 12和18比
140 12小于18,跳过本次循环
141 j=1,下标对应数为18,小循环4-2
142 j+1对应的数是2
143 18和2比
144 18大于2,互换位置
145 先把18存到temp中
146 再让前边的大值18等于后边比他小的2
147 最后把存在temp中前边较大的值18给了后边的arr[j+1]
148 调换2与18的顺序完成
149 j=2,下标对应数为18,小循环4-3
150 j+1对应的数是23
151 18和23比
152 18小于23,跳过本次循环
153 j=3,下标对应数为23,小循环4-4
154 j+1对应的数是9
155 23和9比
156 23大于9,互换位置
157 先把23存到temp中
158 再让前边的大值23等于后边比他小的9
159 最后把存在temp中前边较大的值23给了后边的arr[j+1]
160 调换9与23的顺序完成
161 j=4,下标对应数为23,小循环4-5
162 j+1对应的数是35
163 23和35比
164 23小于35,跳过本次循环
165 i=4,下标对应数为23,大循环 5
166 j=0,下标对应数为12,小循环5-1
167 j+1对应的数是2
168 12和2比
169 12大于2,互换位置
170 先把12存到temp中
171 再让前边的大值12等于后边比他小的2
172 最后把存在temp中前边较大的值12给了后边的arr[j+1]
173 调换2与12的顺序完成
174 j=1,下标对应数为12,小循环5-2
175 j+1对应的数是18
176 12和18比
177 12小于18,跳过本次循环
178 j=2,下标对应数为18,小循环5-3
179 j+1对应的数是9
180 18和9比
181 18大于9,互换位置
182 先把18存到temp中
183 再让前边的大值18等于后边比他小的9
184 最后把存在temp中前边较大的值18给了后边的arr[j+1]
185 调换9与18的顺序完成
186 j=3,下标对应数为18,小循环5-4
187 j+1对应的数是23
188 18和23比
189 18小于23,跳过本次循环
190 i=5,下标对应数为35,大循环 6
191 j=0,下标对应数为2,小循环6-1
192 j+1对应的数是12
193 2和12比
194 2小于12,跳过本次循环
195 j=1,下标对应数为12,小循环6-2
196 j+1对应的数是9
197 12和9比
198 12大于9,互换位置
199 先把12存到temp中
200 再让前边的大值12等于后边比他小的9
201 最后把存在temp中前边较大的值12给了后边的arr[j+1]
202 调换9与12的顺序完成
203 j=2,下标对应数为12,小循环6-3
204 j+1对应的数是18
205 12和18比
206 12小于18,跳过本次循环
207 i=6,下标对应数为56,大循环 7
208 j=0,下标对应数为2,小循环7-1
209 j+1对应的数是9
210 2和9比
211 2小于9,跳过本次循环
212 j=1,下标对应数为9,小循环7-2
213 j+1对应的数是12
214 9和12比
215 9小于12,跳过本次循环
216 i=7,下标对应数为67,大循环 8
217 j=0,下标对应数为2,小循环8-1
218 j+1对应的数是9
219 2和9比
220 2小于9,跳过本次循环
221 输出结果:[2, 9, 12, 18, 23, 35, 56, 67, 95];
222 初始值对比:[12,35,23,18,95,2,67,9,56];

 原理:

第一遍循环,在内循环里把最大的数拍到了最后。

第二遍循环i,在内循环里,排除掉最后一个最大的不循环,将剩下的再次循环,把次要大的排到最后。

最终,出来从大到小的循环。

再循环里边,让当前循环到的数和后一个比较,若小于不动位置,若大于,则将这个数先存到temp中,然后让这个数等于后一个数,再让后一个数等于temp,完成两个数的位置调换。

依次类推,最后比后一个数大的数,都被移到了最后。

若变成从大到小的循环:

只需把  if(arr[j]>arr[j+1])  处的大于号换成小于号即可。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣谈编程

选择排序

面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

33980
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

还有一个不错的视频(https://marcus-biel.com/java-comparable-interface-video-tutorial/)。

11340
来自专栏玄魂工作室

Python黑帽编程2.9 面向对象编程

Python黑帽编程2.9 面向对象编程 我个人认为,计算机语言的发展,有两个方向,一个是从低到高的发展过程,在这个过程中,语言的思考和解决问题的方式是面向硬件...

30370
来自专栏Java架构师进阶

HashMap的工作原理

    HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和...

8830
来自专栏大史住在大前端

野生前端的数据结构练习(9)冒泡排序,选择排序,插入排序

bubble sort的是最基本的算法,被誉为永远会被考从来不被用的算法,基本原则是大数右移,每轮遍历后最右侧的数是最大的,所以下一轮循环时可不予考虑,时间复杂...

8220
来自专栏C语言及其他语言

《黄老师问答笔录》之C语言常见易错问题

以下摘自黄老师课堂课堂答疑、与学生交流的真实问题总结,为了便于入学者学习查阅,总结归纳于此。 1、问:我想判断一个数字是否在一个区间里,比如if(90<a<10...

361130
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

17460
来自专栏Golang语言社区

Golang语言社区--Go语言基础第二节变量

大家好,我是社区主编cserli(或者大家叫我彬哥也可以),Golang语言社区一直致力于Go语言相关技术干货的分享,希望初学者可以少走些弯路,我...

627270
来自专栏LeetCode

LeetCode <dp>64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left t...

17000
来自专栏海天一树

NOIP 2018提高组初赛C/C++答案详解

分析: 二进制化八进制:从低位(右)往高位(左),每三位直接换成八进制即可。 (1001101011)2 = (10 0110 1011)2 = (26B)...

29640

扫码关注云+社区

领取腾讯云代金券