1.算法排序
a.插入排序
var arr = [23,34,3,4,23,44,333,444];
var arrShow = (function insertionSort(array){
if(Object.prototype.toString.call(array).slice(8,-1) ==='Array'){
for (var i = 1; i < array.length; i++) {
var key = array[i];
var j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}else{
return 'array is not an Array!';
}
})(arr);
console.log(arrShow);//[3, 4, 23, 23, 34, 44, 333, 444]
b.二分插入排序
function binaryInsertionSort(array) {
if (Object.prototype.toString.call(array).slice(, -) === 'Array') {
for (var i = ; i < array.length; i++) {
var key = array[i], left = , right = i - ;
while (left <= right) {
var middle = parseInt((left + right) / );
if (key < array[middle]) {
right = middle - ;
} else {
left = middle + ;
}
}
for (var j = i - ; j >= left; j--) {
array[j + ] = array[j];
}
array[left] = key;
}
return array;
} else {
return 'array is not an Array!';
}
}
c.选择排序
function selectionSort(array) {
if (Object.prototype.toString.call(array).slice(, -) === 'Array') {
var len = array.length, temp;
for (var i = ; i < len - ; i++) {
var min = array[i];
for (var j = i + ; j < len; j++) {
if (array[j] < min) {
temp = min;
min = array[j];
array[j] = temp;
}
}
array[i] = min;
}
return array;
} else {
return 'array is not an Array!';
}
}
d、冒泡排序
function bubbleSort(array) {
if (Object.prototype.toString.call(array).slice(, -) === 'Array') {
var len = array.length, temp;
for (var i = ; i < len - ; i++) {
for (var j = len - ; j >= i; j--) {
if (array[j] < array[j - ]) {
temp = array[j];
array[j] = array[j - ];
array[j - ] = temp;
}
}
}
return array;
} else {
return 'array is not an Array!';
}
}
e、快速排序
//方法一
function quickSort(array, left, right) {
if (Object.prototype.toString.call(array).slice(, -) === 'Array' && typeof left === 'number' && typeof right === 'number') {
if (left < right) {
var x = array[right], i = left - , temp;
for (var j = left; j <= right; j++) {
if (array[j] <= x) {
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
quickSort(array, left, i - );
quickSort(array, i + , right);
};
} else {
return 'array is not an Array or left or right is not a number!';
}
}
var aaa = [, , , , ];
quickSort(aaa, , aaa.length - );
console.log(aaa); //方法二
var quickSort = function(arr) {
if (arr.length <= ) { return arr; }
var pivotIndex = Math.floor(arr.length / );
var pivot = arr.splice(pivotIndex, )[];
var left = [];
var right = [];
for (var i = ; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
f、堆排序
/*方法说明：堆排序
@param array 待排序数组*/
function heapSort(array) {
if (Object.prototype.toString.call(array).slice(, -) === 'Array') {
//建堆
var heapSize = array.length, temp;
for (var i = Math.floor(heapSize / ); i >= ; i--) {
heapify(array, i, heapSize);
} //堆排序
for (var j = heapSize - ; j >= ; j--) {
temp = array[];
array[] = array[j];
array[j] = temp;
heapify(array, , --heapSize);
}
} else {
return 'array is not an Array!';
}
}
/*方法说明：维护堆的性质
@param arr 数组
@param x 数组下标
@param len 堆大小*/
function heapify(arr, x, len) {
if (Object.prototype.toString.call(arr).slice(, -) === 'Array' && typeof x === 'number') {
var l = * x, r = * x + , largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
heapify(arr, largest, len);
}
} else {
return 'arr is not an Array or x is not a number!';
}
}
h、归并排序
function mergeSort(array, p, r) {
if (p < r) {
var q = Math.floor((p + r) / );
mergeSort(array, p, q);
mergeSort(array, q + , r);
merge(array, p, q, r);
}
}
function merge(array, p, q, r) {
var n1 = q - p + , n2 = r - q, left = [], right = [], m = n = ;
for (var i = ; i < n1; i++) {
left[i] = array[p + i];
}
for (var j = ; j < n2; j++) {
right[j] = array[q + + j];
}
left[n1] = right[n2] = Number.MAX_VALUE;
for (var k = p; k <= r; k++) {
if (left[m] <= right[n]) {
array[k] = left[m];
m++;
} else {
array[k] = right[n];
n++;
}
}
}
g、桶排序
/*方法说明：桶排序
@param array 数组
@param num 桶的数量*/
function bucketSort(array, num) {
if (array.length <= ) {
return array;
}
var len = array.length, buckets = [], result = [], min = max = array[], regex = '/^[1-9]+[0-9]*$/', space, n = ;
num = num || ((num > && regex.test(num)) ? num : );
for (var i = ; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
}
space = (max - min + ) / num;
for (var j = ; j < len; j++) {
var index = Math.floor((array[j] - min) / space);
if (buckets[index]) { // 非空桶，插入排序
var k = buckets[index].length - ;
while (k >= && buckets[index][k] > array[j]) {
buckets[index][k + ] = buckets[index][k];
k--;
}
buckets[index][k + ] = array[j];
} else { //空桶，初始化
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
return result;
}
i、计数排序
function countingSort(array) {
var len = array.length, B = [], C = [], min = max = array[];
for (var i = ; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
C[array[i]] = C[array[i]] ? C[array[i]] + : ;
}
for (var j = min; j < max; j++) {
C[j + ] = (C[j + ] || ) + (C[j] || );
}
for (var k = len - ; k >=; k--) {
B[C[array[k]] - ] = array[k];
C[array[k]]--;
}
return B;
}
j、js自带的函数sort
arr.sort(function(a,b){
return a-b;
})
<script>
var arr = [,,,,,,,];
arr.sort(function(a,b){
return a-b;
})
console.log(arr);
</script>