直接上代码,有问题私聊
#include<iostream>
#include <vector>
#include<time.h>
using namespace std;
//输出排序好函数的值
void printvalue(vector<int>nums,int size)
{
for (int value=0;value<size;value++)
cout << nums[value] << endl;
}
//工具函数交换两个函数的值
void swap(int& a, int& b)
{
int tem = a;
a = b;
b = tem;
}
//随机生成数组进行测试
void Gengrate(vector<int>& test, int size)
{
srand(time(NULL));
for (int i = 0; i < size; i++)
{
test.push_back(rand() % (size));
}
}
//归并排序
void _merge(vector<int>&a, int low, int mid, int high)
{ //分支
int left = low;
int right = mid+1;
int k = low;
vector<int>tem(a.size());
while (left < mid + 1 && right < high + 1)
{
// cout << "mid " << mid << endl;
if (a[left] < a[right])
{
tem[k++] = a[left++];
}
else
{
tem[k++] = a[right++];
}
}
while (left < mid + 1)
{
tem[k++] = a[left++];
}
while (right < high + 1)
{
tem[k++] = a[right++];
}
for (int i = low; i < high + 1; i++)
{
a[i] = tem[i];
}
}
void merge_sort(vector<int>&a, int low, int high)
{
//出口条件
if (low >= high)
return;
int mid = low + ((high - low) >>1);
//cout << "mid " <<mid<< endl;
merge_sort(a,low,mid);
merge_sort(a,mid+1,high);
_merge(a,low,mid,high);
}
//快速排序返回位置的函数
int returnpos(vector<int>& nums, int low, int high)
{
int value = nums[low];
while (low < high)
{
while (low<high && nums[high]>=value)
high--;
swap(nums[high],nums[low]);
while (low < high && nums[low] <=value)
low++;
swap(nums[high],nums[low]);
}
return low;
}
//快速排序
//通常选取第一个值作为比较值,交换前后的顺序
void quicksort(vector<int>&nums,int low,int high)
{
//快速排序是通过两两相互比较,交换值
if (low < high)
{
int pos = returnpos(nums, low, high);
quicksort(nums,low,pos-1);
quicksort(nums,pos+1, high);
}
}
//冒泡排序
void bubblesort(vector<int>&nums)
{
bool flag = true;
for (int i = 0; i < nums.size()&&flag; i++)
{
flag = false;
for (int j = nums.size() - 1; j > i; j--)
{
if (nums[j - 1] > nums[j])
{
swap(nums[j - 1], nums[j]);
flag = true;
}
}
}
}
//直接插入排序
void InsertSort(vector<int>&nums)
{ //从第一个元素开始默认与前一个元素比较
for (int i = 1; i < nums.size(); i++)
{
int key = nums[i];
int index = i - 1;
while (index >= 0 &&nums[index]>key)
{
nums[index + 1] = key;
index--;
}
nums[index + 1] = key;
}
}
//选择排序
void SelectSort(vector<int>& nums)
{
for (int i = 0; i < nums.size(); i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] > nums[j])
swap(nums[i],nums[j]);
}
}
}
//希尔排序
void ShellSort(vector<int>& nums)
{
for (int i= nums.size() / 2;i > 0; i = i / 2)
{
for (int j = i; j < nums.size(); j++)
{
int key = nums[j];
int index = j - i;
while (index >= 0 && nums[index] > key)
{
nums[index + i] = nums[index];
index -= i;
}
nums[index + i] = key;
}
}
}
int main()
{
int size = 1000;
vector<int>test;
Gengrate(test, size);
clock_t Merge_start = clock();
merge_sort(test,0, size-1);
cout << "归并排序所用时间为" << (double)(clock() - Merge_start) / CLOCKS_PER_SEC << endl;
printvalue(test,size);
//快速排序
Gengrate(test, size);
clock_t start=clock();
quicksort(test,0,size-1);
cout << "快速排序所用时间为" <<(double)(clock() - start)/CLOCKS_PER_SEC<< endl;
printvalue(test, size);
clock_t bubbletime = clock();
Gengrate(test, size);
bubblesort(test);
cout << "冒泡所用时间" << (double)(clock() - bubbletime) / CLOCKS_PER_SEC << endl;
printvalue(test,size);
clock_t InsertTime = clock();
Gengrate(test, size);
InsertSort(test);
cout << "直接插入排序所用时间" << (double)(clock() -InsertTime) / CLOCKS_PER_SEC << endl;
printvalue(test, size);
clock_t ShellSortTime = clock();
Gengrate(test, size);
ShellSort(test);
cout << "希尔排序所用时间" << (double)(clock() - ShellSortTime) / CLOCKS_PER_SEC << endl;
printvalue(test, 100);
clock_t SelectTime = clock();
Gengrate(test, size);
SelectSort(test);
cout << "选择排序所用时间" << (double)(clock() - SelectTime) / CLOCKS_PER_SEC << endl;
printvalue(test, 10);
return 0;
}