Js排序算法
/**
* 1、冒泡排序
* 特点：
* 采用双循环遍历计算，按照数组索引依次遍历，每次将相邻元素两两对比，实现元素交换；
* 稳定，也是一种优化算法。
*/
public bubbleSort(arr:any) {
for (let i = 0; i < arr.length; i++) {
// - 1 => 最后一次无元素对比；
// - i => 只遍历当前数组 i 之后的所有元素；
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // 由小到大
// let temp:any = arr[j + 1]; // 元素交换
// arr[j + 1] = arr[j];
// arr[j] = temp;
arr[j] = [arr[j + 1], arr[j + 1] = arr[j]][0];
}
}
}
return arr;
}
/**
* 2、选择排序
* 特点：
* 采用双循环遍历计算，外层循环按照索引依次遍历，内层循环取外层当前元素后面的数据依次遍历，取外层每次遍历的参数，与内层循环遍历的参数对比，实现元素交换；
* 思路清晰，但是适用于数据规模小的数组。
*/
public selectionSort(arr:any) {
let minIdx:any;
let temp:any;
for (let i = 0; i < arr.length - 1; i++) { // 最后一次无需参数对比
minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIdx] > arr[j]) {
minIdx = j;
}
}
temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
return arr;
}
/**
* 2、插入排序
* 特点：
* 拆半插入
* 采用双循环遍历计算，外层循环按照索引依次遍历，内层循环取外层当前元素后面的数据依次遍历，取外层每次遍历的参数，与内层循环遍历的参数对比，实现元素交换；
* 思路清晰，但是适用于数据规模小的数组。
*/
// public insertionSort(arr:any) {
// let minIdx:any;
// let temp:any;
// for (let i = 0; i < arr.length - 1; i++) { // 最后一次无需参数对比
// minIdx = i;
// for (let j = i + 1; j < arr.length; j++) {
// if (arr[minIdx] > arr[j]) {
// minIdx = j;
// }
// }
// temp = arr[i];
// arr[i] = arr[minIdx];
// arr[minIdx] = temp;
// }
// return arr;
// }
public insertionSort(arr: any) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
/**
* 归并排序（分治法）
* 特点：自上而下的递归，自下而上的迭代
* 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
* 解决（Conquer）：用合并排序法对两个子序列递归的排序。
* 合并（Combine）：合并两个已排序的子序列已得到排序结果。
*/
public mergeSort(arr: any):any {
if (arr.length < 2) {
return arr;
}
let middle:any = Math.floor(arr.length / 2);
let left:any = arr.slice(0, middle);
let right:any = arr.slice(middle);
return this.merge(this.mergeSort(left), this.mergeSort(right));
}
public merge(left:any, right:any) {
let result:any = [];
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());
return result;
}
