常用排序算法（C++实现）

常用排序算法（C++实现）

1. 快速排序
2. 归并排序
3. 冒泡排序
4. 直接选择排序
5. 直接插入排序

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;


void quick_sort(vector& q, int l, int r);  //快速排序
void merge_sort(vector& q, int l, int r);  //归并排序
void bubble_sort(vector& q, int l, int r); //冒泡排序
void select_sort(vector& q, int l, int r); //选择排序
void insert_sort(vector& q, int l, int r); //插入排序
void Print(vector& q);                     //输出


int main()
{
	vector vec;
	int n = 0, t = 0;
	cout << "输入数据个数：";
	cin >> n;
	srand((unsigned)time(NULL));
	cout << "随机生成" << n << "个数据：";
	for (int i = 0; i < n; i++)
	{
		t = rand() % 100 + 1;
		vec.push_back(t);
	}
	Print(vec);
	vector v1(vec), v2(vec), v3(vec), v4(vec), v5(vec);
	cout << "快速排序结果：";
	quick_sort(v1, 0, v1.size() - 1);
	Print(v1);
	cout << "归并排序结果：";
	merge_sort(v2, 0, v2.size() - 1);
	Print(v2);
	cout << "冒泡排序结果：";
	bubble_sort(v3, 0, v3.size() - 1);
	Print(v3);
	cout << "选择排序结果：";
	bubble_sort(v4, 0, v4.size() - 1);
	Print(v4);
	cout << "插入排序结果：";
	insert_sort(v5, 0, v5.size() - 1);
	Print(v5);
	return 0;
}


void quick_sort(vector& q, int l, int r)
{
	if (l >= r) return;
	int x = q[l + (r - l) / 2], i = l - 1, j = r + 1;
	while (i < j)
	{
		while (q[++i] < x); //do i++; while (q[i] < x);
		while (q[--j] > x); //do j++; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}


void merge_sort(vector& q, int l, int r) //归并排序
{
	if (l >= r) return;
	int mid = l + (r - l) / 2;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int i = l, j = mid + 1;
	vector temp;
	while (i <= mid && j <= r)
	{
		if (q[i] < q[j]) temp.push_back(q[i++]);
		else temp.push_back(q[j++]);
	}
	while (i <= mid) temp.push_back(q[i++]);
	while (j <= r) temp.push_back(q[j++]);
	for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}


void bubble_sort(vector& q, int l, int r) //冒泡排序
{
	if (l >= r) return;
	for (int i = 0; i < r - l; i++)
	{
		int flag = 0;
		for (int j = l; j < r - i; j++)
		{
			if (q[j] > q[j + 1])
			{
				swap(q[j], q[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0) break;  //对冒泡排序的优化
	}
}


void select_sort(vector& q, int l, int r) //选择排序
{
	if (l >= r) return;
	for (int i = l; i <= r; i++)
	{
		int mi = i;
		for (int j = i + 1; j <= r; j++)
		{
			if (q[mi] > q[j]) mi = j;
		}
		if (mi != i) swap(q[i], q[mi]);
	}
}


void insert_sort(vector& q, int l, int r) //插入排序
{
	if (l >= r) return;
	for (int i = l + 1; i <= r; i++)
	{
		int temp = q[i];
		int j = i - 1;
		while (j >= 0 && q[j] > temp)
		{
			q[j + 1] = q[j];
			j--;
		}
		q[j + 1] = temp;
	}
}


void Print(vector& q)
{
	for (unsigned int i = 0; i < q.size(); i++) cout << q[i] << " ";
	cout << endl;
}

执行结果：