基本排序算法
用到的技术是一组嵌套的for循环。其中外循环会遍历数组中的每一项，内循环则用于比较元素。选择排序和插入排序要比冒泡排序快，插入排序是这三种最快的。
冒泡排序
按照升序排列，较大的值会浮动到数组的右侧，而较小的值会浮动到数组的左侧。算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。
function bubbleSort() {
var numElements = this.dataStore.length;
var temp;
for ( var outer = numElements; outer >= 2; --outer) {
for ( var inner = 0; inner <= outer -1; ++inner) {
if(this.dataStore[inner] > this.dataStore[inner - 1]) {
swap(this.dataStore, inner, inner+1);
}
}
}
}
假设数组大小为N，外部循环N-1次，内部分别循环循环N、N-1...2次。
- 第一次循环(0, N-1)，循环结束后最大值在数据最右侧。
- 第二次循环(0, N-2)，循环结束后倒数第二大的数据位于序号为N-2的位置。
- ...
- 第N-1次循环(0，1)，循环结束后，排序完成。
选择排序
从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。
外循环从数组的第一个元素移动到倒数第二个元素，内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。
function selectionSort() {
var min, temp;
for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
min = outer;
for (var inner = outer +1; inner <= this.dataStore.length-1; ++inner) {
if (this.dataStore[inner] < this.dataStore[min]) {
min = inner;
}
swap(this.dataStore, outer, min);
}
}
}
数组位置是互换，不是移动。这是与插入排序的区别
插入排序
外循环将数组挨个移动，而内循环对外循环选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。
function insertionSort(){
var temp, inner;
for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
temp = this.dataStore[outer];
inner = outer;
while (inner > 0 && (this.dataStore[inner -1] >= temp)) {
this.dataStore[inner] = this.dataStore[inner -1];
--inner
}
this.dataStore[inner] = temp
}
}
高级排序算法
希尔排序
在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素，这样可以使离正确位置很远的元素更快的回到合适的位置。
在开始做最后一次处理时，大部分元素都将在正确的位置，算法就不必对很多元素进行交换。这就是希尔排序比插入排序更高效的地方。
...
this.gaps = [5,3,1];
function shellsort() {
for (var g = 0; g < this.gaps.length; ++g) {
for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
var temp = this.dataStore[i];
for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]){
this.dataStore[j] = this.dataStore[j - this.gaps[g]];
}
this.dataStore[j] = temp;
}
}
}
间隔序列，静态和动态效率是一样的
归并排序
把一系列排好序的子序列合并成一个大的完整有序序列。
基本上不会用到
快速排序
处理大数据集最快的排序算法之一。通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。
首先要在列表中选择一个元素作为基准值。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。
快速排序的算法如下：
- 选择一个基准元素，将列表分隔成两个子序列
- 对列表重新排序，将所有小于基准值得元素放在基准值的前面，所有大于基准值的元素放在基准值的后面
- 分别对较小元素的子序列和较大元素的子序列重复步骤1和2
function qSort(list) {
if (list.length == 0) {
return [];
}
var lesser = [];
var greater = [];
var pivot = list[0];
for (var i = 1; i < list.length; i++) {
if (list[i] < pivot) {
lesser.push(list[i]);
} else {
greater.push(list[i]);
}
}
return qSort(lesser).concat(pivot, qSort(greater));
}
快速排序算法非常适用于大型数据集合，在处理小数据集时性能反而会下降
参考
- 《数据结构与算法 JavaScript 描述》
