Javascript

排序算法(js版本)

本文主要是介绍排序算法(js版本),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

1.冒泡

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

未优化

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 ,选择适当的位置插入。
image

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版本)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!