基本概念
- 算法优劣
稳定性
稳定：如果a原本在b前面，而a=b，排序之后仍然在b的面前
不稳定性：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
- 排序方式
内排序：所有排序操作都在内存中完成，占用常数内存，不占用额外内存。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行，占用额外内存
- 复杂度
时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
冒泡排序
基本思路：它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行指导没有再需要交换，也就是说该数列已经排序完成。
算法：
比较相邻的元素，如果第一个比第二个大，就交换它们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
针对所有的元素重复以上的步骤，除了最后一个
重复步骤1～3，直到排序完成
// 冒泡排序
function bubbleSort(arr) {
let len = arr.length;
// i 控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0 所以i<len-1
for (let i = 0; i < len-1; i++) {
// j 控制比较次数 第i次循环内需要比较的次数为len-i
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let tmp = arr[j + 1]
arr[j + 1] = arr[j];
arr[j] = tmp
}
}
}
console.log(arr.toString())
}
let arr = [3, 15, 36, 26, 27, 2]; //[2, 3, 15, 26, 27, 36]
时间复杂度：
最好的情况是：当数列为由小到大的有序数列，只需要循环一次，比较n
T(n)=O(n)
最坏的则是由大到小： T(n)=O(n^2)
平均时间复杂度： T(n)=O(n^2)
选择排序
原理：在每一次循环内都由一个数去跟所有的数比较一遍，每次比较都选取相对较小的那个数来进行下一次的比较，并不断跟新较小数的下表。这样再一次循环结束时就能得到最小数的下标，再通过一次交换将最小数放在最前面，通过n-1次循环之后完成排序。
// 选择排序
function selectSort(arr) {
let len = arr.length
// i控制循环次数
for (let i = 0; i < len - 1; i++) {
// minIndex 用来保存每次比较后较小数的下标
var minIndex = i
// j 控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面
// 所以下一次循环的时候就可以跳过这个数，因此j应该从i+1开始
for (let j = i+1; j < len; j++) {
// 每比较一次都需要将较小数的下标记录下来
if (arr[minIndex] > arr[j]) {
minIndex = j
}
}
// 当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置
if(minIndex!=i){
let tmp = arr[i]
arr[i] = arr[minIndex];
arr[minIndex] = tmp
}
}
console.log(arr.toString())
}
let arr = [3, 15, 36, 26, 27, 2]; //[2, 3, 15, 26, 27, 36]
selectSort(arr)
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。
选择排序每次交换一对元素，它们当中至少有一个被移到其最终位置上，因此对n个元素的表进行n排序之多进行n-1次交换。
最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
插入排序
原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
// 插入排序
function insertSort(arr){
let len = arr.length
// i控制循环次数，因为已经默认第一个数是正确的。
for(let i=1;i<len;i++) {
//变量j用来记录即将要排序的数的位置
var j=i;
//target用来记录即将要排序的那个数的值即目标值
var target=arr[j];
//while循环用来为目标值在已经排好序的数中找到合适的位置，
//因为是从后向前比较，并且是与j-1位置的数比较，所以j>0
while(j>0 && target<arr[j-1]) {
//当目标数的值比它当前位置的前一个数的值小时，将前一个数的位置向后移一位。
//并且j--使得目标数继续与下一个元素比较
arr[j]=arr[j-1];
j--;
}
//更目标数的位置。
arr[j]=target;
//打印每次循环结束之后数组的排序状态（方便理解）
console.log("第"+i+"次循环之后效果："+arr.toString());
}
console.log(arr.toString())
}
let arr = [15, 3, 36, 26, 27, 2]; //[2, 3, 15, 26, 27, 36]
insertSort(arr)
