各种排序算法的比较次数

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

借助比较的排序每次比较贡献O(1)的复杂度

插入排序   最少n-1 最多n(n-1)/2

冒泡排序   最少n-1 最多n(n-1)/2

选择排序   n(n-1)/2

快速排序   

  1. int partition(int *arr , int low , int high)  
  2. {  
  3.     int pivo = arr[low];  
  4.     while(low < high)  
  5.     {  
  6.         while(low < high && arr[high] >= pivo)  
  7.             –high;  
  8.         arr[low] = arr[high];  
  9.         while(low < high && arr[low] <= pivo)  
  10.             ++low;  
  11.         arr[high] = arr[low];  
  12.     }  
  13.     arr[low] = pivo;  
  14.     return low;  
  15. }  
  16.   
  17. // 快速排序 递归  
  18. void qsort(int *arr , int low , int high)  
  19. {  
  20.     if(low < high)  
  21.     {  
  22.         int pivo = partition(arr , low , high);  
  23.         qsort(arr , low , pivo-1);  
  24.         qsort(arr , pivo+1 , high);  
  25.     }  
  26. }  

分析:在递归部分由于递归深度可为logn — n,故递归部分的比较次数为logn — n,partition部分的比较次数与数据分布有关,大约为n次,还需进一步分析。。。

总共比较次数nlogn — n^2

希尔排序   ??

归并排序  在每一次二路归并的过程中,对于N个元素:当一个数组的最小元素比另一数组的最大元素还大时;若两个数组元素交替增长,比较次数最多,为2N-1

再加上递归深度logN,故比较次数为 NlogN — (2N-1)logN

堆排序  ??

点这里可以跳转到人工智能网站

发表评论