数据结构与算法-排序篇

//插入排序

function insertionSort(array) {
for (var i = 1; i < array.length; i++) { 　　　　var key = array[i]; 　　　　var j = i - 1; 　　　　while ( array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}
var arr=[6,764,38,56,77,78,53,27,2,46,4,19,54,48];
console.log(insertionSort(arr));

//冒泡

function maopao(arra){
var temp;
for(var i=0;i<arra.length;i++){ //比较多少趟，从第一趟开始

for(var j=0;j<arra.length-i-1;j++){ //每一趟比较多少次数 if(arra[j]>arra[j+1]){
temp=arra[j];
arra[j]=arra[j+1];
arra[j+1]=temp;
}
}
};
return arra;
}
var arrry=[6,764,38,56,77,78,53];
var s=maopao(arrry);

//选择排序

function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
var arr=[6,764,38,56,77,78,53,27,2,46,4,19,54,48];

//希尔排序

function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/5) { //动态定义间隔序列 　　　　gap =gap*5+1; 　　} 　　for (gap; gap > 0; gap = Math.floor(gap/5)) {
for (var i = gap; i < len; i++) { 　　　　　　temp = arr[i]; 　　　　　　for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
var arr=[6,764,38,56,77,78,53,27,2,46,4,19,54,48];

//归并排序
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length){
result.push(left.shift());
}
while (right.length){
result.push(right.shift());
}
console.timeEnd(‘归并排序耗时’);
return result;
}
var arr=[6,764,38,56,77,78,53,27,2,46,4,19,54,48];