希尔和堆排序
//希尔排序(插入)
Array.prototype.shellSort = function(){
var increment = this.length;
console.info('初始化步长：'+increment);
var temp,j;
do{
increment = parseInt(increment/3)+1;
console.info('步长变为：'+increment);
for (var i = increment; i < this.length; i++) {
console.info('对比 第'+i+'个元素:'+this[i]+',第'+(i-increment)+'个元素:'+
this[i-increment]);
if(this[i]<this[i-increment]){
temp = this[i];
for(j = i-increment;j>=0&&temp<this[j];j-=increment){
console.info('赋值 第'+(j+increment)+'个元素'+this[j+increment]
+'赋值为第'+j+'元素'+this[j]);
this[j+increment] = this[j];
}
this[j+increment] = temp;
console.info('赋值 第'+(j+increment)+'个元素'+this[j+increment]
+'赋值为第'+i+'元素'+temp);
}
}
}
while(increment>1);
}
//堆排序
//调整函数
Array.prototype.headAdjust = function(pos, len){
//将当前节点值进行保存
var swap = this[pos];
//定位到当前节点的左边的子节点
var child = pos * 2 + 1;
//递归，直至没有子节点为止
while(child < len){
//如果当前节点有右边的子节点，并且右子节点较大的场合，采用右子节点
//和当前节点进行比较
if(child + 1 < len && this[child] < this[child + 1]){
child += 1;
}
//比较当前节点和最大的子节点，小于则进行值交换，交换后将当前节点定位
//于子节点上
if(this[pos] < this[child]){
this[pos] = this[child];
pos = child;
child = pos * 2 + 1;
}
else{
break;
}
this[pos] = swap;
}
}
//构建堆
Array.prototype.buildHeap = function(){
//从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
//将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
//直至构建出大顶堆（升序为大顶，降序为小顶）
for(var i=parseInt(this.length/2); i>=0; i--){
this.headAdjust(i, this.length);
}
}
Array.prototype.heapSort = function(){
//构建堆
this.buildHeap();
//从数列的尾部开始进行调整
for(var i=this.length-1; i>0; i--){
//堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
//最大元素保存于尾部，并且不参与后面的调整
var swap = this[i];
this[i] = this[0];
this[0] = swap;
//进行调整，将最大）元素调整至堆顶
this.headAdjust(0, i);
}
}
var a1 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('希尔排序before: ' + a1);
a1.shellSort();
console.log('希尔排序after: ' + a1);
var a2 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('堆排序before: ' + a2);
a2.heapSort();
console.log('堆排序after: ' + a2);
希尔排序before: 3,1,5,7,2,4,9,6,10,8
初始化步长：10
步长变为：4
对比 第4个元素:2,第0个元素:3
赋值 第4个元素2赋值为第0元素3
赋值 第0个元素2赋值为第4元素2
对比 第5个元素:4,第1个元素:1
对比 第6个元素:9,第2个元素:5
对比 第7个元素:6,第3个元素:7
赋值 第7个元素6赋值为第3元素7
赋值 第3个元素6赋值为第7元素6
对比 第8个元素:10,第4个元素:3
对比 第9个元素:8,第5个元素:4
步长变为：2
对比 第2个元素:5,第0个元素:2
对比 第3个元素:6,第1个元素:1
对比 第4个元素:3,第2个元素:5
赋值 第4个元素3赋值为第2元素5
赋值 第2个元素3赋值为第4元素3
对比 第5个元素:4,第3个元素:6
赋值 第5个元素4赋值为第3元素6
赋值 第3个元素4赋值为第5元素4
对比 第6个元素:9,第4个元素:5
对比 第7个元素:7,第5个元素:6
对比 第8个元素:10,第6个元素:9
对比 第9个元素:8,第7个元素:7
步长变为：1
对比 第1个元素:1,第0个元素:2
赋值 第1个元素1赋值为第0元素2
赋值 第0个元素1赋值为第1元素1
对比 第2个元素:3,第1个元素:2
对比 第3个元素:4,第2个元素:3
对比 第4个元素:5,第3个元素:4
对比 第5个元素:6,第4个元素:5
对比 第6个元素:9,第5个元素:6
对比 第7个元素:7,第6个元素:9
赋值 第7个元素7赋值为第6元素9
赋值 第6个元素7赋值为第7元素7
对比 第8个元素:10,第7个元素:9
对比 第9个元素:8,第8个元素:10
赋值 第9个元素8赋值为第8元素10
赋值 第8个元素10赋值为第7元素9
赋值 第7个元素8赋值为第9元素8
希尔排序after: 1,2,3,4,5,6,7,8,9,10
堆排序before: 3,1,5,7,2,4,9,6,10,8
堆排序after: 1,2,3,4,5,6,7,8,9,10
[Finished in 0.1s]
快速排序
function quickSort(arr){
//如果数组<=1,则直接返回
if(arr.length<=1){
return arr;
}
var pivotIndex=Math.floor(arr.length/2);
//找基准，并把基准从原数组删除
var pivot=arr.splice(pivotIndex,1)[0];
//定义左右数组
var left=[];
var right=[];
//比基准小的放在left，比基准大的放在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));
}
var a1 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('排序before: ' + a1);
a1 = quickSort(a1);
console.log('排序after: ' + a1);
排序before: 3,1,5,7,2,4,9,6,10,8
排序after: 1,2,3,4,5,6,7,8,9,10
归并排序
function merge(left,right) {
var result = [];
while(left.length>0&&right.length>0){
if(left[0]<right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
function mergeSort(arr){
if(arr.length==1){
return arr;
}
var mid = Math.floor(arr.length/2);
var left = arr.slice(0,mid);
var right = arr.slice(mid);
return merge(mergeSort(left),mergeSort(right))
}
var a1 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('排序before: ' + a1);
a1 = mergeSort(a1);
console.log('排序after: ' + a1);
排序before: 3,1,5,7,2,4,9,6,10,8
排序after: 1,2,3,4,5,6,7,8,9,10
[Finished in 0.1s]
