冒泡排序
排序的效果图
解法
当前解法为升序
冒泡排序的特点，是一个个数进行处理。第i个数，需要与后续的len-i-1个数进行逐个比较。
为什么是 len-i-1个数？
因为数组末尾的i个数，已经是排好序的，确认位置不变的了。
为什么确认位置不变，因为它们固定下来之前，已经和前面的数字都一一比较过了。
function bubbleSort(arr){
const len = arr.length;
for(let i = 0; i < len - 1; i++){
for(let j = 0; j < len - i - 1; j++){
if(arr[j] > arr[j+1]){
const tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
return arr;}
复制代码
快速排序
概要
快速排序，使用的是分治法的思想。
通过选定一个数字作为比较值，将要排序其他数字，分为 >比较值 和 <比较值，两个部分。并不断重复这个步骤，直到只剩要排序的数字只有本身，则排序完成。
效果图
解法
function quickSort(arr){
sort(arr, 0, arr.length - 1);
return arr;
function sort(arr, low, high){
if(low >= high){
return;
}
let i = low;
let j = high;
const x = arr[i]; // 取出比较值x，当前位置i空出，等待填入
while(i < j){
// 从数组尾部，找出比x小的数字
while(arr[j] >= x && i < j){
j--;
}
// 将空出的位置，填入当前值， 下标j位置空出
// ps：比较值已经缓存在变量x中
if(i < j){
arr[i] = arr[j]
i++;
}
// 从数组头部，找出比x大的数字
while(arr[i] <= x && i < j){
i++;
}
// 将数字填入下标j中，下标i位置突出
if(i < j){
arr[j] = arr[i]
j--;
}
// 一直循环到左右指针i、j相遇，
// 相遇时，i==j, 所以下标i位置是空出的
}
arr[i] = x; // 将空出的位置，填入缓存的数字x，一轮排序完成
// 分别对剩下的两个区间进行递归排序
sort(arr, low, i - 1);
sort(arr, i+1, high);
}}
复制代码
希尔排序
概要
希尔排序是一种插入排序的算法，它是对简单的插入排序进行改进后，更高效的版本。由希尔（Donald Shell）于1959年提出。
特点是利用增量，将数组分成一组组子序列，然后对子序列进行插入排序。
由于增量是从大到小，逐次递减，所以也称为缩小增量排序。
效果图
解法
注意点
插入排序时，并不是一个分组内的数字一次性用插入排序完成，而是每个分组交叉进行。
执行插入时，使用交换法
function shellSort(arr){
// 分组规则 gap/2 递减
for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
for(let i = gap; i < arr.length; i++){
let j = i;
// 分组内数字，执行插入排序，
// 当下标大的数字，小于 下标小的数字，进行交互
// 这里注意，分组内的数字，并不是一次性比较完，需要i逐步递增，囊括下个分组内数字
while(j - gap >= 0 && arr[j] < arr[j - gap]){
swap(j, j-gap);
j = j - gap;
}
}
}
return arr;
function swap(a, b){
const tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}}
复制代码
执行插入时，使用移动法
function shellSort(arr){
for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
for(let i = gap; i < arr.length; i++){
let j = i;
const x = arr[j]; // 缓存数字，空出位置
while(j - gap >= 0 && x < arr[j-gap]){
arr[j] = arr[j - gap]; // 将符合条件的数字，填入空出的位置
j = j - gap;
}
arr[j] = x; // 最后，将缓存的数字，填入空出的位置
}
}
return arr;}
复制代码
