利用JavaScript实现独特排序算法的高效方法

这里用Javascript完成冒泡排序、挑选排序、插入排序、合并排序以及疾速排序这些罕见的排序算法

起首我们给本文商定一个完成的框架：定义一个ArrayList类内里包括排序数组声明、数组元素增加、排序算法完成以及数组输出的要领。

代码框架：

function ArrayList(){
var array=[]; this.inputArraymember=function(){ //将10个大小在1~15的随机数增加到数组中
var ins=0;
for(var i=0;i<10;i++){
ins=Math.floor(Math.random()*15+1);
array.push(ins);
}
}; this.响应的排序算法=function(){...算法的详细完成代码...}; //代码块替代部份 this.toString=function(separator){ //将数组按指定分隔符天生字符串轻易输出
return array.join(separator);
}; } var a = new ArrayList();
a.inputArraymember();
console.log("随机天生的原始数组为："+a.toString('-'));
a.bubbleSort();
console.log("排序后数组为："+a.toString('-'));

冒泡排序

用两层轮回，第一层用来纪录盈余的还未排序的数的个数，第二层用来在剩下的未排序的数中找到最大的数并将其放到未排序数的末了面（冒泡）。

代码完成：

this.bubbleSort=function(){
var length=array.length;
for(var i=0;i for(var j=0;j if(array[j]>array[j+1]){
var t=array[j]; array[j]=array[j+1];array[j+1]=t;
}
}
}
};

冒泡排序的时刻复杂度是O(n²)。将以上代码替代文章最先商定的代码框架中的“代码块替代部份”即可用于在调试东西中运转检察代码运转效果。

挑选排序

思绪很简单，每次都找出未排序的数当中最小的数并放在开首，直到一切数的位置肯定下来。说清楚点就是从一切序列中先找到最小的，然后放到第一个位置。以后再看盈余元素中最小的，放到第二个位置……以此类推。

代码完成：

this.selectsort=function(){
var length=array.length,currentMin;
for(var i=0;i currentMin=i; //用来纪录最小数的下标，默以为最最先的未排序的元素下标
for(var j=i;j if(array[currentMin]>array[j]){
currentMin=j;
}
}
if(i!==currentMin){ //若下标不是未排序的最最先的谁人元素的下标，则将二者的值交流
var t=array[currentMin];
array[currentMin]=array[i];
array[i]=t;
}
}
};

可看出，挑选排序也用了两个嵌套着的轮回，所以时刻复杂度也是O(n²)，是一种旧址排序。

插入排序

从第二个数最先（由于第一个数只要一个，前面没得比。），与前面的数挨个比较，直到找到前一个数比当前值小，后一个数比当前值大的位置，让后将当前值置于此处，以此类推。

代码完成：

this.insertsort=function(){
var length=array.length, j,temp;
for(var i=1;i j=i;
temp=array[i]; //先存储待比较的数
while(j>0&&array[j-1]>temp){ //假如这个数比上一个数小，则让上一个数占有如今这个数的位置（右移每一个比当前数小的数）
array[j]=array[j-1];
j--
}
array[j]=temp; //直到这个数不比上一个数小的时刻，将这个数放在当前的位置
}
};


合并排序

时刻复杂度为O(nlogn)。合并用的是分治的头脑，将原始数组切分红较小的数组，直到每一个小数组只要一个位置，接着讲小数组合并成较大的数组，直到末了只要一个排序终了的大数组。

代码完成：

this.mergeSort=function() {
array = mergeSortRec(array);
}; //建堆函数，将数组一向拆分红两部份，直到各部份数组长度都为1的时刻住手，然后举行merge操纵
var mergeSortRec = function(array){
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length / 2),
left = array.slice(0, mid),//slice() 要领可从已有的数组中返回选定的元素,语法 arrayObject.slice(start,end)
right = array.slice(mid, length);
return merge(mergeSortRec(left), mergeSortRec(right));
};
//将各部份举行合并
var merge = function(left, right) {
var result = [],
il = 0,
ir = 0;
while(il if (left[il] result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
//假如il数组另有盈余，则将其盈余部份增加到效果数组中
while (il result.push(left[il++]);
}
//假如ir数组另有盈余，则将其盈余部份增加到效果数组中
while (ir result.push(right[ir++]);
}
return result;
};


疾速排序

时刻复杂度为O(logn)。用的是分治的头脑。

代码完成：

this.quickSort = function(){
quick(array, 0, array.length - 1);
};
var partition = function(array, left, right) { //分别历程

//主元的挑选要领最好是随机挑选一个数组想或是挑选中心项，这里挑选中心项
var pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right;
console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);
while (i <= j) {
while (array[i] i++;
console.log('i = ' + i);
}
while (array[j] > pivot) {
j--;
console.log('j = ' + j);
}
if (i <= j) {
console.log('swap ' + array[i] + ' with ' + array[j]);
swapQuickStort(array, i, j);
i++;
j--;
}
}
return i;
};
var swapQuickStort = function(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
var quick = function(array, left, right){//将子数组星散为较小值数组和较大值数组
var index;
if (array.length > 1) {
index = partition(array, left, right);
if (left quick(array, left, index - 1);
}
if (index quick(array, index, right);
}
}
return array;
};