专栏首页前端说吧JS-几大排序算法(更新中...)

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 条评论
登录 后参与评论

相关文章

  • Python - 基础知识

    在代码世界中,赋值符号=(一个等号)不是左边等于右边的意思。仅仅表示赋值动作:把右边的内容放到了左边的盒子中。

    xing.org1^
  • CSS-论css如何纯代码实现内凹圆角

    xing.org1^
  • CSS3-transform变形功能

    xing.org1^
  • 外媒:域名Covermate.com超35万终端交易

    近段时间,域名圈仍爆出了不少好米交易,我们来看看是哪些域名。

    躲在树上的域小名
  • Linux-CentOS6.9安装Python3与Python2共存

    sudo -s 1 查看CentOS系统自带的Python信息,一般为2.6或2.7版,我们接下来要做的就是保留系统自带的Python版本,并安装 Pyth...

    双面人
  • Linux安装Python

        Linux下默认系统自带python2.6的版本,这个版本被系统很多程序所依赖,所以不建议删除,如果使用最新的Python3编译安装源码包和系统默认包之...

    py3study
  • 米未来以中五位价格买下四声域名bdzp.com

    四声母.com域名一直是域名市场的风向标,向来备受投资人和终端的青睐,近日就获悉,一枚四声域名bdzp.com以中五位价格交易,卖家是米友“米未来”...

    躲在树上的域小名
  • HBase面试题

    (1) Hbase一个分布式的基于列式存储的数据库,基于Hadoop的hdfs存储,zookeeper进行管理。

    黑白格
  • 1.opencv图像基本操作

    如果已经看过pillow库对图片进行处理,应该已经对图片处理有了解了(不了解的可以去看一下)。尽管pillow库在处理图片方面已经非常强大,但是和opencv功...

    用户7054460
  • 使用gpg密钥验证github提交

    版权声明:本文为博主原创文章,转载请注明出处。 ...

    乐百川

扫码关注云+社区

领取腾讯云代金券