经典排序算法复习

十大经典排序算法

备忘录

本博客用于快速复习几种简单排序算法。这些算法虽然经典，但是都很简单，只要明白其思想和原理，都能很快写出来。关键是要把握好一些细节之处，例如循环边界等。

代码

#pragma warning(disable : 4996)
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define ARRAY vector<int> //下标从0开始有效
#define INF	0x07070707
using namespace std;

//打印数组
void printArry(ARRAY &ary){
	for (int i = 0; i < ary.size(); i++){
		cout << ary[i] << " ";
	}
	cout << endl;
	return;
}

/*插入排序
过程：维护一个有序的数组，数组长度从1开始，每趟循环后长度加1，并通将尾部元素插入到适当位置的方式调整这个有序数组。
注意事项：段移位时注意覆盖问题，循环要从后往前
*/
void insertSort(ARRAY &ary){
	for (int i = 1; i < ary.size(); i++){
		for (int j = 0; j < i; j++){
			if (ary[j] > ary[i]){
				int tmp = ary[i];
				for (int k = i; k > j; k--){
					ary[k] = ary[k-1];
				}
				ary[j] = tmp;
				break;
			}
		}
	}
}

/*
冒泡排序
过程：不断遍历每一组相邻的元素，若这组元素的大小不符合顺序则交换他们，直到一组循环下来没有元素被交换
*/
void bubbleSort(ARRAY &ary){
	while (true){
		bool change = false;
		for (int i = 0; i < ary.size() - 1; i++){
			if (ary[i] > ary[i + 1]){
				swap(ary[i], ary[i + 1]);
				change = true;
			}
		}
		if (!change) {
			break;
		}
	}
	return;
}

/*
选择排序
过程：维护一个未排序序列，每趟循环将这个序列中最小的元素与第一个元素交换，然后首个元素从未排序序列中移除
*/
void selectSort(ARRAY &ary){
	for (int i = 0; i < ary.size(); i++){
		int minIdx = i, minEle = INF;
		for (int j = i; j < ary.size(); j++){
			if (ary[j] < minEle) {
				minEle = ary[j];
				minIdx = j;
			}
		}
		if (i != minIdx){
			swap(ary[i], ary[minIdx]);
		}
	}
	return;
}

/*
计数排序
特定：计数排序要求输入的数据必须是有确定范围的整数，速度快于任何比较排序算法
过程：使用数组来记录一个范围内每个值出现的次数，再按顺序反向输出回原数组。
*/
void countSort(ARRAY &ary, int minEle, int maxEle){
	ARRAY counter(maxEle-minEle+1, 0);
	for (int i = 0; i < ary.size(); i++){
		counter[ary[i] - minEle] ++;
	}
	int idx = 0;
	for (int i = 0; i < counter.size(); i++){
		while (counter[i]-- > 0){
			ary[idx++] = i + minEle;
		}
	}
	return;
}

/*
桶排序
备注：桶排序是计数排序的升级版。
过程：将一堆数按照大小层次分为许多个桶，对每个桶进行排序操作，然后再反向输出回原数组
*/
void bucketSort(ARRAY &ary, int minEle, int maxEle){
	const int bucketNum = 10;
	const int aryRange = maxEle - minEle + 1;
	int bucketSize = (aryRange >= bucketNum ? aryRange / bucketNum +1 : 1);
	ARRAY buckets[bucketNum];
	//进桶
	for (int i = 0; i < ary.size(); i++){
		buckets[(ary[i] - minEle) / bucketSize].push_back(ary[i]);
	}
	//对各个桶进行排序
	for (int i = 0; i < bucketNum; i++){
		sort(buckets[i].begin(), buckets[i].end());
	}
	int idx = 0;
	//用排序结果覆盖原数组
	for (int i = 0; i < bucketNum; i++){
		for (int j = 0; j < buckets[i].size(); j++){
			ary[idx++] = buckets[i][j];
		}
	}
	return;
}

/*
希尔排序
备注：也称递减增量排序算法，是插入排序的一种更高效的改进版本。
基本思想：先将整个待排序的分割为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
*/
void shellSort(ARRAY &ary){
	//gap指步长，0~gap为各个子序列的第一个元素。
	for (int gap = ary.size() / 2; gap > 0; gap /= 2){
		for (int i = 0; i < gap; i++){
			for (int j = i + gap; j < ary.size(); j += gap){
				while (j - gap >= 0 && ary[j] < ary[j - gap]){	//注意出发条件是比上一个元素小，而不是比第一个元素小。
					swap(ary[j], ary[j - gap]);
					j -= gap;
				}
			}
		}
	}
	return;
}

