比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
JavaScript代码实现：
function bubbleSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for (var i = 0; i < len - 1; i++) { for (var j = len - 1; j >= i; j--) { if (array[j] < array[j - 1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } return array; } else { return 'array is not an Array!'; } }
3）算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
五、快速排序
1）算法简介
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2）算法描述和实现
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 "基准"（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
JavaScript代码实现：
//方法一 function quickSort(array, left, right) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') { if (left < right) { var x = array[right], i = left - 1, temp; for (var j = left; j <= right; j++) { if (array[j] <= x) { i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } quickSort(array, left, i - 1); quickSort(array, i + 1, right); }; } else { return 'array is not an Array or left or right is not a number!'; } } var aaa = [3, 5, 2, 9, 1]; quickSort(aaa, 0, aaa.length - 1); console.log(aaa); //方法二 var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); };
3）算法分析
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlogn)
六、堆排序
1）算法简介
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
2）算法描述和实现
具体算法描述如下：
将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
JavaScript代码实现：
/*方法说明：堆排序 @param array 待排序数组*/ function heapSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { //建堆 var heapSize = array.length, temp; for (var i = Math.floor(heapSize / 2); i >= 0; i--) { heapify(array, i, heapSize); } //堆排序 for (var j = heapSize - 1; j >= 1; j--) { temp = array[0]; array[0] = array[j]; array[j] = temp; heapify(array, 0, --heapSize); } } else { return 'array is not an Array!'; } } /*方法说明：维护堆的性质 @param arr 数组 @param x 数组下标 @param len 堆大小*/ function heapify(arr, x, len) { if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') { var l = 2 * x, r = 2 * x + 1, largest = x, temp; if (l < len && arr[l] > arr[largest]) { largest = l; } if (r < len && arr[r] > arr[largest]) { largest = r; } if (largest != x) { temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr, largest, len); } } else { return 'arr is not an Array or x is not a number!'; } }
3）算法分析
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
七、归并排序
1）算法简介