|
|
这篇文章主要介绍了Javascript实现的常用算法,如冒泡、快速、鸽巢、选择、木桶、奇偶等,需要的朋友可以参考下
复制代码 代码如下:
l = [6, 2, 4, 1, 98, 34, 5, 9, 23, 8, 10, 32]
//冒泡排序
/*function bubbleSort(arr) {
newarr = arr.slice()
if (newarr.length <= 2) return newarr
for (var i = 0; i < newarr.length - 1; i++) {
for (var j = 0; j < newarr.length - i - 1; j++) {
if (newarr[j] > newarr[j + 1]) {
newarr[j] = [newarr[j + 1], newarr[j + 1] = newarr[j]][0]
}
}
}
return newarr
}
console.log(l)
result = bubbleSort(l)
console.log(result)*/
//快速排序
/*function quickSort(arr) {
if (arr.length <= 1) return arr;
var left = [],
right = [],
middle = [];
var mid = arr[Math.floor(arr.length / 2)]
for (var i = 0; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i]);
} else if (arr[i] > mid) {
right.push(arr[i]);
} else {
middle.push(mid);
}
}
return [].concat(quickSort(left), middle, quickSort(right))
}
var results = quickSort(l)
console.log(results)
*/
//选择排序
/*function selectSort(arr) {
var min = 9999,
minindex = 0;
var left = [],
right = arr.slice();
if (arr.length <= 1) return arr;
for (var i = 0; i < arr.length; i++) {
if (arr[i] <= min) {
min = arr[i];
minindex = i;
}
}
left.push(min);
right.splice(minindex, 1);
return [].concat(left, selectSort(right))
}
var results = selectSort(l)
console.log(results)*/
//插入排序
/*function insertSort(arr) {
var tmp;
for (var i = 1; i < arr.length; i++) {
tmp = arr[i];
for (var j = i; j > 0; j--) {
if (arr[j - 1] > tmp) {
arr[j] = arr[j - 1];
} else {
break;
}
}
arr[j] = tmp;
}
return arr;
}
var results = insertSort(l)
console.log(results)*/
//木桶排序
/*function bucketSort(arr){
var bucket = [];
var newarr = [];
for (var i = 0; i < arr.length; i++) {
bucket[arr[i]] = arr[i];
}
for (var i = 0; i < bucket.length; i++) {
if (bucket[i] !== undefined){
newarr.push(bucket[i])
}
}
return newarr;
}
var results = bucketSort(l)
console.log(results)*/
//鸽巢排序,非负整数
/*function pigeonholeSort(arr){
var tempArr = [];
for(var i=0,l=arr.length;i<l;i++){
tempArr[arr[i]] = (tempArr[arr[i]]+1)||1 ;
}
var result = [],count;
for(var k=0;k<tempArr.length;k++){
count = tempArr[k];
if(count){
for(var i=0;i<count;i++){
result.push(k);
}
}
}
return result;
}
var results = pigeonholeSort(l)
console.log(results)*/
//归并排序
/*function mergeSort(arr) {
if (arr.length <= 1) return arr;
var mid = Math.floor(arr.length / 2);
var left = MergeSort(arr.slice(0, mid));
var right = MergeSort(arr.slice(mid));
var result = [];
while (left.length && right.length) {
if (left[left.length - 1] <= right[0]) {
result = result.concat(left);
left = [];
} else if (right[right.length - 1] < left[0]) {
result = result.concat(right);
right = [];
} else {
if (right[0] < left[0]) {
result.push(right.shift());
} else {
result.push(left.shift());
}
}
}
result = result.concat(left, right);
return result;
}*/
/*function mergeSort(arr) {
var merge = function(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);
}
if (arr.length == 1) return arr;
var middle = Math.floor(arr.length / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
var results = mergeSort(l)
console.log(results)
*/
//堆排序
/*function heapSort(arr) {
var findRoot = function(arr, p, length) {
p = p || 0;
length = length || arr.length;
var self = arguments.callee;
var l = p * 2 + 1;
var r = (p + 1) * 2;
var left, right;
if (l < length) left = self(arr, l, length);
if (r < length) right = self(arr, r, length);
if (left > arr[p]) arr[p] = [left, arr[l] = arr[p]][0];
if (right > arr[p]) arr[p] = [right, arr[r] = arr[p]][0];
return arr[p];
};
for (var i = arr.length; i > 0; i--) {
findRoot(arr, 0, i);
arr[i - 1] = [arr[0], arr[0] = arr[i - 1]][0];
}
return arr;
}
var results = heapSort(l)
console.log(results)*/
//奇偶排列
/*function oddEvenSort(arr) {
var swaped = true,
k = 0;
while (swaped) {
if (k > 0) swaped = false;
for (var i = k; i < arr.length - 1; i += 2) {
if (arr[i]>arr[i+1]) {
arr[i] = [ arr[i+1], arr[i+1]=arr[i] ][0];
swaped = true;
}
}
k = [1, 0][k]
}
return arr;
}
var results = oddEvenSort(l)
console.log(results)*/
function oddEvenSort(arr) {
var swaped = true;
while (swaped) {
swaped = false;
for (var i = 0; i < arr.length; i += 2) {
if (arr[i] > arr[i + 1]) {
arr[i] = [arr[i + 1], arr[i + 1] = arr[i]][0];
swaped = true;
}
}
for (var i = 1; i < arr.length; i += 2) {
if (arr[i] > arr[i + 1]) {
arr[i] = [arr[i + 1], arr[i + 1] = arr[i]][0];
swaped = true;
}
}
}
return arr;
}
var results = oddEvenSort(l)
console.log(results)
|
|
发表于 2014-4-29 08:38:57
