#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);
}
// 基数排序
