排序算法的javascript实现与说明(99js笔记)

冒泡排序

冒泡的原理是让最大的元素或最小的元素“浮动”

插入排序、选择排序、快速排序和冒泡排序都是比较排序

思考

依次比较两个相邻的数字，将十进制数字放在前面，大数字放在后面。

第一步：比较第一个数字和第二个数字，把小数放在前面，大数字放在后面。将第二个数字与第三个数字进行比较，将小数放在前面，大数字放在后面，并继续，直到最后两个数字进行比较，小数放在前面，大数字放在后面。第二步：第二遍：仍然从第一对开始比较(因为第二个和第三个数字互换，第一个数字不再小于第二个数字)。十进制数发布后，将与倒数第二个数(倒数第二个位置已经是最大的)进行比较。第二遍后，在倒数第二个位置获得一个新的最大数(实际上是整个序列中的第二大数)如果是，重复上述过程，直到最终完成排序。因为在排序过程中小数总是向前，大数向后，相当于冒泡往上走，所以叫做冒泡排序。气泡排序的动画效果

实现：这段代码比较简单，属于算法中最基础的代码。注意三点

1.交换类的方法可以用javascript中的a=[b，b=a][0]来解决，而不是

复制代码如下：var，a，b，temp temp=a；a=b；b=温度

这种交换方法2。注意循环变量的缓存，这里缓存了array.length3。注意嵌入式循环，从第一个数字到倒数第二个数字进行比较，N是比较的步数

函数bubbleSort(array){ var l=array . length；for(var I=0；I l；I) {//比较的步数为(var j=0)的数组长度；j . l-I；J) {//嵌入交换的个数是从第一个数到最后一个总长-n，n是比较的步数if(array[j]array[j-1]){ array[j]=[array[j-1]，array [j-1]=array [j]] [0]/。k l；k ) {console.log(数组[k]'，')；}console.log('这是第(I ^ 1)'个排序')}}var a=[6，54，6，22，5，7，8，2，34]；起泡rt(a)；动画效果

插入排序很简单，就是我们触摸卡片并插入！思考：

1首先，假设我们碰了一张牌，手里所有的牌都设置为空=[]，碰了一把推(arr[0])；2取出下一张牌并设置为a，从后向前扫描我们所有的空牌(已排序)；3如果我们手中的牌空[empty.length-n]大于新元素，则将牌移到下一个位置(腾出空间)空[empty.length-n]=empty [empty。length-n 1] 4重复步骤3，直到已分拣的卡片清空[清空。length-n]小于或等于a5，将A插入这个空的位置[empty.length-n]=a6重复步骤2，但javascript代码仍然被实现

函数insert(arr){ var l=arr . length；var empty=[]；//空数组，表示我们手空. push(arr[0])；//我们来摸一个for(var I=1；I l；I) {//注意这里的起点是1，因为我们已经摸过一个了！如果是空的。length-1]) {empty [empty。length]=arr[I]}//如果大于有序数组empty，则直接放在for(var j=empty . length；j 0 arr[i]空[j-1]；j-){//与最大值的arr进行比较，以清空arr。当arr命令一个数组的一个位时，没有必要移动它。空[j]=空[j-1]；//向右移动空[j-1]=arr[I]；//将值放在空位置}//console . log(empty)} return empty }那么这里比较重要的知识点就是符号，意思是“和”，也就是表达式成立之前必须满足两边的条件。符号也可以替换if。例如，如果(a){fun()}等于ab。另一个要点是，如果数组是arr，那么它的“最后一项”就是arr[arr.length-1]。

排序动画

选择排序也是一种简单的排序算法。

思考：

找到最小的元素-把它扔进数组-再次找到较小的元素-把它扔进数组，以此类推。首先，找到无序数组中最小的元素。查找的方法可以采用常数判断赋值的手段，即让数组[0]中的第一个元素为最小元素，那么“最小元素”将在数组中的序号为0后遍历数组。如果数组中的第二个元素比他小，那么第二个元素就是最小的元素，把“0”更新为“1”。遍历后，我们知道这个数列的最小元素是下标“n”；直接取出存储在排序序列的开头(array[n])，然后继续从剩余的未排序元素中搜索最小的元素，再放在排序序列的末尾。注意遍历的下标从1开始。因为我们选出了最小的元素。以此类推，直到所有元素都被排序。

函数select sort(array){ var min；var l=array.length//的缓存长度(var I=0；I l；I) {//开始循环，总共循环l次，就可以找出l个元素min=I；//假设第一个是(var j=I ^ 1)的最小元素；j l；J) {//从第一个开始循环，遍历if (array[min] array[j])//判断后一个是否小于前一个，min=j；//更新“最小值”的下标}if (min！=i) {//这里，因为我们在同一个数组中操作，所以可以直接交换元素。例如，如果数组的第一项是I，那么我发现最小的元素是array[min]，所以我需要用I交换这个min，以此类推。array[i]=[array[min]，array[min]=array[I]][0]；//exchange elements } }返回数组；}这里我们还是要注意的是，交换的写法是array[i]=[array[min]，array [min]=array [I]] [0]，可以方便的交换array[i]和array[min ]~

排序动画

快速排序快速排序是目前最强大的排序算法，它采用了递归的思想。思考

从数组中选择一个元素，称为“基准”。这个元素可以通过长度/2直接选择来遍历数组。所有小于基准值的元素都放在基准的前面，所有大于基准值的元素都放在基准的后面(两边可以是相同的数字)。一般来说，男人站在左边，女人站在右边。然后我们得到一个数组array=一个由比基准小的部分组成的数组，lArray，一个由比基准大的部分组成的数组。那么我们只需要“以同样的方式”对待larray和rraray ~这需要递归编写。经过处理，lArray分为lArray基准，比lArray基准小，比lArray基准大。然后我们继续操作，男人站在左边，女人站在右边。直到我们发现lArray的长度变成1，已经不足以再除了，我们认为排序结束了。

函数quick sort(arr){ var l=arr . length；//缓存数组长度if(arr . length=1){ return arr }；//如果我们得到的lArray，rArray rraray的长度小于1，那么我们就不需要对其进行排列了~ varnum=math。地板(arr。长度/2)；//取数组中间的数字。注意长度/2不一定是整数，使用Math.floor对varnum value=arr.split (num，1) [0]进行舍入；//使用拼接方法取出一个元素，注意语法var left=[]；//创建左引用容器var right=[]；//为(var I=0；I l；I=1) {//开始遍历数组arr[i] numValue？向左推(arr[i]) :向右推(arr[I])；//男人站在左边，女人站在右边。}返回快速排序(左)。concat ([num value]，quick sort(right))//递归，继续对左右数组进行操作。}动画效果：

注意这里arr.splice(num，1)只画一个数字，但是拼接的结果也是一个数组，需要[0]，否则数组(1)的一堆数组会奇怪的出现。拼接的引用：//www . JB 51 . net/w3school/js/jsref _ splice.htm数学. floor是数学对象的引用//www . JB 51 . net/w3school/js/js _ obj _ math.htm什么是递归：http://baike.baidu.com/view/96473.htm

除了快速排序之外，以上四种算法都是简单的排序算法，这四种算法在采访中也经常被测试~这里需要强调的是，以上算法使用了大量关于循环和数组的知识，所以一定要记住！