[数据结构与算法]C++实现快速排序 希尔排序 插入排序 冒泡排序 选择排序 归并排序

直接上代码，有问题私聊

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