首页 > 代码库 > 排序算法复习：直接插入排序、堆排序、快排、冒泡排序
排序算法复习：直接插入排序、堆排序、快排、冒泡排序
冒泡排序，感觉是最简单的排序：
基本思路：每次把数组中最小的一个元素像气泡一样浮动、固定到最顶端：
从前向后遍历数组，每次拿到一个元素，就执行一遍冒泡：
从数组末尾开始，到当前元素截止，从后向前遍历，每次比较数组中相邻的两个元素，如果后者比较小，就把两者互换。
这样经过第一次冒泡，可以把最小的元素『浮』到数组的首位。第二次冒泡会把第二小的元素『浮』到数组的第二位。直到所有的元素都被『浮动』到正确的位置。
代码极其简单：
var BubbleSort = function (array) { var len = array.length; for(var i=0; i<len; ++i){ for(var j=len-1; j>i; --j){ if(array[j] < array[j-1]){ var temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; } } }};
冒泡算法一般是把小的元素上浮。也可以略微改动一下，变成大的元素下沉，实现上很相似。
插入排序：
基本思路：假定已有一个有序数组（从小到大），则每次插入只要把新元素放到合适的位置就可以了，为了减少额外的内存占用，可以在原数组上做调整：
对数组从前向后遍历，保证遍历过的元素，都是从小到大排列：所以遍历到新元素时，就要把新元素和已遍历过的元素逐个比较，通过 swap 最后把新元素放到合适位置。
代码实现：
var InsertSort = function (array) { //从前到后，每次指定一个数字，逐个比较它之前的每个数字，插入到合适的位置 var len = array.length; for(var i=0; i<len; ++i){ for(var j=i; j>0; --j){ if(array[j] < array[j-1]){ var tmp = array[j - 1]; array[j - 1] = array[j]; array[j] = tmp; } else { break; } } }};
感觉直接插入排序，中间也有用到冒泡的思路：遍历到新元素时，用冒泡的方式，把新元素逐步浮动到正确的位置。
堆排序：
基本思路：构建一个最小堆，每次从堆中取出堆顶，也就是最小元素。然后调整最小堆，再次取出堆顶的最小元素。直到堆为空。（用数组的方式构建优先队列的方式，我后续写一下）
为了避免申请额外的数组，此处直接在原数组中做了调整：每次取出的最小元素没有放到新的数组，而是放到数组尾部，然后把剩下的数组元素调整成最小堆。
这样当所有元素都被移动到数组尾端之后，也就完成了排序。
代码实现：
//从小到大var HeapSort = function (array) { var len = array.length; for(var k=len-1; k>=0; --k) { //build heap for (var i = k; i > 0; --i) { var pIndex = Math.floor((i - 1) / 2); if (array[i] < array[pIndex]) { var temp = array[pIndex]; array[pIndex] = array[i]; array[i] = temp; } } //remove smallest to array end array.push(array.shift()); }};
这里用到了 JS 中的数组内建函数 shift、push。如果要更通用的方式，有这样一个思路：第一次构建成最小堆后，不取出堆顶，而是直接用除堆顶以外的元素再次构建最小堆。伪码如下：
for(i from 0 to array.lengh){
build heap using array[i]-array[length-1]
}
快排：
据论证是最快的排序方式，等后续我实现希尔排序后比较一下速度。。。
基本思路：每次指定一个元素，将数组中所有小于它的元素，放到数组最侧，大于它的元素放到右侧。然后以该元素为界分成两个数组区间，对它们执行同样的操作。
代码实现：
var QuickSort = function (array, pre, last) { var keyIndex = last; var key = array[keyIndex]; var oldPre = pre; var oldLast = last; last -= 1; if(pre > last){ return; } while(pre <= last){ if(array[pre] <= key){ ++pre; } else if(array[last] >= key){ --last; } else { var temp = array[last]; array[last] = array[pre]; array[pre] = temp; } } array[keyIndex] = array[pre]; array[pre] = key; QuickSort(array, oldPre, pre-1); QuickSort(array, pre+1, oldLast);};
JS 中数组的 sort 函数，也是用的快排，但是我对比后发现 sort 函数比上面实现的快排要慢，基本上 sort 耗时是 QuickSort 的2-3倍。这中间具体多了些什么？
用来对比的 sort 函数：
arrayCopy.sort(function (first, second) { if(first < second){ return -1; } return 1;});
附上我的测试代码：
var testArray = [];var totalNum = 20000;for(var i=0; i<totalNum; ++i){ testArray.push(Math.random() * totalNum); // testArray.push(Math.ceil(Math.random() * totalNum));}var arrayCopy = testArray.slice();var now = Date.now();InsertSort(arrayCopy);console.log("插入排序：" + (Date.now() - now));arrayCopy = testArray.slice();now = Date.now();HeapSort(arrayCopy);console.log("堆排序：" + (Date.now() - now));arrayCopy = testArray.slice();now = Date.now();BubbleSort(arrayCopy);console.log("冒泡排序：" + (Date.now() - now));arrayCopy = testArray.slice();now = Date.now();arrayCopy.sort(function (first, second) { if(first < second){ return -1; } return 1;});console.log("Array.sort 排序：" + (Date.now() - now));arrayCopy = testArray.slice();now = Date.now();QuickSort(arrayCopy, 0, arrayCopy.length-1);console.log("快排：" + (Date.now() - now));
几次测试的结果：
插入排序：217堆排序：770冒泡排序：740Array.sort 排序：11快排：6插入排序：217堆排序：771冒泡排序：753Array.sort 排序：10快排：5插入排序：218堆排序：763冒泡排序：735Array.sort 排序：9快排：4插入排序：217堆排序：762冒泡排序：747Array.sort 排序：11快排：7插入排序：222堆排序：764冒泡排序：759Array.sort 排序：17快排：7
排序算法复习：直接插入排序、堆排序、快排、冒泡排序