/*
基数排序
备注：与桶排序和计数排序一样利用了桶的概念。将整数按位数切割成不同的数字，然后按每个位数分别比较，除了整数外还可以用于字符串和特定格式的浮点数。
*/
void radixSort(ARRAY &ary){
	queue<int> buckets[20];
	//从个位开始，将元素复制到该位对应的桶
	bool notEnd = true;
	for (int base = 10; notEnd; base *= 10){
		int dev = base / 10;
		notEnd = false;
		for (int i = 0; i < ary.size(); i++){
			if (abs(ary[i]) >= base) {
				notEnd = true;	//当所有数值长度小于base时结束循环
			}
			int t = (ary[i] >= 0 ? 10 : 0);
			int m = (abs(ary[i]) % base) / dev;
			buckets[t + m].push(ary[i]);
		}
		//完成一轮操作后将元素复制回数组
		int idx = 0;
		for (int i = 9; i >=0; i--){
			while (!buckets[i].empty()){
				ary[idx++] = buckets[i].front();
				buckets[i].pop();
			}
		}
		for (int i = 10; i < 20; i++){
			while (!buckets[i].empty()){
				ary[idx++] = buckets[i].front();
				buckets[i].pop();
			}
		}
	}
	return;
}

/*
快速排序
备注：快速排序是一种分而治之思想在排序算法上的典型应用。快速排序的最坏运行情况是 O(n²)，
	但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。
	所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
过程：1->从数列中挑出一个元素作为基准。2->进行分区操作。3->递归
*/
void quickSort(ARRAY &ary, int l, int r){	//注意r有效
		if (l >= r){
			return;
		}
		int le=l, re=r, mid=ary[l];
		while (le < re) {
			while (le < re){// 从右向左找第一个小于x的数
				if (ary[re] < mid) {
					ary[le] = ary[re];
					break;
				}
				re--;
			}
			while (le < re){// 从左向右找第一个大于x的数
				if (ary[le] > mid){
					ary[re] = ary[le];
					break;
				}
				le++;
			}		
		}
		ary[le] = mid;
		quickSort(ary, l, le - 1); /* 递归调用 */  //注意不包括i了
		quickSort(ary, le+1, r); /* 递归调用 */
		return;
}


/*
堆排序
*/
//调整最大堆(升序)
void heapAdjust(ARRAY &ary, int root, int tail){	//不包括tail
	for (int i = root * 2 + 1; i < tail; i = i * 2 + 1){
		i += (i+1<tail && ary[i + 1] > ary[i] ? 1 : 0);
		if (ary[root] > ary[i]) break;
		swap(ary[root], ary[i]);
		root = i;
	}
	return;
}
//堆排序
void HeapSortInsc(ARRAY& ary){
	int size = ary.size();
	//生成大顶堆
	for (int i = size / 2 - 1; i >= 0; i--){
		heapAdjust(ary, i, size);
	}
	//每次将根部移到数组尾部，再重新维护堆
	for (int i = size - 1; i > 0; i--){
		swap(ary[0], ary[i]);
		heapAdjust(ary, 0, i - 1);	//注意是i-1
	}
	return;
}

/*
归并排序
笔记：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
*/
void mergerSort(ARRAY &ary, int root, int tail){	//包含tail
	if (root >= tail){
		return;
	}
	int mid = (root + tail) / 2;
	mergerSort(ary, root, mid);
	mergerSort(ary, mid + 1, tail);
	ARRAY tmp(tail - root + 1);
	auto begin = ary.begin();
	merge(begin+root, begin+mid+1, begin+mid+1, begin+tail+1, tmp.begin());
	for (int i = 0, idx = root; i < tmp.size(); i++){
		ary[idx++] = tmp[i];
	}
	return;
}


int main(){
	ARRAY ary{10, 9, 8, 7, 6, 5, 4,3, 100,1, 0, 0, -1, 100,100,5,5,5};
	ARRAY ary2{ -1,23, 11, -91, -30, 0, -100, -123, 19, 299, 91, 80, 80, 80 };
	//insertSort(ary);
	//bubbleSort(ary);
	//selectSort(ary);
	//countSort(ary, -1, 100);
	//bucketSort(ary, -1, 100);
	//shellSort(ary);
	//radixSort(ary2);
	//quickSort(ary2, 0, ary2.size()-1);
	//HeapSortInsc(ary2);
	mergerSort(ary2, 0, ary2.size() - 1);


	printArry(ary2);
	return 0;
}