- 冒泡排序
比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至 正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0;i<len;i++) {
for (var j = 0;j<len-1-i;j++) {
if(arr[j] > arr[j+1]){
var temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
let arr = [8,2,9,10,12,11,3]
console.log(bubbleSort(arr))
屏幕快照 2018-12-23 上午1.42.10.png
- 选择排序
选择排序算法是一种原址比较排序算法。
思路是：找到数据结构中的最小值并 将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。
屏幕快照 2018-12-23 上午1.43.30.png
function selectionSort(arr) {
let indexMin;
for (let i = 0; i < arr.length - 1; i++){
indexMin = i
for (var j = i; j < arr.length; j++){
if(arr[indexMin] > arr[j]) {
indexMin = j
}
if (i !== indexMin){
let aux = arr[i]
arr[i] = arr[indexMin]
arr[indexMin] = aux
}
}
return arr
}
let arr = [44,38,5,47,15]
-
合并排序（分治策略）
归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
屏幕快照 2018-12-23 下午3.27.44.png
屏幕快照 2018-12-23 下午3.32.27.png
屏幕快照 2018-12-23 下午6.01.01.png
let arr = [44,38,5,47,15]
// 合并两个有序数组
function merge(A,p,q,r){
// A:数组
// p:左半边开始位置
// q:左半边结束,右半边开始位置
// r:右半边结束
let A1 = a.slice(p,q); // 存放左半边的临时空间
let A2 = a.slice(q,r); // 存放右半边的临时空间
A1.push(Number.MAX_SAFE_INTEGER);
A2.push(Number.MAX_SAFE_INTEGER);
for(let k = p , i = 0 , j = 0 ; k < r; k++ ){
// k : 下一个写入位置
// i : A1中回写位置
// j : A2中回写位置
A[k] = A1[i] < A2[j] ? A1[i++] : A2[j++]
}
}
function merge_sort(A,p,r){
// p : 开始位置
// r : 结束位置
if( r - p < 2 ) { return };
const q = Math.ceil( ( p + r ) / 2 );
// 排左半边
merge_sort(A,p,q);
// 排右半边
merge_sort(A,q,r);
// 合并两个有序数组
merge(A,p,q,r);
}
-
快速排序
屏幕快照 2018-12-23 下午8.44.13.png
屏幕快照 2018-12-23 下午9.47.00.png
function merge_sort(A,p,r){
// p : 开始位置
// r : 结束位置
if( r - p < 2 ) { return };
const q = Math.ceil( ( p + r ) / 2 );
// 排左半边
merge_sort(A,p,q);
// 排右半边
merge_sort(A,q,r);
// 合并两个有序数组
merge(A,p,q,r);
}
function swap(A,i,j){
[A[i],A[j]] = [A[j],A[i]]
}
function partition(A,lo,hi){
// lo : 开始位置
// hi : 结束位置
// 找中间点,最后一位
let pivot = A[hi-1];
let i = lo,j = hi-1;
//小于中心点范围：[lo,i]
//未确认范围：[i,j]
//大于中心点范围：[j,hi-1]
while( i !== j){
// 左边小于中心数字，左指针往后走
if(A[i] <= pivot){
i++
}else{ // 否则就交换位置，j往前
swap(A,i,j--)
}
}
swap(A,j,--j)
// 返回中心点位置
return j
}
function qsort(A,lo = 0,hi = A.length){
if(hi-lo <= 1) return
const p = partition(A,lo,hi)
qsort(A,lo,p);
qsort(A,p+1,hi);
}
