排序算法（js版本）

几个概念
1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序：需要利用额外的数组来辅助排序。

1.冒泡

思想：把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置….

未优化

int [] arry={2,4,1,0,8,5};
      int n=arry.length;
      int temp;
      for (int i = 0; i <n ; i++) { //  从0-i有序
            for (int j = 0; j <n-i-1 ; j++) {
                if (arry[j]<arry[j+1]){
                    temp=arry[j];
                    arry[j]=arry[j+1];
                    arry[j+1]=temp;
                }
            }
        }

优化
相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了.

for (let i = 0; i < a.length; i++) {
    let flag = false;
    let temp;
    for (let j = 0; j < a.length - i - 1; j++) {
        if (a[j] > a[j + 1]) {
            flag = true;
            temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp
        } 
    }
     //如果没有交换，直接退出循环
     if (!flag) {
        break;
    }
}

插入排序

思路：
1、从数组第2个元素开始抽取元素。

2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。

3、继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。

let a = [1,4,5,1,2,9,0,3];
for(let i=1;i<a.length;i++){
    for(let j=i-1;j>=0 && a[j]>a[j+1]; j--){
    //这里用了解构来交换值
      [a[j],a[j+1]]=[a[j+1],a[j]];
    }
}

性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序
注意这里不能自己写个swap（）函数来交换，牵扯到作用域的问题。
交换两个值有很多方法！

3.选择排序

思路：
1.在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置
2.再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。
3.以此类推，直到所有元素均排序完毕。

let a = [1,4,5,1,2,9,0,3];
let min;//无序区的最小值
let i;//有序区的末尾位置
let j;//无序区的开始位置
for( i=0;i<a.length;i++){
     min=i;
     //找出a[i+1]-a[n]之间最小的元素
     for(j=i+1;j<a.length;j++){
        if(a[j]<a[min]){
            //更新无序区最小值的位置
            min=j;
        }
     }
     //若min!=i，则交换 a[i] 和 a[min]。
     //交换后，保证了a[0]..a[i]之间元素有序
     if(min!=i){
        [a[min],a[i]]=[a[i],a[min]];
     }
    
}

性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 4、原地排序
稳定性得具体问题具体分析
不同的实现方法有不同的结果.

• 如果是在数组中交换,那么就有可能不稳定,如{5,5,2}
• 如果是链表或者开一个新的数组（自然不会破坏相同元素的相对位置）,那么又是稳定的。
  则可以这样说，当空间复杂度为O(1)的时候，是不稳定的。

《算法》p217,有提到，有很多办法可以将任意排序算法变成稳定的，但是，往往需要额外的时间或者空间。

排序算法（js版本）

原文地址：https://www.cnblogs.com/My-Coding-Life/p/14802399.html