冒泡排序
冒泡排序可能是咱们接触的第一个排序算法了，比较简单也实用。
思路：顺次比拟相邻的两个元素，值大的就换到左边，一趟循环下来最左边就是最大的元素了。而后再从头开始，找第二大的元素，这样始终走下来，整个数组就有序了。
能够参考以下 gif 图，了解冒泡排序的思维。
那么 N 个数字要排序实现，总共进行 N - 1 趟排序，每 i 趟的排序次数为 (N-i) 次，所以须要比拟的次数就是[n(n-1)]/2，即工夫复杂度为 O(n^2)
间接上代码：
var bubbleSort = function(array){ // 冒泡排序
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(array, j, j+1);
}
}
}
}
var swap = function(array, index1, index2){ // 替换两个元素的地位
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
}
var createNonSortedArray =function(size){ // 创立一个 size 大小的无序列表 ArrayList
var array = new Array();
for (var i = size; i > 0; i--) {array.push( parseInt(Math.random()*10000));
}
return array;
}
var arr = createNonSortedArray(10000);
bubbleSort(arr);这个代码无论是最好的状况（数组有序），还是最坏状况（数组逆序），须要比拟的次数都是[n(n-1)]/2，也就是工夫复杂度均为 O(n^2)，但如果是最好的状况，一趟比拟下来发现没有元素要替换，那么工夫复杂度就能降到 O(n)，故再加一个标记位，就能让冒泡排序的最好状况工夫复杂度降到 O(n)，如下：
var bubbleSort = function(array){
var length = array.length,
for (var i = 0; i < length; i++) {
var didSwap = false; // 设置标记位
for (var j = 0; j < length-1-i; j++) {if (array[j] > array[j+1]) {swap(array, j, j+1);
didSwap = true;
}
}
if(!didSwap) break; // 没有替换了，间接跳出循环
}
}插入排序
思维：一个元素就是有序的，那么从第二个元素开始，与它之前的元素作比拟，如果比之前的元素小，就替换地位。直到比某个元素大，就完结此次循环，也就找到了该元素应该在的地位了。把所有元素都走一遍，整个数组就有序了。
能够参考以下 gif 图，了解插入排序的思维。
在插入排序中，当待排序数组是有序时，是最优的状况，只需以后数跟前一个数比拟一下就能够了，这时一共须要比拟 N - 1 次，工夫复杂度为 O(n)。
最坏的状况是待排序数组是逆序的，此时须要比拟次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏状况下的工夫复杂度为 O(n^2)。
var insertionSort = function(array){
var length = array.length,
temp, j;
for(var i = 1; i<length; i++){
j = i;
temp = array[i];
while(j > 0 && array[j-1] > temp){array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}抉择排序
思维：从数组的第一个元素开始，一趟循环，找出最小的，放到第一个元素的地位，而后从第二个元素开始，反复之前的步骤，直到数组整个有序。
能够参考以下 gif 图，了解抉择排序的思维。
其中橙色示意以后排序趟的最左侧元素，绿色是这趟排序找到的最小元素的地位，灰背景是以后比拟的指针。
工夫复杂度其实与冒泡排序相似，也是一个 O(n)复杂度的算法。
代码如下：
var selectionSort = function(array){
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(array, i, indexMin) // 与之前冒泡排序 swap 办法统一，替换元素地位
}
}
}