【模板】8大排序算法模板函数

冷不防 2022-11-13 00:51 252阅读 0赞

*  排序（1）：冒泡排序
 *  排序（2）：直接插入排序
 *  排序（3）：希尔排序
 *  排序（4）：快速排序
 *  排序（5）：简单选择排序
 *  排序（6）：堆排序
 *  排序（7）：归并排序
 *  排序（8）：基数排序

8中模板函数都在其中，只需要加入主程序调用即可

#include <iostream>
    #include <vector>
     
    using namespace std;
     
    // 基础冒泡排序
    vector<int> bubbleSort_1(vector<int> list){ 
    	vector<int> result;
    	if (list.empty()){ 
    		return result;
    	}
    
    	result = list;
    	int temp;
    	// 要遍历的次数
    	for (int i = 0; i < result.size() - 1; ++i){ 
    		cout << "第" << i + 1 << "趟排序:" << endl;;
    		// 从后向前依次的比较相邻两个数的大小
    		for (int j = 0; j < result.size() - 1; j++){ 
    			// 如果后面的元素小，则交换它们的位置
    			if (result[j + 1] < result[j]){ 
    				temp = result[j + 1];
    				result[j + 1] = result[j];
    				result[j] = temp;
    			}
    			cout << "排序中:";
    			for (int s = 0; s < result.size(); s++){ 
    				cout << result[s] << " ";
    			}
    			cout << endl;
    		}
    		cout << "排序结果:";
    		for (int s = 0; s < result.size(); s++){ 
    			cout << result[s] << " ";
    		}
    		cout << endl;
    	}
    
    	return result;
    }
    
    // 优化冒泡排序
    vector<int> bubbleSort_2(vector<int> list){ 
    	vector<int> result;
    	if (list.empty()){ 
    		return result;
    	}
    
    	result = list;
    	int temp;
    	// 要遍历的次数
    	for (int i = 0; i < result.size() - 1; ++i){ 
    		cout << "第" << i + 1 << "趟排序:" << endl;;
    		//交换标志位
    		bool bChanged = false;
    		// 从后向前依次的比较相邻两个数的大小
    		for (int j = 0; j < result.size() - 1; j++){ 
    			// 如果后面的元素小，则交换它们的位置
    			if (result[j + 1] < result[j]){ 
    				temp = result[j + 1];
    				result[j + 1] = result[j];
    				result[j] = temp;
    				bChanged = true;
    			}
    			cout << "排序中:";
    			for (int s = 0; s < result.size(); s++){ 
    				cout << result[s] << " ";
    			}
    			cout << endl;
    		}
    		// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
    		if (false == bChanged){ 
    			break;
    		}
    		cout << "排序结果:";
    		for (int s = 0; s < result.size(); s++){ 
    			cout << result[s] << " ";
    		}
    		cout << endl;
    	}
    
    	return result;
    }
     
    // 直接插入排序
    vector<int> insertSort(vector<int> list){ 
    	vector<int> result;
    	if (list.empty()){ 
    		return result;
    	}
    	result = list;
    	// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
    	for (int i = 1; i < result.size(); i++){ 
    		// 取出第i个数，和前i-1个数比较后，插入合适位置
    		int temp = result[i];
    		// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
    		int j = i - 1;
    		for (j; j >= 0 && result[j] > temp; j--){ 
    			result[j + 1] = result[j];
    		}
    		result[j + 1] = temp;
    	}
    	return result;
    }
    
    // 希尔排序
    vector<int> ShellSort(vector<int> list){ 
    	vector<int> result = list;
    	int n = result.size();
    	for (int gap = n >> 1; gap > 0; gap >>= 1){ 
    		for (int i = gap; i < n; i++){ 
    			int temp = result[i];
    			int j = i - gap;
    			while (j >= 0 && result[j] > temp){ 
    				result[j + gap] = result[j];
    				j -= gap;
    			}
    			result[j + gap] = temp;
    		}
    		for (int i = 0; i < result.size(); i++){ 
    			cout << result[i] << " ";
    		}
    		cout << endl;
    	}
    	return result;
    }
    
    // 快速排序的division函数
    int division(vector<int> &list, int left, int right){ 
    	// 以最左边的数(left)为基准
    	int base = list[left];
    	while (left < right) { 
    		// 从序列右端开始，向左遍历，直到找到小于base的数
    		while (left < right && list[right] >= base)
    			right--;
    		// 找到了比base小的元素，将这个元素放到最左边的位置
    		list[left] = list[right];
     
    		// 从序列左端开始，向右遍历，直到找到大于base的数
    		while (left < right && list[left] <= base)
    			left++;
    		// 找到了比base大的元素，将这个元素放到最右边的位置
    		list[right] = list[left];
    	}
     
    	// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
    	// 而left位置的右侧数值应该都比left大。
    	list[left] = base;
    	return left;
    }
     
    // 快速排序
    void QuickSort(vector<int> &list, int left, int right){ 
    	// 左下标一定小于右下标，否则就越界了
    	if (left < right) { 
    		// 对数组进行分割，取出下次分割的基准标号
    		int base = division(list, left, right);
     
    		// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
    		QuickSort(list, left, base - 1);
     
    		// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
    		QuickSort(list, base + 1, right);
    	}
    }
    
    // 简单选择排序
    vector<int> SelectSort(vector<int> list){ 
    	// 需要遍历获得最小值的次数
    	// 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
    	vector<int> result = list;
    	for (int i = 0; i < result.size(); i++){ 
    		// 用来保存最小值得索引
    		int index = i;
    		// 用来保存最小值得索引
    		for (int j = i + 1; j < result.size(); j++){ 
    			if (result[index] > result[j]){ 
    				index = j;
    			}
    		}
    		// 将找到的第i个小的数值放在第i个位置上
    		swap(result[i], result[index]);
    		cout << "第" << i + 1<< "趟:\t";
    		for (int i = 0; i < result.size(); i++){ 
    			cout << result[i] << " ";
    		}
    		cout << endl;
    	}
    	return result;
    }
    
    // 堆排序的初始化函数
    void HeapAdjust(vector<int> &list, int parent, int length){ 
    	int temp = list[parent];					// temp保存当前父节点
    	int child = 2 * parent + 1;					// 先获得左孩子
     
    	while (child < length){ 
    		// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
    		if (child + 1 < length && list[child] < list[child + 1]){ 
    			child++;
    		}
     
    		// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
    		if (temp >= list[child]){ 
    			break;
    		}
     
    		// 把孩子结点的值赋给父结点
    		list[parent] = list[child];
     
    		// 选取孩子结点的左孩子结点,继续向下筛选
    		parent = child;
    		child = 2 * parent + 1;
    	}
    	list[parent] = temp;
    }
     
    // 堆排序
    vector<int> HeadSort(vector<int> list){ 
    	int length = list.size();
    	// 循环建立初始堆
    	for (int i = length / 2; i >= 0; i--){ 
    		HeapAdjust(list, i, length);
    	}
     
    	// 进行n-1次循环，完成排序
    	for (int i = length - 1; i > 0; i--){ 
    		// 最后一个元素和第一元素进行交换
    		int temp = list[i];
    		list[i] = list[0];
    		list[0] = temp;
     
    		// 筛选 R[0] 结点，得到i-1个结点的堆
    		HeapAdjust(list, 0, i);
    		cout << "第" << length - i << "趟排序:";
    		for (int i = 0; i < list.size(); i++){ 
    			cout << list[i] << " ";
    		}
    		cout << endl;
    	}
    	return list;
    }
    
    // 归并排序的合并函数
    void Merge(vector<int> &input, int left, int mid, int right, vector<int> temp){ 
    	int i = left;				// i是第一段序列的下标
    	int j = mid + 1;			// j是第二段序列的下标
    	int k = 0;					// k是临时存放合并序列的下标
    	
    	// 扫描第一段和第二段序列，直到有一个扫描结束
    	while (i <= mid && j <= right){ 
    		// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
    		if (input[i] <= input[j]){ 
    			temp[k++] = input[i++];
    		}
    		else{ 
    			temp[k++] = input[j++];
    		}
    	}
    	// 若第一段序列还没扫描完，将其全部复制到合并序列
    	while (i <= mid){ 
    		temp[k++] = input[i++];
    	}
     
    	// 若第二段序列还没扫描完，将其全部复制到合并序列
    	while (j <= right){ 
    		temp[k++] = input[j++];
    	}
     
    	k = 0;
    	// 将合并序列复制到原始序列中
    	while (left <= right){ 
    		input[left++] = temp[k++];
    	}
    }
    
    // 归并排序
    void MergeSort(vector<int> &input, int left, int right, vector<int> temp){ 
    	if (left < right){ 
    		int mid = (right + left) >> 1;
    		MergeSort(input, left, mid, temp);
    		MergeSort(input, mid + 1, right, temp);
    		Merge(input, left, mid, right, temp);
    	}
    }
     
    // 归并排序
    void mergesort(vector<int> &input){ 
    	// 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
    	vector<int> temp(input.size());				
    	MergeSort(input, 0, input.size() - 1, temp);
    }
    
    // 基数排序的求出数组中最大数的位数的函数
    int MaxBit(vector<int> input){ 
    	// 数组最大值
    	int max_data = input[0];
    	for (int i = 1; i < input.size(); i++){ 
    		if (input[i] > max_data){ 
    			max_data = input[i];
    		}
    	}
     
    	// 数组最大值的位数
    	int bits_num = 0;
    	while (max_data){ 
    		bits_num++;
    		max_data /= 10;
    	}
     
    	return bits_num;
    }
     
    // 基数排序的取数xxx上的第d位数字
    int digit(int num, int d){ 
    	int pow = 1;
    	while (--d > 0){ 
    		pow *= 10;
    	}
    	return num / pow % 10;
    }
     
    // 基数排序
    vector<int> RadixSort(vector<int> input, int n){ 
    	// 临时数组，用来存放排序过程中的数据
    	vector<int> bucket(n);					
    	// 位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数
    	vector<int> count(10);				
    	// 从低位往高位循环
    	for (int d = 1; d <= MaxBit(input); d++){ 
    		// 计数器清0
    		for (int i = 0; i < 10; i++){ 
    			count[i] = 0;
    		}
     
    		// 统计各个桶中的个数
    		for (int i = 0; i < n; i++){ 
    			count[digit(input[i],d)]++;
    		}
     
    		/* * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为： [0, 2, * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中 * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的 * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在 * 7、6、5三个(8-5=3)位置 */
    		for (int i = 1; i < 10; i++){ 
    			count[i] += count[i - 1];
    		}
     
    		/* * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的顺序，不应该打 * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个 * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处 * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。 * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮 * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会 * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该 * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题 */
    		for (int i = n - 1; i >= 0; i--){ 
    			int k = digit(input[i], d);
    			bucket[count[k] - 1] = input[i];
    			count[k]--;
    		}
     
    		// 临时数组复制到 input 中
    		for (int i = 0; i < n; i++){ 
    			input[i] = bucket[i];
    		}
    	}
     
    	return input;
    }