1. 冒泡排序
/*
算法描述
1.比较相邻元素，若第一个大于第二个，交换他们。
2.重复第一步，最后的数将会最大。
3.重复以上步骤，除了最后一个数
4.继续重复以上步骤，直到没有任何一对数需要比较。
*/
function bubbleSort(arr) { //参数：数组;返回值。
var len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len -1 - i; j++) {
if (arr[j] > arr[j + 1]) { //相邻两个元素比较
let temp = arr[j + 1]; //元素交换
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr; //返回排完序数组
}
alert(bubbleSort([21,78,15,36,59,11,34,25,13])); //11,13,15,21,25,34,36,59,78
2.快速排序
/*
快排算法描述
1.找基准点。
2.建立两个空数组。
3.arr中大于基准点放left,则反之。
4.left,基准点，right连接起来。
*/
function quicksort(arr) { //参数类型：数组；返回值，数组。
if (arr.length <= 1) {
return arr;
}
var equally = Math.floor(arr.length / 2); //arr中间索引
var benchmark = arr.splice(equally,1); //arr中间值
var left = [];
var right = [];
for (var i = 0,len = arr.length; i < len; i++) {
if (arr[i] < benchmark) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quicksort(left).concat([benchmark],quicksort(right)); //不断递归，最后都递归为一个数，然后拼接数组，返回排完序数组。
}
alert(quicksort([21,81,12,85,31,97,18,2,87,75,3])); //output:2,3,12,18,21,31,75,81,85,87,97
3.选择排序
/*
算法描述
1.与第一个数比较，如果大于它，则交换位置
2.重复第一步，一遍循环，第一个数是最小值；
3.重复n-1次循环，OK。
*/
function selectSort(arr) { //参数：数组；返回值：数组。
var len = arr.length;
var temp;
for (var i = 0; i < len - 1; i++) {
for (var j = j + 1; j < len; j++) {
if (arr[j] < arr[i]) { //与第一个数比较
temp = arr[j]; //交换位置
arr[j] = arr[i];
arr[i] = temp;
}
}
}
return arr; //返回数组
}
alert(selectSort([14,52,18,78,54,114,65,28,56])); //14,52,18,78,54,114,65,28,56
4.插入排序
/*
算法描述
1.第一个数a[0]与第二个数a[1]比较，若a[0] > a[1],则 a[1] = a[0]
2.关键是第三个数a[2],a[2]先与a[1]，若a[2] < a[1],则交换位置，此时a[1]再与a[0]比较大小。
*/
function insertSort(arr) { //参数：数组；返回值：数组。
for (let i = 1,len = arr.length; i < len;i++) {
for (let j = i - 1; j >= 0;j--) { //j--：若a[2] < a[1],指针退1。
if (arr[j] > arr[j + 1]) { //比较相邻两数大小
let temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr; //返回数组
}
alert(insertSort([12,85,42,67,34,56,19,97,47])); //12,19,34,42,47,56,67,85,97
5.归并排序
/*
算法描述
1.把arr分成left,right子序列;
2.比较left,right大小，返回排完序数组，递归两次；
3.递归与栈相关，弹出并返回的值执行其他动作。
*/
function mergeSort(arr) { //参数类型：数组；返回：数组。
if (arr.length < 2) {
return arr;
}
const middle = Math.floor(arr.length / 2); //中间值
const left = arr.slice(0,middle); //left[]
const right = arr.slice(middle); //right[]
return merge(mergeSort(left),mergeSort(right)); //递归两次
}
function merge(left,right) {
var newArr = [];
while (left.length && right.length) {
if (left[0] < right[0]) { //子序列比较大小
newArr.push(left.shift());
} else {
newArr.push(right.shift());
}
}
return newArr.concat(left,right); //返回合并好的了子序列
}
alert(mergeSort([54,24,15,95,75,35,68,78,12,31,108])); //12,15,24,31,35,54,68,75,78,95,108