本文共 7264 字，大约阅读时间需要 24 分钟。

1、插入排序：和玩纸牌游戏一样，抓牌时小的插在前边，后边牌往后移动

void insertSort(int* arr, int len){   if(!arr || len<2)       return;   int preIndex=0, curVal=0;   for(int i=1; i
   
    =0 && arr[preIndex]>curVal){          arr[preIndex+1] = arr[preIndex];          preIndex--;       }       arr[preIndex+1] = curVal;   }}
   

2、冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

void bubbleSort(size_t size, int* arr) {	if (!arr || size <= 1) {		return;	}	bool bComplete = false;	for (size_t i = 0; i < size; i++) {		bComplete = true;		for (size_t j = 0; j < size - i - 1; j++) {			if (arr[j] > arr[j + 1])			{				std::swap(arr[j], arr[j + 1]);				bComplete = false;			}		}		if (bComplete) {			return;		}	}}

3、选择排序：选择排序是一种简单直观的排序算法

void selectSort(size_t size, int* arr) {	if (!arr || size <= 1) {		return;	}	size_t minIndex = 0;	for (size_t i = 0; i < size - 1; i++) {		minIndex = i;		for (size_t j = i + 1; j < size; j++) {			if (arr[j] < arr[minIndex]) {				minIndex = j;			}		}		std::swap(arr[i], arr[minIndex]);	}}

4、希尔排序：是简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

