当前位置:   article > 正文

常见七种排序算法简析&算法复杂度分析_几种排序算法的差别寄复杂度

几种排序算法的差别寄复杂度

1.选择排序
选择排序,顾名思义,就是每次选择第i大(第i小)

for(int i=1;i<=n;i++){
   int minn=inf,k;
   for(int j=i;j<=n;j++)
     if(a[j]<minn) minn=a[j],k=j;
   swap(a[j],a[k]);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+…+1=n*(n-1)/2
所以复杂度很稳定,总是O(n^2)

2.冒泡排序
很经典的算法,每次循环比较相邻两个元素的大小,如果后一个较小,那么交换,可以想象就像吐泡泡一样,最小的被不停交换到最上面

//没有任何优化版本的冒泡排序
  for(i=1;i<=n;i++)
        for(j=0;j<n-i-1;j++)
            if(a[j]>a[j+1])
              swap(a[j],a[j+1]);
  • 1
  • 2
  • 3
  • 4
  • 5

优化一:
当已经全部有序时,结束排序

for(i=1;i<=n;i++){
        for(j=1;j<n-i;j++){
            int tmp=0;
            if(a[j]>a[j+1]){
              tmp=1;
              swap(a[j],a[j+1]);
            }
        }
       if(tmp==0) break;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

优化二:每次记录下上一次最后交换的位置

int last=n-1;
for(i=1;i<=n;i++){
        int tmp=0;
        for(j=0;j<last;j++){
            if(a[j]>a[j+1]){
             tmp=1;
              swap(a[j],a[j+1]);
              last=j;
            }
        }
       if(tmp==0) break;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.插入排序
取出下一个元素,在已经排序的元素序列中从后向前扫描,每次寻找元素应该被插入的位置。

 for (i = 1; i < n; i++){
     pos = i -1 ;   
     cur = num[i];
     while ( pos >= 0 && num[pos] > cur){
           num[pos + 1] = num[pos];
           pos--;
     }
     num[pos + 1] = cur; 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

时间复杂度为O(n^2)
特殊的,当元素大小都相同时,时间复杂度为O(n)
(因为每次都在自己的位置上,相当于序列扫一遍)
4.合并排序
其实也叫归并排序,先将无序序列利用二分法划分为子序列,直至每个子序列只有一个元素时,然后再对有序子序列逐步(两两)进行合并排序。(本质上是分治和递归的应用)

//板子不在这个电脑上,下次一定.jpeg
  • 1

时间复杂度:
两个子序列已经排序完毕,总的时间复杂度就是两个序列的时间复杂度+合并的复杂度,因为两边分别已经排好了,所以扫一遍看插入位置就可以了
所以 T(n)=2T(n/2)+θ(n)
T(n)=O(nlogn)
(元素相同的时候也没有什么区别
5.快速排序

sort(a+1,a+n+1);//狗头保命
  • 1

哦豁豁,优质算法2333
本质上还是分治(分治大法好)
找一个基准值(x),left、right分别是左右断点
1’ 从right往前找,找到第一个比x小的元素,使得a[left]=a[right],right–
2’从left往后找,找到第一个比x大的元素,使得a[right]=a[left],left++
3’循环往复,直到left==right,a[left]=x,over

举个

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/632368
推荐阅读
相关标签