JavaScript-排序算法

冒泡排序

冒泡排序是所有排序中最简单的，但从性能和计算时间来看，也是最差的。

  var length = array.length
  for(var i = 0; i<length; i++){
      for(var j = 0; j<length-1; j++) {
          if(array[j]>array[j+1]) {
              swap(j, j+1)
          }
      }
  }
 
 var swap = function(index1, index2) {
   var aux = array[index1]
   array[index1] = array[index2]
   array[index2] = aux
 }      //用于交换值的函数

看到以上代码，它的大致思路是这样的，首先，声明一个名为length的变量，用来存储数组的长度（行{1}）接着，外循环会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序（应该是数组中每项都经过一轮，轮数和数组长度一致）。然后，内循环将从第一位迭代至倒数第二位，内循环实际上进行当前项和下一项的比较。如果这两项顺序不对（当前项比下一项大），则交换它们，意思是位置为j+1的值将会被换置到位置j处，反之亦然。

这个算法这样写是可以改进的，因为在排序的时候我们发现，当外循环执行到第二轮开始，有的数字已经是正确排序，尽管如此，后续还一直在比较当中，这是不必要的，我们想到从内循环来减去外循环跑过的轮数，改进后的代码如下：

var length = array.length
for(var i = 0; i<length; i++) {
    for(var j = 0; j<length-1-i; j++){    //注意：这里是修改的地方
        if(array[j]>array[j+1]) {   
            swap(j, j+1)
        }
    }
}

 var swap = function(index1, index2) {
   var aux = array[index1]
   array[index1] = array[index2]
   array[index2] = aux
 }      //用于交换值的函数

选择排序

var length = array.length, indexMin
for(var i = 0; i<length-1; i++) {
  indexMin = i
  for(var j = i; j<length; j++) {
   if(array[indexMin]>array[j]) {
     indexMin = j
   }
  }
  if (!i==indexMin) {
      swap(i, indexMin)
  }
}     //swap函数与上面相同

选择排序的思路是这样的，找到数据结构中的最小值，并将其放在第一位，接着找到第二小的值放在第二位，以此类推。根据代码我们来分析一下，

• 首先，声明一些即将使用的变量
• 接着外循环迭代数组，控制迭代轮次，假设数组长度为n，则轮次为n-1，因为前面确定下来最后一个也就确定了。
• 接下来假设本迭代轮次第一个值为数组的最小值，从当前i的值开始至数组结束，依次进行比较，比较是否j位置的值比当前i位置的值小，如果是，则改变最小值至新最小值。当内循环结束，将得出数组第n小的值。最后，如果该最小值和原最小值不同，则交换其值。

未完待续.......................................