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

快速排序、归并排序、堆排序三种排序算法的性能谁最好呢?网上查了一下说快速排序最快、其次是归并排序,最差的是堆排序;而理论上三种排序算法的时间复杂度都是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 }

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

时间: 03-08

快速排序、归并排序、堆排序三种算法性能比较的相关文章

背景建模技术(二):BgsLibrary的框架、背景建模的37种算法性能分析、背景建模技术的挑战

背景建模技术(二):BgsLibrary的框架.背景建模的37种算法性能分析.背景建模技术的挑战 1.基于MFC的BgsLibrary软件下载 下载地址:http://download.csdn.net/detail/frd2009041510/8691475 该软件平台中包含了37种背景建模算法,可以显示输入视频/图像.基于背景建模得到的前景和背景建模得到的背景图像,还可以显示出每种算法的计算复杂度等等.并且,测试的可以是视频.图片序列以及摄像头输入视频.其界面如下图所示: 2.BgsLibr

最近公共祖先(三种算法)

最近研究了一下最近公共祖先算法,根据效率和实现方式不同可以分为基本算法.在线算法和离线算法.下面将结合hihocoder上的题目分别讲解这三种算法. 1.基本算法 对于最近公共祖先问题,最容易想到的算法就是从根开始遍历到两个查询的节点,然后记录下这两条路径,两条路径中距离根节点最远的节点就是所要求的公共祖先. 题目参见 #1062 : 最近公共祖先·一 附上AC代码,由于记录的方式采取的是儿子对应父亲,所以实现的时候有点小技巧,就是对第一个节点的路径进行标记,查找第二个节点的路径时一旦发现访问到

Opencv——彩色图像灰度化的三种算法

为了加快处理速度在图像处理算法中,往往需要把彩色图像转换为灰度图像.24为彩色图像每个像素用3个字节表示,每个字节对应着RGB分量的亮度. 当RGB分量值不同时,表现为彩色图像:当RGB分量相同时,变现为灰度图像: 一般来说,转换公式有3中. (1)Gray(i,j)=[R(i,j)+G(i,j)+B(i,j)]/3; (2)Gray(i,j)=0.299*R(i,j)+0.587*G(i,j)+0.144*B(i,j); (3)Gray(i,j)=G(i,j);//从2可以看出G的分量比较大所

Java利用 DES / 3DES / AES 这三种算法分别实现 对称加密

转载请注明出处:http://blog.csdn.net/smartbetter/article/details/54017759 有两句话是这么说的: 1)算法和数据结构就是编程的一个重要部分,你若失掉了算法和数据结构,你就把一切都失掉了. 2)编程就是算法和数据结构,算法和数据结构是编程的灵魂. 注意,这可不是我说的,是无数程序员总结的,话说的很实在也很精辟,若想长久可持续发展,多研究算法还是很有必要的,今天我给大家说说加密算法中的对称加密算法,并且这里将教会大家对称加密算法的编程使用.包含

字符串匹配的三种算法

下面将介绍三种有关字符串匹配的算法,一种是朴素的匹配算法,时间复杂度为O(mn),也就是暴力求解.这种方法比较简单,容易实现.一种是KMP算法,时间复杂度为O(m+n),该算法的主要任务是求模式串的next数组.另外还有一种对KMP算法的改进,主要是求nextval数组. 第一种朴素的匹配算法: int index(char str[], char subStr[]) { int i = 0, j = 0,index = 0; while (str[i] != '\0' && subStr

Java常用三种算法排序比较

Java常用三种算法排序比较 冒泡排序: package demo1; /** * * @author xiaoye 2014-5-13 */ /** * 有N 个数据需要排序,则从第0 个数开始,依次比较第0 和第1 个数据, * 如果第0 个大于第1 个则两者交换,否则什么动作都不做,继续比较第 1 个第2个-, * 这样依次类推,直至所有数据都"冒泡"到数据顶上. 冒泡排序的效率 O(N*N ),比较 N*N/2 ,交换N*N/4 . */ public class Bubble

缓存算法(FIFO 、LRU、LFU三种算法的区别)

缓存算法(FIFO .LRU.LFU三种算法的区别) FIFO算法# FIFO 算法是一种比较容易实现的算法.它的思想是先进先出(FIFO,队列),这是最简单.最公平的一种思想,即如果一个数据是最先进入的,那么可以认为在将来它被访问的可能性很小.空间满的时候,最先进入的数据会被最早置换(淘汰)掉. FIFO 算法的描述:设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能: set(key,value):将记录(key,value)插入该结构.当缓存满时,将最先进入缓存的数据置

三种Linux性能分析工具的比较

无论是在CPU设计.服务器研发还是存储系统开发的过程中,性能总是一个绕不过去的硬指标.很多时候,我们发现系统功能完备,但就是性能不尽如意,这时候就需要找到性能瓶颈.进行优化.首先我们需要结合硬件特点.操作系统和应用程序的特点深入了解系统内部的运行机制.数据流图和关键路径,最好找出核心模块.建立起抽象模型:接着需要利用各种性能分析工具,探测相关模块的热点路径.耗时统计和占比.在这方面,Linux操作系统自带了多种灵活又具有专对性的工具,此外一些厂家也开源了不少优秀的性能分析工具.下面就结合笔者最近

字符串相似度三种算法介绍

余弦相似度 计算公式为: P(A,B) = sqrt(A × B) / (|A| × |B|) 设有两个字符串: ABCDEFG ABCHIJK 其中共有11个字符,为: A B C D E F G H I J K 如果,不考虑他们之间的关联性以及顺序等隐私,那么可以讲这两个字符串转换成两个11维空间中的向量: {1.1.1.1.1.1.1.0.0.0.0} {1.1.1.0.0.0.0.1.1.1.1} 那,计算他们之间的相似度为: P = sqrt(3) / (sqrt(7) × sqrt(