void shellSort(size_t size, int*arr) {	if (!arr || size <= 1) {		return;	}	size_t gap = 1;	size_t j = 0;	//固定增量变化	for (gap = size / 2; gap > 0; gap /= 2) {		for (size_t i = gap; i < size; ++i) {			//int()转换类型，避免溢出，相当于分组的插入排序			for (j = i; int(j - gap) >= 0 && arr[j - gap] > arr[j]; j -= gap) {				std::swap(arr[j - gap], arr[j]);			}		}	}}

5、归并排序

void merge(int*arr, size_t left, size_t mid, size_t right) {	int len = right - left + 1;	int *temp = new int[len];  //数组较长时请用new，不然栈空间容易溢出	size_t index = 0;	size_t i = left, j = mid + 1;	while (i <= mid && j <= right){		temp[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; //对两边的数组从小到大放入临时空间	}	while (i <= mid){		temp[index++] = arr[i++];//比较完后，左半边有没放进去的，直接写入	}	while (j <= right)	{		temp[index++] = arr[j++];//比较完后，右半边有没有放进去的，直接写入	}	for (int k = 0; k < len; ++k){		arr[left++] = temp[k];  //把有序的临时数组写入原来数组的起始位置	}	delete[] temp;  //释放空间	temp = NULL;  //指针置空}void divide(int* arr, size_t left, size_t right) {	//递归出口	if (left == right){		return;	}	size_t mid = (left + right) / 2; //找出区间中部的数，将数组分段	divide(arr, left, mid);//递归调用，对左边继续分段；	divide(arr, mid + 1, right);//递归调用，对左边继续分段；	merge(arr, left, mid, right); //对左右两半进行排序合并成一小段有序的数组}void mergeSort(size_t size, int* arr) {	if (!arr || size <= 1) {		return;	}	size_t left = 0, right = size - 1;	divide(arr, left, right);}

6、快速排序：每次都取数组的第一个元素作为基准元素，凡是大于这个基准元素的都放在右边，凡是小于这个基准元素的都放在它的左边。

• 设置两个变量i,j（称为哨兵），令序列的第一个元素为基准元素。
• i指向序列的最左边， j指向序列的最右边，j从右往左试探，i从左往右试探，直到j找到小于基准的数就停止，i找到大于基准的数就停止，交换i和j指向的两个数，j继续往左试探，i继续往右试探
• 如果i和j相遇，则i或j上的元素与基准元素交换，一轮排序结束
• 对基准元素两边的序列重复上述步骤

void qSort(int* arr, int left, int right) {	int i = left;	int j = right;	int temp = arr[left]; //基准元素	//递归结束条件	if (left >= right) {		return;	}	while (i != j) {		while (arr[j] >= temp && i < j) { //从右往左，找到小于基准的数			j--;		}		while (arr[i] <= temp && i < j) { //从左往右，找到大于基准的数			i++;		}		//交换i和j指向的两个数，然后继续，知道i,j相遇		if (i < j) {			std::swap(arr[i], arr[j]); 		}	}	//i和j相遇，i 或 j上的元素与基准元素交换，一轮排序结束	arr[left] = arr[i]; 	arr[i] = temp;	//再分别对两边数据递归快排	qSort(arr, left, i - 1);	qSort(arr, i + 1, right);}void quickSort(size_t size, int* arr) {	if (!arr || size <= 1) {		return;	}	qSort(arr, 0, size - 1);}

7、堆排序

//建立大堆(1、完全二叉树；2、父节点的值始终大于子节点)void heapify(int* tree, int n, int i) {	//递归结束出口	if (i >= n) {		return;	}	int left = 2 * i + 1;	int right = 2 * i + 2;	int maxIndex = i;	maxIndex = (left < n && tree[left] > tree[maxIndex]) ? left : maxIndex;	maxIndex = (right < n && tree[right] > tree[maxIndex]) ? right : maxIndex;	if (maxIndex != i) {		std::swap(tree[i], tree[maxIndex]);		heapify(tree, n, maxIndex);	}}void heapSort(int size, int* arr) {	if (!arr || size <= 1) {		return;	}	int lastNodeIndex = size - 1; //最后一个子节点	int lastParentIndex = (lastNodeIndex - 1) / 2; //最后一个子节点的父节点	//从最后一个子节点的父节点开始对所有父节点建立大堆	for (int i = lastParentIndex; i >= 0; i--){		heapify(arr, size, i);	}	//经过上一步骤处理后根节点必然是最大的值	//将根节点和最后一个子节点交换位置后截取掉树的最后一个节点，也就是最大的值，这时大堆被打乱，再对树中剩下的值heapify	for (int i = size - 1; i >= 0; i--) {		std::swap(arr[i], arr[0]);		heapify(arr, i, 0);	}}

8、计数排序

void countSort(int size, int* arr) {	if (!arr || size <= 1) {		return;	}	int index = 0, min, max;	min = max = arr[0];	//遍历数组找出最小和最大的数  5  3  4  7  2  4  3  4  7	for (size_t i = 1; i < size; i++) {		min = arr[i] < min ? arr[i] : min;		max = arr[i] > max ? arr[i] : max;	}	int len = max - min + 1;	int* temp = new int[len](); //初始化为0	for (int i = 0; i < size; i++) {		temp[arr[i] - min]++;	}	//打印下计数数组	for (int i = 0; i < len; i++)	{		std::cout << temp[i] << " ";	}	std::cout << std::endl;	for (int i = min; i <= max; i++)	{		int count = temp[i - min];		for (int j = 0; j < count; ++j)	//存放元素个数不为0的，才进入循环		{			arr[index++] = i;  //把元素值写回数组		}	}	delete[] temp;	temp = nullptr;}

9、桶排序，将数据按规则分组，对各小组再分别排序

• 数组长度一定的，只申请一次内存，避免内存碎片化，提高效率
•  给定桶的个数，程序运行状况在不同环境下可控

void bucketSort(size_t size, int *arr, int bucketCount = 10){	if (!arr || size <= 1) {		return;	}	int maxval = arr[0];	int minval = arr[0];	//遍历数组，找出最大最小元素	for (int i = 0; i != size; ++i)	{		maxval = maxval > arr[i] ? maxval : arr[i];		minval = minval < arr[i] ? minval : arr[i];	}	//如果最大等于最小，数组不需要排序	if (maxval == minval){		return;	}	int div = /*1000*/bucketCount; //桶的个数	int space = (maxval - minval) / div + 1; //每个桶的数值跨度，+1放大一点包住	int *numsofeachbucket = new int[div](); //开辟数组，存放每个桶内的元素个数，（）初始化为0	int *endpositionofeachbucket = new int[div]();	for (size_t i = 0; i != size; ++i){		//把元素按大小分到不同的桶，并增加该桶元素个数		numsofeachbucket[(arr[i] - minval) / space]++;		endpositionofeachbucket[(arr[i] - minval) / space]++;	}	for (int i = 1; i != div; ++i){		endpositionofeachbucket[i] += endpositionofeachbucket[i - 1];		//每个桶区间的最大下标+1的值	}	int *temp = new int[size];	//开辟堆空间，存放临时数组	for (size_t i = 0; i != size; ++i){		temp[--endpositionofeachbucket[(arr[i] - minval) / space]] = arr[i];		//遍历数组，把每个元素写入对应的桶中，从每个桶的后部往前写		//--运行完成后endpositionofeachbucket[i]就是该桶的首位	}	for (size_t i = 0; i != div; ++i)	{		if (numsofeachbucket[i] > 1)	//桶元素2个或以上才排序		{			//对每个桶的数组进行快速排序（元素个数，每个桶数组首位的地址）			quickSort(numsofeachbucket[i], &temp[endpositionofeachbucket[i]]);		}	}	//对排序后的数组，写入原数组	for (size_t i = 0; i != size; ++i){		arr[i] = temp[i];	}	delete[] numsofeachbucket;	delete[] endpositionofeachbucket;	delete[] temp;	numsofeachbucket = nullptr;	endpositionofeachbucket = nullptr;	temp = nullptr;}

10、基数排序

void radix_countsort(size_t size, int *arr, int exp){	int numofeachbucket[10] = { 0 };  //十个数位，每个桶上有0个元素	for (int i = 0; i != size; ++i) {		++numofeachbucket[(arr[i] / exp) % 10];	//记录该数位上相同的元素个数	}	for (int i = 1; i < 10; ++i) {		numofeachbucket[i] += numofeachbucket[i - 1];	}	int *temp = new int[size];	for (int i = size - 1; i >= 0; --i) {		int k = (arr[i] / exp) % 10;		temp[numofeachbucket[k]] = arr[i]; //把数组放在不同的区间位置上		numofeachbucket[k]--;	}	for (int i = 0; i != size; ++i) {		arr[i] = temp[i];  //一个数位排好后，写回原数组，开始下一位数的装桶排序	}	delete[] temp;	temp = nullptr;}void radixSort(size_t size, int *arr){	if (!arr || size <= 1) {		return;	}	int max = arr[0];	//找出最大的数	for (size_t i = 0; i != size; ++i) {		max = arr[i] > max ? arr[i] : max;	}	//从最低位开始对每个数位进行排序	for (int exp = 1; max / exp > 0; exp *= 10) {		radix_countsort(size, arr, exp);	}}

转载地址：http://kriii.baihongyu.com/