首页 > 代码库 > 算法分析-前七章排序算法全实现

算法分析-前七章排序算法全实现

var A = [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2];

Array.prototype.swap = function (i, j) {
var temp = this[j];
this[j] = this[i];
this[i] = temp;
};

Array.prototype.getMaxVal = function () {
//可以用任意我们学过的排序方法写,我们学过冒泡,选择,归并,快排,堆排序。
//当然这样我们只要取出最大值即可,不需要全部排序,但是为了学程序,我将给出我们已经学过的所有排序方法,并全部排序

// return this.BUBBLE_SORT()[this.length - 1];
// return this.SELECT_SORT()[this.length - 1];
};
//冒泡
Array.prototype.BUBBLE_SORT = function () {

//冒泡就是两两将换,
for (var i = this.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (this[j] > this[j + 1]) {
this.swap(j, j + 1);
}
}
}
return this;
};


//选择排序

Array.prototype.SELECT_SORT = function () {
for (var i = 0; i < this.length - 1; i++) {
var min = this[i]; //默认选择第一个最小;
var index = i; //记录最小值的坐标

for (var j = i + 1; j < this.length; j++) {
if (this[j] < min) {
min = this[j];
index = j;
}
}
this.swap(index, i);
}
return this;
};


//随机算法-快排
Array.prototype.PARTITION = function (p, r) {
var i = p - 1;
var x = this[r];
for (var j = p; j <= r - 1; p++) {
if (this[j] < x) {
this.swap(++i, j);
console.log(this);
}

}
this.swap(++i, r);
return i;
};

Array.prototype.RANDOM_PARTION = function (p, r) {

var q = p + Math.round(Math.random() * (r - p));
console.log("q", q, "交换前", this);
this.swap(q, r);
console.log("q", q, "交换后", this);
var index = this.PARTITION(p, r);
console.log(index);
return index;
};

Array.prototype.QUICK_SORT = function (p, r) {
if (r > p) {
var q = this.RANDOM_PARTION(p, r);

arguments.callee.call(this, p, q - 1);
arguments.callee.call(this, q + 1, r);
}
return this;
};

console.log(A.QUICK_SORT(0, A.length - 1));

算法分析-前七章排序算法全实现