亲测有效

#include<iostream>
#include<vector>
#include<windows.h>
#include<random>
constexpr auto sumSize = 10000;//设置想要的数据
using namespace std;
template<typename T> void selectSorted(vector<T>& array, const int length)//选择排序
{
int cir_out;
int cir_in;
for (cir_out = 0; cir_out < length; cir_out++)
{
for (cir_in = cir_out; cir_in < length; cir_in++)
{
if (array[cir_out] > array[cir_in])
{
swap(array[cir_out], array[cir_in]);
}
}
}
}
template<typename T> void bubleSorted(vector<T>& array, const int length)//冒泡排序
{
for (int cir_out = 0; cir_out < length; cir_out++)
{
for (int cir_in = 0; cir_in < length - cir_out - 1; cir_in++)
{
if (array[cir_in] > array[cir_in + 1])
{
swap(array[cir_in], array[cir_in + 1]);
}
}
}
}
template<typename T> void insertSort(vector<T>& array, const int length)//插入排序
{
for (int i = 0; i < length - 1; i++)
{
int end = i;//位置0
int temp = array[end + 1];//位置1
while (end >= 0)
{
if (temp < array[end])//如果位置1数大于位置0，位置0向后移位，，位置1插入位置0
{
array[end + 1] = array[end];
end--;
}
else//否则不处理
break;
}
array[end + 1] = temp;
}
}
template <typename T> void bucketSort(vector<T>& array, const int length)//桶排序
{
int i, j;
vector<T> buckets(50000);
for (i = 0; i < 101; i++)
{
buckets[i] = 0;
}
for (i = 0; i < length; i++)
{
buckets[array[i]]++;
}
for (i = 0, j = 0; i < 50000; i++)
{
while (buckets[i] > 0) {
array[j] = i;
buckets[i]--;
j++;
}
}
}
template<typename T> void merge(vector<T>& data, int start, int end, vector<T>& result)
{
int left_length = (end - start + 1) / 2 + 1;
int left_index = start;
int right_index = start + left_length;
int result_index = start;
while (left_index < start + left_length && right_index < end + 1)
{
if (data[left_index] <= data[right_index])
result[result_index++] = data[left_index++];
else
result[result_index++] = data[right_index++];
}
while (left_index < start + left_length)
result[result_index++] = data[left_index++];
while (right_index < end + 1)
result[result_index++] = data[right_index++];
}
template<typename T> void merge_sort(vector<T>& data, int start, int end, vector<T>& result)
{
if (1 == end - start)
//如果相邻
{
if (data[start] > data[end])//左边比右边大
{
swap(data[start],data[end]);
}
return;
}
else if (end == start)//回退条件
return;
else {
merge_sort(data, start, (end - start + 1) / 2 + start, result);
merge_sort(data, (end - start + 1) / 2 + start + 1, end, result);
merge(data, start, end, result);//归并
for (int i = start; i <= end; ++i)
{
data[i] = result[i];
}
}
}
template<typename T> void shellSort(vector<T>& array, const int length)//希尔排序
{
// 获取初始的间隔长度
int interval = length / 2;
//
不断地缩小间隔的大小，进行分组插入排序
while (interval >= 1) {
//
从 arr[interval] 开始往后遍历，将遍历到的数据与其小组进行插入排序
for (int i = interval; i < length; i++) {
int temp = array[i];
int j = i;
while (j - interval >= 0 && array[j - interval] > temp) {
array[j] = array[j - interval];
j -= interval;
}
array[j] = temp;
}
// 5. 缩小间隔
interval = interval / 2;
}
}
template<typename T> void Down(vector<T>& array, int i ,const int length) { // 最后结果就是大顶堆
int parent = i;
// 父节点下标
int child = 2 * i + 1;
// 子节点下标
while (child < length) {
if (child + 1 < length && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
child++;
}
if (array[parent] < array[child]) { // 判断父节点是否小于子节点
swap(array[parent],array[child]);
// 交换父节点和子节点
parent = child;
// 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行，比较下面的父节点和子节点
}
}
template<typename T> void BuildHeap(vector<T>& array,const int length) {
for (int i = length / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
Down(array, i, length);
// 否则有的不符合大顶堆定义
}
}
template<typename T> void heapSort(vector<T>&array, const int length) {
BuildHeap(array, length); // 初始化堆
for (int i = length - 1; i > 0; i--) {
swap(array[0],array[i]); // 交换顶点和第 i 个数据
// 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆
}
}
template<typename T> int partion(vector<T>& array, int left, int right)
{
if (left >= right)
//先检查左右条件
return -1;
int i = left, j = right, x = array[left];
while (i < j)
{
while (i < j && array[j] >= x)//从右向左找到第一个小于x的
j--;
if (i < j)
array[i++] = array[j];//填坑之后i++,如果是考试填空或简答题，一般不是先用a[j]填坑，是先找到i,j的位置，然后才交换a[i],a[j]的值。
while (i < j && array[i] <= x)//从左向右找第一个大于x的数
i++;
if (i < j)
array[j--] = array[i];
}
array[i] = x;
//把最开始取出来的x放到i处
return i;
}
template<typename T> void quickSorted(vector<T>& array, int left, int right)
{
if (left < right)
{
int q = partion(array, left, right);
quickSorted(array, left, q - 1);
quickSorted(array, q + 1, right);
}
}
template<typename T> void display(vector<T>& array, const int length)
{
for (int k = 0; k< sumSize; k++)
{
cout << array[k] << " ";
}
cout << endl;
}
int main(int argc, char* argv[])
{
int j;
int t = 1;
vector<int> array(sumSize, 0);
vector<int> temp(sumSize, 0);
vector<int> randtemp(sumSize, 0);
LARGE_INTEGER frequency, start, finish;
for (int i = 0; i < sumSize; i++)
{
int num = rand() % 100;
array[i] = num;
randtemp[i] = num;
}//产生伪随机数进行比较
/*for (int i = 0; i < sumSize; i++)
{
array[i] = i;
randtemp[i] = i;
}如需和产生顺序数将上面的替换掉*/
/*for (int i = sumSize-1,j=0; i >= 0,j<sumSize; i--,j++)
{
array[i] = i;
randtemp[j] =i;
}产生逆序数*/
while (t)
{
cout << "1.冒泡排序" << endl;
cout << "2.选择排序" << endl;
cout << "3.插入排序" << endl;
cout << "4.希尔排序" << endl;
cout << "5.桶排序" << endl;
cout << "6.堆排序" << endl;
cout << "7.归并排序" << endl;
cout << "8.快速排序" << endl;
cout << "0.退出";
cin >> j;
if (j != 0)
{
for (int i = 0; i < sumSize; i++)
{
array[i] = randtemp[i];
cout << array[i] << " ";
}
}
else
break;
cout << endl;
QueryPerformanceFrequency(&frequency);
QueryPerformanceCounter(&start);
switch (j)
{
case 1:
bubleSorted(array, sumSize);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 2:
selectSorted(array, sumSize);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 3:
insertSort(array, sumSize);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 4:
shellSort(array, sumSize);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 5:
bucketSort(array, sumSize);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 6:
heapSort(array, sumSize);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 7:
merge_sort(array, 0, sumSize - 1, temp);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
case 8:
quickSorted(array, 0, sumSize - 1);
QueryPerformanceCounter(&finish);
display(array, sumSize);
cout << "运行时间：" << ((double)finish.QuadPart - start.QuadPart) / (double)frequency.QuadPart << "s" << endl;
cout << endl;
break;
default: j = 0;
}
}
}

最后

以上就是笨笨发带为你收集整理的八大常用排序算法（堆排序，冒泡排序，快速排序，归并排序，桶排序等）不同数据量的时间效率比较亲测有效的全部内容，希望文章能够帮你解决八大常用排序算法（堆排序，冒泡排序，快速排序，归并排序，桶排序等）不同数据量的时间效率比较亲测有效所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。