(function () {
/* 通排序
最快最简单的排序
*/
var data = [100, 50, 75, 25, 1, 20, 90, 30, 80, 40, 60, 50], result = [],
barrel = [], i, j, item;
//初始化桶 m = 桶数
for (i = 0; i <101; i++) {
barrel[i] = 0;
}
//插入桶 n = 排序数的个数
for (i = 0; item = data[i]; i++) {
barrel[item]++;
}
//遍历桶 m
for (i = 0; i ) {
//输出排序数 n
if (barrel[i] !== 0) {
for (j = 0; j ) {
result.push(i);
}
}
}
console.log(result.join(", "));
// O(m+n+m+n) = O(2*(m+n)) = O(M+N)
}());
(function () {
/* 冒泡排序
基本思想:每次比较两个相邻的元素,如果他们的顺序错误就把他们交换过来。
原理:每一趟只能确定将一个数归位。
*/
var data = [100, 50, 75, 25, 1, 20, 90, 30, 80, 40, 60, 50],
length = data.length - 1, inLength, i, j, vitem;
for (i = 0; i ) {
inLength = length - i;
for (j = 0; j ) {
if (data[j] > data[j + 1]) {
vitem = data[j + 1];
data[j + 1] = data[j];
data[j] = vitem;
}
}
}
console.log(data.join(", "));
// O(N²)
}());
(function () {
/* 快排序
快排每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止。
每次交换是跳跃式的,总的比较和交换次数就少了。确定基准数两面相对其是正确的顺序。
基于“二分”思想
*/
var data = [6, 9, 3, 7, 1, 5, 4, 8, 2, 3],
quickSort = function (left, right) {
var mid = data[left], i = left, j = right, vitem;
if (left > right) {
return;
}
while (i !== j) {
while (data[j] >= mid && i < j) {
j--;
}
while (data[i] <= mid && i < j) {
i++;
}
if (i < j) {
vitem = data[j];
data[j] = data[i];
data[i] = vitem;
}
}
data[left] = data[i];
data[i] = mid;
quickSort(left, i - 1);
quickSort(i + 1, right);
};
quickSort(0, data.length - 1);
console.log(data.join(", "));
// O(NlogN)
}());