一. 冒泡排序
特点: 依次从头到尾相邻两个元素比较,如果左边比较高,就左右互换,每次遍历总数减去一.即:末尾是当前排序后最大的元素.
算法复杂度: O(n^2)
/**
*@description 冒泡排序
* @param {array} arr
* @returns {array}
*/
function bubblingSort (arr) {
const length = arr.length;
for(var j = length - 1; j >= 0; j--) {
for(var i = 0; i < j; i++) {
let tmp = arr[i];
if(tmp > arr[i+1]) {
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
}
return arr;
}
二.选择排序
特点: 从下标1位置开始,依次将最小值放在最前面,即:第一次遍历完,最小值在第一个位置,第二次遍历完,最小值在第二个位置.依次遍历到完整排序完.
算法复杂度: O(n^2)
/**
*@description 选择排序
* @param {array} arr
* @returns {array}
*/
function selectionSort(arr) {
const length = arr.length;
for(var j = 0; j < length; j++) {
let min = j;
for(var i = j + 1; i < length; i++) {
if (arr[i] < arr[min]) {
min = i;
}
}
if (min != j) {
let tmp = arr[j];
arr[j] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
三.插入排序
特点: 局部有序,从下标为1开始,左边为局部有序(单个元素默认为有序).后续依次比较左边元素,如果比标记值大则右移动.如果比标记值小.则将标记值插入到其后边.
算法复杂度: O(n^2)
/**
*@description 插入排序
* @param {array} arr
* @returns {array}
*/
function insertSort(arr) {
const length = arr.length;
for(var i = 1; i < length; i++) {
let tmp = arr[i];
var j = i;
while(arr[j - 1] > tmp && j > 0 ) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
}
return arr;
}
四.希尔排序
特点: 先分组,比如按照5. 3. 2 1.主要是间隔问题.常规算法,取间距为N/2
也就是说对于N=100的数组,增量间隔序列为 50,25,12,6,3,1
算法复杂度最好情况: O(n^(1.3—2))
/**
*@description 希尔排序
* @param {array} arr
* @returns {array}
*/
function shellSort(arr) {
const length = arr.length;
// 初始化增量
var gap = Math.floor(length / 2)
while(gap >= 1) {
for(var i = gap; i < length; i++) {
var tmp = arr[i];
var j = i;
while(arr[j - gap] > tmp && j > gap - 1) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = tmp
}
gap = Math.floor(gap / 2);
}
return arr;
}
五.快速排序
特点:
算法复杂度: 最好 nlogn 最差 n平方
/**
*@description 快速排序
* @param {array} arr
* @returns {array}
*/
function quickSort(arr) {
// 数组分区, 左小右大
function partition(arr, left, right) {
let storIndex = left;
let pivot = arr[right]; // 直接从右边的元素为基准元素
// [1,2,3,4,5]
for(let i = left; i < right; i++) {
if (arr[i] < pivot) {
let tmp = arr[storIndex];
arr[storIndex] = arr[i];
arr[i] = tmp;
storIndex ++;
}
}
let tmp = arr[storIndex];
arr[storIndex] = arr[right];
arr[right] = tmp;
return storIndex;
}
// 排序主函数
function sort(arr, left, right) {
if(left > right) {
return;
}
let storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
sort(arr,0, arr.length - 1);
return arr;
}
