-
冒泡排序：
原理：比较两个相邻的元素，将值大的元素交换至右端。
思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function bubbleSort(arr) {
let len = arr.length;
if(len >= 1) {
for(let i = 0;i < len - 1; 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;
}
console.log(bubbleSort(arr));
冒泡排序优化版：
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function bubbleSort(arr) {
let len = arr.length;
let lastExchangeIndex = 0;
//无序数列的边界，每次比较只需要比到这里为止
let sortBorder = len - 1;
if(len >= 1) {
for(let i = 0;i < len; i++) {
//有序标记，每一轮的初始是true
let isSorted = true;
for(let j = 0;j < sortBorder - i; j++) {
if(arr[j] > arr[j + 1]) {
let temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
//有元素交换，所以不是有序，标记变为false
isSorted = false;
//把无序数列的边界更新为最后一次交换元素的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if(isSorted) { //有序,跳出循环
break;
}
}
}
return arr;
}
console.log(bubbleSort(arr));
-
选择排序：
一.选择排序原理
1.每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到刚才已排序序列的后面。
3.以此类推，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。例如：序列3，3，2，1， 我们知道第一次遍历的时候，选择最后一个元素1和第一个元素3交换，那么原序列中2个3的相对前后顺序就和之前不一样了，所以选择排序不是一个稳定的排序算法。
二.选择排序时间复杂度
第一次循环比较 n - 1次，第二次循环比较 n - 2次，依次类推，最后一个元素不需要比较，因此共进行 n - 1次循环，最后一次循环比较1次。
因此一共比较1 + 2 + 3 + ... +（n - 2）+（n - 1）次，求和得n2/2 - n / 2 ，忽略系数，取最高指数项，该排序的时间复杂度为O(n2)
const arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
function selectionSort(arr) {
let len = arr.length;
let minIndex, temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
// 寻找最小的数
minIndex = j;
// 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
console.log(selectionSort(arr));
选择排序优化版：
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function selectionSort(arr) {
let len = arr.length;
let left = 0;
let right = len - 1;
while (left < right) {
let max = left;//记录无序区最大元素下标
let min = left;//记录无序区最小元素下标
let j = 0;
for (j = left + 1; j <= right; j++) {
//找最大元素下标
if (arr[j] < arr[min])
{
min = j;
}
//找最小元素下标
if (arr[j] > arr[max])
{
max = j;
}
}
//最小值如果是第一个则没有必要交换
if (min != left) {
let tmp = arr[left];
arr[left] = arr[min];
arr[min] = tmp;
}
//这里很重要，如果最大元素下标是left,前面已经和最小元素交换了，此时最大元素下标应该是min
if (max == left) {
max = min;
}
//最大值如果是最后一个则没必要交换
if (max != right) {
let tmp = arr[right];
arr[right] = arr[max];
arr[max] = tmp;
}
left++;
right--;
}
return arr;
}
console.log(selectionSort(arr));
插入排序：
const arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
function insertSort(arr) {
const len = arr.length;
let preIndex, current;
for (let 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;
}
console.log(insertSort(arr));
