快速排序、堆排序、希尔排序、冒泡排序、选择排序
数据结构选择：数组 概要设计：定义一个容量为一亿个整数的数组，定义变量n，用rand函数生成n个随机数，并赋值给数组，用clock函数计算排序所用时间。编写排序函数和主函数。
一、快速排序
#include<iostream>
#include <ctime>
#include<cstdlib>
using namespace std
;
int a
[100000000],n
;
void partition(int A
[],int s
, int t
, int& cutpoint
)
{
int x
=A
[s
];
int i
=s
,j
=t
;
while(i
!=j
){
while(i
<j
&&A
[j
]>x
)
j
--;
if(i
<j
)
{
A
[i
]=A
[j
];
i
++;
}
while(i
<j
&&A
[i
]<x
)
i
++;
if(i
<j
)
{
A
[j
]=A
[i
];
j
--;
}
}
A
[i
]=x
;
cutpoint
=i
;
}
void quicksort(int A
[],int s
,int t
)
{
int f
;
if(s
<t
)
{
partition(A
,s
,t
,f
);
quicksort(A
,s
,f
-1);
quicksort(A
,f
+1,t
);
}
}
int main()
{
cin
>>n
;
for (int c
=0;c
<n
;c
++)
a
[c
]=rand();
int begintime
=clock();
quicksort(a
,0,n
-1);
int endtime
= clock();
cout
<<endtime
-begintime
<<"ms"<<endl
;
for(int d
=0;d
<n
;d
++)
{
cout
<<a
[d
]<<" ";
}
return 0;
}
二、堆排序
#include<iostream>
#include <ctime>
#include<cstdlib>
#include<vector>
using namespace std
;
void max_heapify(vector
<int> &nums
, int beg
, int end
)
{
int curr
= beg
;
int child
= curr
* 2 + 1;
while (child
< end
) {
if (child
+ 1 < end
&&nums
[child
] < nums
[child
+ 1])
child
++;
if (nums
[curr
] < nums
[child
]) {
swap(nums
[curr
], nums
[child
]);
curr
= child
;
child
= 2 * curr
+ 1;
}
else
break;
}
}
void heap_sort(vector
<int> &nums
)
{
int n
= nums
.size();
for (int i
= n
/ 2 + 1; i
>=0; i
--)
{
max_heapify(nums
, i
, nums
.size() - 1);
}
for (int i
= n
- 1; i
> 0; i
--)
{
swap(nums
[0], nums
[i
]);
max_heapify(nums
, 0, i
);
}
}
int a
[100000000],n
;
int main()
{
cin
>>n
;
for (int c
=0;c
<n
;c
++)
{
a
[c
]=rand();
}
int begintime
=clock();
vector
<int> vec(a
,a
+n
);
heap_sort(vec
);
int endtime
= clock();
cout
<<endtime
-begintime
<<"ms"<<endl
;
for(int d
=0;d
<n
;d
++)
{
cout
<<vec
[d
]<<" ";
}
return 0;
}
三、希尔排序
#include<iostream>
#include <ctime>
#include<cstdlib>
#include<vector>
using namespace std
;
int a
[100000000],n
;
void shell_sort(vector
<int> &nums
)
{
for(int gap
=nums
.size()>>1;gap
>0;gap
>>=1)
for (int i
= gap
; i
< nums
.size(); i
++)
{
int temp
= nums
[i
];
int j
= i
- gap
;
for (; j
>= 0 && nums
[j
] > temp
; j
-= gap
)
nums
[j
+gap
] = nums
[j
];
nums
[j
+gap
] = temp
;
}
}
int main()
{
cin
>>n
;
for (int c
=0;c
<n
;c
++)
{
a
[c
]=rand();}
int begintime
=clock();
vector
<int> vec(a
,a
+n
);
shell_sort(vec
);
int endtime
= clock();
cout
<<endtime
-begintime
<<"ms"<<endl
;
for(int d
=0;d
<n
;d
++)
{
cout
<<vec
[d
]<<" ";
}
return 0;
}
四、冒泡排序
#include<iostream>
#include <ctime>
#include<cstdlib>
using namespace std
;
int a
[100000000],n
;
int main()
{
cin
>>n
;
int temp
;
for (int i
=0;i
<n
;i
++)
{
a
[i
]=rand();
}
int begintime
=clock();
for (int i
=0;i
<n
-2;i
++)
{
for (int j
=n
-2;j
>=i
;j
--)
{
if(a
[j
+1]<a
[j
])
{
temp
=a
[j
];
a
[j
]=a
[j
+1];
a
[j
+1]=temp
;
}
}
}
int endtime
= clock();
cout
<<endtime
-begintime
<<"ms"<<endl
;
for (int j
=0;j
<n
;j
++)
{cout
<< a
[j
] <<" " ;}
return 0;
}
选择排序
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std
;
int a
[100000000],n
;
int main()
{
int temp
;
cin
>>n
;
for (int i
=0;i
<n
;i
++)
{
a
[i
]=rand();
}
int begintime
=clock();
for (int i
=0;i
<n
;i
++)
{
for (int j
=i
+1;j
<n
;j
++)
{
if (a
[i
]>a
[j
])
{
temp
= a
[j
];
a
[j
] = a
[i
];
a
[i
] = temp
;
}
}
}
int endtime
= clock();
cout
<<endtime
-begintime
<<"ms"<<endl
;
for (int c
=0;c
<n
;c
++)
{
cout
<< a
[c
] <<" " ;}
return 0;
}
测试数据
最多可实现一亿个数的排序。由于数据为一亿时冒泡和选择排序等待时间过长，没有一亿数据的测试结果。 测试效率快速排序>堆排序>希尔排序>冒泡排序>选择排序。
快速排序运行时间
堆排序运行时间
希尔排序运行时间
冒泡排序运行时间
选择排序运行结果
