排序算法（js版本）

标签：ima   选择排序   大于等于   之间   作用域   amp   额外   就是   pre   

几个概念
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 

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

for (let i = 0; i  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=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

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

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

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

排序算法（js版本）

标签：ima   选择排序   大于等于   之间   作用域   amp   额外   就是   pre   

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