快速排序、归并排序、堆排序三种算法性能比较

时间:2021-01-20 20:07:46

快速排序、归并排序、堆排序三种排序算法的性能谁最好呢?网上查了一下说快速排序最快、其次是归并排序,最差的是堆排序;而理论上三种排序算法的时间复杂度都是O(nlogn),只不过快速排序最差的会达到O(n^2),但是数据的随机性会消除这一影响,今天就来实际比较一下:

  1 #include <iostream>
  2 #include<time.h>
  3 using namespace std;
  4 #define MAX 100000000
  5 int data1[MAX],data2[MAX],data3[MAX],temp[MAX];
  6  //快速排序
  7 void QuickSort(int data[],int i,int j)
  8 {
  9     if(i>=j) return;
 10     int low = i;
 11     int high = j;
 12      int key = data[low];
 13      while(low<high)
 14      {
 15            while(high>low && data[high]>=key) --high;
 16            data[low] = data[high];
 17            while(low<high && data[low]<key) ++low;
 18            data[high] = data[low];
 19      }
 20      data[low] = key;
 21      QuickSort(data,i,low-1);
 22      QuickSort(data,low+1,j);
 23 }
 24 //归并排序
 25 
 26 void MergeJudge(int data[],int first,int mid,int last,int temp[])
 27 {
 28        int k=0;
 29        int i=first,j = mid+1;
 30        while(i<=mid && j<=last)
 31        {
 32            if(data[i] < data[j])
 33                temp[k++] = data[i++] ;
 34            else
 35                temp[k++] = data[j++] ;
 36        }
 37        while(i<=mid) temp[k++] = data[i++];
 38        while(j<=last) temp[k++] = data[j++];
 39        for(int i = 0;i<k;i++) data[first+i] = temp[i];
 40 }
 41 
 42 void MergeSort(int data[],int first,int last,int temp[])
 43 {
 44     if(first>=last) return;
 45     int mid = (first + last) /2;
 46     MergeSort(data,first,mid,temp);
 47     MergeSort(data,mid+1,last,temp);
 48     MergeJudge(data,first,mid,last,temp);
 49 }
 50 
 51 inline void swap(int& a,int& b)
 52 {
 53     int t = a;
 54     a = b;
 55     b = t;
 56 }
 57 //堆排序
 58 void HeapJudge(int data[],int index,int n)
 59 {
 60     while(index<n)
 61     {
 62           int left = index * 2 + 1;
 63           int right = index * 2 + 2;
 64           int max = index;
 65           if(left<n && data[max] < data[left])  max = left;
 66           if(right<n && data[max] < data[right]) max = right;
 67           if(max == index) break;
 68           swap(data[max],data[index]);
 69           index = max;
 70     }                                                       
 71 }
 72 
 73 
 74 
 75 void HeapSort(int data[],int n)
 76 {
 77      for(int i=n/2-1 ; i>=0 ; i--)
 78      {
 79          HeapJudge(data,i,n);
 80      }
 81      for(int i = n-1;i>=0;i--)
 82      {
 83          swap(data[0],data[i]);
 84          HeapJudge(data,0,i);
 85      }
 86 }
 87 
 88 void print(int data[],int n)
 89 {
 90     for(int i=0;i<n;i++)
 91     {
 92         printf("%d ",data[i]);
 93     }
 94     printf("\n");
 95 }
 96 bool check(int data[],int n)
 97 {
 98      for(int i=0;i<n-1;i++)
 99      {
100          if(data[i]>data[i+1]) return false;
101      }
102      return true;
103 }
104 int main()
105 {
106 srand(unsigned int(time(0)));
107     while(1)
108     {
109 
110        int n;
111        scanf("%d",&n);
112        for(int i=0;i<n;i++)
113        {
114            data1[i] = rand();
115            data2[i]=data1[i];
116            data3[i]=data1[i];
117        }
118       printf("数据数量:%d\n",n);
119       double start = clock();
120       QuickSort(data1,0,n-1);
121       double end = clock();
122       if(n<=10) print(data1,n);
123       printf("快速排序:%.02lf ms\n",end-start);
124       if(!check(data1,n)) printf("快速排序出错!");
125 
126       start = clock();
127       MergeSort(data2,0,n-1,temp);
128       end = clock();
129       if(n<=10) print(data2,n);
130       printf("归并排序:%.02lf ms\n",end-start);
131       if(!check(data2,n)) printf("归并排序出错!");
132 
133       start = clock();
134       HeapSort(data3,n);
135       end = clock();
136       if(n<=10) print(data3,n);
137       printf("堆排序:%.02lf ms\n",end-start);
138       if(!check(data3,n)) printf("堆排序出错!");
139     }
140 
141       return 0;
142 }

快速排序、归并排序、堆排序三种算法性能比较

快速排序、归并排序、堆排序三种算法性能比较

快速排序、归并排序、堆排序三种算法性能比较

从上面数据可以看得出来:在数据量小的时候快速排序当属第一,堆排序最差,但随着数据的不断增大归并排序的性能会逐步赶上并超过快速排序,性能成为三种算法之首。可能在数据量大到一定数量时,快速排序的堆栈开销比较大,所以在性能上大打折扣,甚至堆排序的性能也能好过它,但总体上来说快速排序表现的还是比较优秀的。