- 冒泡排序
// 冒泡排序 每次将最小元素推至最前
function sort4(array) {
var len = array.length,
i, j, tmp, result;
result = array.slice(0);
for (i = 0; i < len; i++) {
for (j = len - 1; j > i; j--) {
if (result[j] < result[j - 1]) {
tmp = result[j - 1];
result[j - 1] = result[j];
result[j] = tmp;
}
}
}
return result;
}
<small>改进冒泡排序</small>
// 如果在某次的排序中没有出现交换的情况，
// 那么说明在无序的元素现在已经是有序了，就可以直接返回了。
function sort5(array) {
var len = array.length,
i, j, tmp, exchange, result;
result = array.slice(0);
for (i = 0; i < len; i++) {
exchange = 0;
for (j = len - 1; j > i; j--) {
if (result[j] < result[j - 1]) {
tmp = result[j];
result[j] = result[j - 1];
result[j - 1] = tmp;
exchange = 1;
}
}
if (!exchange) return result;
}
return result;
}
- 选择排序
// 在无序区中选出最小的元素，然后将它和无序区的第一个元素交换位置。
// 原理跟冒泡排序一样，算是冒泡的衍生版本
function sort7(array) {
var len = array.length,
i, j, k, tmp, result;
result = array.slice(0);
for (i = 0; i < len; i++) {
k = i;
for (j = i + 1; j < len; j++) {
if (result[j] < result[k]) k = j;
}
if (k != i) {
tmp = result[k];
result[k] = result[i];
result[i] = tmp;
}
}
return result;
}
- 快速排序
<small> 在JS中相对较快</small>
//（1）在数据集之中，选择一个元素作为"基准"（pivot）。
//（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
//（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
function sort6(array) {
var tmp_array = array.slice(0), result,
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));
};
result = quickSort(tmp_array);
return result;
}
- 插入排序
// 插入排序 从下标1开始每增1项排序一次，越往后遍历次数越多
function sort1(array) {
var len = array.length,
i, j, tmp, result;
// 设置数组副本
result = array.slice(0);
for(i=1; i < len; i++){
tmp = result[i];
j = i - 1;
while(j>=0 && tmp < result[j]){
result[j+1] = result[j];
j--;
}
result[j+1] = tmp;
}
return result;
}
<small> 改进：二分插入排序</small>
// 先在有序区通过二分查找的方法找到移动元素的起始位置，
// 然后通过这个起始位置将后面所有的元素后移
function sort2(array) {
var len = array.length,
i, j, tmp, low, high, mid, result;
// 赋予数组副本
result = array.slice(0);
for(i = 1; i < len; i++){
tmp = result[i];
low = 0;
high = i - 1;
while(low <= high){
mid = parseInt((low + high)/2, 10);
if(tmp < result[mid]) high = mid - 1;
else low = mid + 1;
}
for(j = i - 1; j >= high+1; j--){
result[j+1] = result[j];
}
result[j+1] = tmp;
}
return result;
}
- 希尔排序
// 希尔排序：先取合适gap将整个待排序记录序列分割成若干个子序列
// 在序列内分别进行直接插入排序，待整个序列基本有序时，
// 再对全体记录进行一次直接插入排序
function sort3(array){
var len = array.length, gap = parseInt(len/2),
i, j, tmp, result;
// 复制数组
result = array.slice(0);
while(gap > 0){
for(i = gap; i < len; i++){
tmp = result[i];
j = i - gap;
while(j>=0 && tmp < result[j]){
result[j + gap] = result[j];
j = j - gap;
}
result[j + gap] = tmp;
}
gap = parseInt(gap/2);
}
return result;
}
<small> 动态定义间隔序列 </small>
while(gap < len/5) { //动态定义间隔序列
gap =gap*5+1;
}
mark: 十大经典排序算法总结（JavaScript描述）
