[数据结构与算法]十大经典排序算法c++实现

算法简介在这里
https://www.cnblogs.com/onepixel/articles/7674659.html
冒泡，选择，插入，希尔，归并，快速，堆，计数，桶，基数

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;


//https://www.cnblogs.com/onepixel/articles/7674659.html


vector<int> bubblesort(vector<int> a)      //冒泡排序
{
	for (int i = 0; i < a.size()-1; ++i) {
		for (int j = 0; j < a.size() - i - 1; ++j) {
			if (a[j] > a[j + 1]) {
				int temp = a[j + 1];
				a[j + 1] = a[j];
				a[j] = temp;
			}
		}
	}
	return a;
}

vector<int> selectionsort(vector<int> a) {  //选择排序
	for (int i = 0; i < a.size()-1; ++i) {
		int minindex = i;
		for (int j = i + 1; j < a.size(); ++j) {
			if (a[j] < a[minindex]) {
				minindex = j;
			}	
		}
		int temp = a[i];
		a[i] = a[minindex];
		a[minindex] = temp;
	}
	return a;
}

vector<int> insertionsort(vector<int> a) {   //插入排序
	for (int i = 1; i < a.size(); ++i) {
		int index = i - 1;
		int currect = a[i];
		while (index >= 0 && a[index] > currect) {
			a[index + 1] = a[index];
			--index;
		}
		a[index + 1] = currect;
	}
	return a;
}

vector<int> shellsort(vector<int> a) {            // 希尔排序
	for (int gap = a.size()/2; gap > 0; gap = gap / 2) {
		for (int i = gap; i < a.size(); ++i) {
			int index = i - gap;
			int currect = a[i];
			while (index >= 0 && a[index] > currect) {
				a[index + gap] = a[index];
				index = index - gap;
			}
			a[index + gap] = currect;
		}
	}
	return a;
}

vector<int> merge(vector<int> left, vector<int> right) {
	vector<int> res = {};
	int i = 0, j = 0;
	while (i < left.size() && j < right.size()) {
		if (left[i] >= right[j]) {
			res.push_back(right[j]);
			++j;
		}
		else {
			res.push_back(left[i]);
			++i;
		}
	}
	while (i < left.size()) {
		res.push_back(left[i]);
		++i;
	}
	while (j < right.size()) {
		res.push_back(right[j]);
		++j;
	}
	return res;
}

vector<int> mergesort(vector<int> arr) {   //归并排序
	if (arr.size() < 2) {
		return arr;
	}
	int middle = arr.size() / 2;
	vector<int> left{ &arr[0],&arr[0] + middle };
	vector<int> right{ &arr[0] + middle ,&arr[0] + arr.size() };
	return merge(mergesort(left), mergesort(right));
}


//https://blog.csdn.net/qq_28584889/article/details/88136498
void quickSort(int left, int right, vector<int>& arr)  //快速排序（从小到大）
{
	if (left >= right)
		return;
	int i, j, base, temp;
	i = left, j = right;
	base = arr[left];  //取最左边的数为基准数
	while (i < j)
	{
		while (arr[j] >= base && i < j)
			j--;
		while (arr[i] <= base && i < j)
			i++;
		if (i < j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	//基准数归位
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);//递归左边
	quickSort(i + 1, right, arr);//递归右边
}


void adjust(vector<int> &arr, int len, int index) {    //递归构建大顶堆
	//arr:需要排序的数组  len：排序的长度  index：当前操作的位置
	int left = 2 * index + 1;  //index的左子节点
	int right = 2 * index + 2;  //index的右子节点

	int maxidx = index;
	if (left<len && arr[left]>arr[maxidx]) maxidx = left;
	if (right<len && arr[right]>arr[maxidx]) maxidx = right;

	if (maxidx != index) {
		int temp = arr[maxidx];
		arr[maxidx] = arr[index];
		arr[index] = temp;
		adjust(arr, len, maxidx);
	}
}

void heapsort(vector<int> &arr, int size) {      //堆排序
	//构建大顶堆（从最后一个非叶子节点向上）
	for (int i = size / 2 - 1; i >= 0; --i) {
		adjust(arr, size, i);
	}
	//调整大顶堆
	for (int i = size - 1; i >= 1; --i) {
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;			//将当前最大的放到数组末尾
		adjust(arr, i, 0);		//将未完成排序的部分继续进行堆排序
	}
}

vector<int> countingsort(vector<int> &arr) {        //计数排序
	unordered_map<int, int> map;
	for (int i = 0; i < arr.size(); ++i) {
		map[arr[i]]++;
	}
	vector<int> res;
	int minarr = *min_element(arr.begin(), arr.end());
	int maxarr = *max_element(arr.begin(), arr.end());
	for (int i = minarr; i <= maxarr; ++i) {
		while (map[i]) {
			res.push_back(i);
			--map[i];
		}
	}
	return res;
}

int main()
{
	vector<int> a = { 7, 6, 5, 4, 3, 2, 1, 8, 9, 9, 9, 8 };
	/*heapsort(a, a.size());*/
	a = countingsort(a);

	for (int i = 0; i < a.size(); ++i) {
		cout<< a[i];
	}
	
	system("pause");
	return 0;
}