1.随机生成数据
var a = (function (){
var a = [];
function randomInt(from, to){
return parseInt(Math.random() * (to - from + 1) + from);
}
for (var i = 0; i < 10000; i++){
a.push(randomInt(0, 1000000))
}
return a;
})();
2.插入排序
function insertionSort(){
var date = new Date();
for (var i = 1; i < a.length; i++){
var temp = a[i];
for (var j = i - 1; j >= 0 && a[j] > temp; j--){
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
console.log("插入排序的时间:" + (new Date() - date));
}
3.希尔排序
function shellSort(){
var date = Date.now();
for (var gap = a.length >> 1; gap > 0; gap >>= 1){
for (var i = gap; i < a.length; i++){
var temp = a[i];
for (var j = i - gap; j >= 0 && a[j] > temp; j -= gap){
a[j + gap] = a[j];
// console.log(a[j])
}
a[j + gap] = temp;
console.log(a[i],a[j])
console.log(a)
}
}
console.log("希尔排序的时间:" + (new Date() - date));
}
4.归并
function merge(a, b, lo, mid, hi){
//每次归并前,都需要先把a中的数据copy到b中。
for (var i = 0; i < a.length; i++){
b[i] = a[i];
}
var i = lo, j = mid + 1;
for (var k = lo; k <= hi; k++){
if (i > mid){
a[k] = b[j++];
}else if (j > hi){
a[k] = b[i++];
}else if (b[i] < b[j]){
a[k] = b[i++];
}else{
a[k] = b[j++]
}
}
}
5.归并排序
function sort(a, temp, lo, hi){
if (lo >= hi) return;
var mid = (hi + lo) >> 1;
sort(a, temp, lo, mid); //左半部分排序
sort(a, temp, mid + 1, hi);//右半部分排序
merge(a, temp, lo, mid, hi);
}
6. 快速排序
function quickSort(a, lo, hi){
if (lo >= hi) return;
var j = quickPartition(a, lo, hi);
quickSort(a, lo, j - 1);
quickSort(a, j + 1, hi);
}
7.快速排序的切分
function quickPartition(a, lo, hi){
var i = lo, j = hi + 1; //左右扫描指针
var p = a[lo]; //切分元素
for (; ;){
//扫描左右,检查扫描是否结束,并交换元素
while (a[++i] <= p){
if (i == hi) break;
}
while (a[--j] >= p){
if (j == lo) break;
}
//如果左指针超过了右指针则结束
if (i >= j) break;
//交换左右的元素
exch(a, i, j);
}
//把a[lo]添加到指定的位置
exch(a, lo, j);
return j;
}
function exch(a, m, n){
var temp = a[m];
a[m] = a[n];
a[n] = temp;
}