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

```  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 }```

## 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