首页 > 代码库 > 算法分析-前七章排序算法全实现
算法分析-前七章排序算法全实现
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));
算法分析-前七章排序算法全实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。