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

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

举个