排序算法总结（排序可视化-控制台版）
学完排序，于是写了一个排序过程可视化的控制台程序。
运行环境：win10
编译器 ：vs2017
编程语言：C++
上图：
代码：
#include<iostream>
#include<iomanip>
#include<windows.h>
#include<vector>
using namespace std;
const int MaxValue = 50; //数组中数据的最大值
int num = 0; //定义全局变量 数组个数
//移动光标位置函数
void gotoxy(int x, int y)
{
COORD pos = { x,y };
HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hOut, pos);
}
//清屏函数
void clear(vector<int> buf)
{
gotoxy(0, 0); //调用移动光标位置函数，每次绘图都从0，0位置开始
for (int i = 0; i < num; i++)
{
for (int j = 0; j < MaxValue; j++)
{
cout << " ";
}
cout << endl;
}
}
//绘图函数
void draw(vector<int> buf,int n = 0)
{
Sleep(100); //每次绘图的停顿时间(可自定义)
clear(buf); //绘图前清空控制台
gotoxy(0, 0);
//输出vector当前的排列顺序
for (int i = n; i < buf.size(); i++)
{
//输出该数字，占3格
cout << setw(3) <<left << buf[i];
//输出个数等同与该数字的“■”作为图像
for (int j = 0; j < buf[i]; j++)
{
cout << "■";
}
cout << endl;
}
}
//////////////////////// 冒泡排序 /////////////////////////
void BubbleSort(vector<int> &buf,int n = num)
{
for (int i = 0; i < n; i++)
{
bool flag = false; //表示本次冒泡是否发生了交换
for (int j = buf.size() - 1; j > i; j--) //一次冒泡过程
{
if (buf[j - 1] > buf[j]) //若为逆序
{
swap(buf[j - 1], buf[j]); //交换
flag = true; //表示发生了交换
draw(buf,0);
}
}
if (flag = false) //若本次冒泡没有发生交换，则说明表已经有序
{
return;
}
}
}
///////////////////////// 插入排序 /////////////////////////
void InsertSort(vector<int> &buf , int n = num)
{
int i,j;
for (i = 2; i <= n; i++) //依次将buf[2]到buf[n]插入到前面的已排序序列
{
if (buf[i] > buf[i - 1]) //若buf[i]小于其前驱，需将buf[i]插入有序表
{
buf[0] = buf[i]; //存入buf[0],(注意，待排序列下标是1 ~ n
for (j = i - 1; buf[0] > buf[j]; --j)//从后往前查找待插入位置
{
buf[j + 1] = buf[j]; //向后挪位
draw(buf,1);
}
buf[j + 1] = buf[0]; //复制到插入位置
draw(buf,1);
}
}
}
////////////////////////// 折半插入 /////////////////////
void InsertSorts(vector<int> &buf , int n = num)
{
int i, j, low, high, mid;
for (i = 2; i <= n; i++) //依次将buf[2]到buf[n]插入到前面的已排序序列
{
buf[0] = buf[i]; //将buf[i]暂存入buf[0]
low = 1; high = i - 1; //设置折半查找范围
while (low <= high) //折半查找
{
mid = (low + high) / 2; //取中间点
if (buf[mid] > buf[0])
{
high = mid - 1; //查找左半子表
}
else
{
low = mid + 1; //查找右半子表
}
}
for (j = i - 1; j >= high + 1; --j)
{
buf[j + 1] = buf[j]; //向后挪位
draw(buf, 1);
}
buf[j + 1] = buf[0]; //插入
draw(buf, 1);
}
}
////////////////////////// 希尔排序 ////////////////////////
void ShellSort(vector<int> &buf , int n = num)
{
int i, j;
for (int dk = n / 2; dk >= 1; dk = dk / 2)
{
for (i = dk + 1; i <= n; i++)
{
if (buf[i] < buf[i - dk])
{
buf[0] = buf[i];
for (j = i - dk; j > 0 && buf[0] < buf[j]; j -= dk)
{
buf[j + dk] = buf[j];
draw(buf, 1);
}
buf[j + dk] = buf[0];
draw(buf, 1);
}
}
}
}
/////////////////////////// 快速排序 ///////////////////
//快排--划分操作
int Partition(vector<int> &buf, int lows, int highs)
{
int pivot = buf[lows]; //将当前表中第一个元素设为基准值，对表进行划分
while (lows < highs) //循环跳出条件，当所有元素遍历一遍时lows等于highs
{
while (lows < highs&&buf[highs] >= pivot)
{
--highs;
}
buf[lows] = buf[highs]; //将比基准值小的元素移到左端
draw(buf, 0);
while (lows < highs&&buf[lows] <= pivot)
{
++lows;
}
buf[highs] = buf[lows]; //将比基准值大的元素移到右端
draw(buf, 0);
}
buf[lows] = pivot; //基准值存放到最终位置
draw(buf, 0);
return lows; //返回存放基准值的位置作为新表划分位置
}
//快排函数主体
void QuickSort(vector<int> &buf,int low = 0,int high = num)
{
if (low < high) //若low>=high说明此表只有一个元素或空
{
int pivotpos = Partition(buf, low, high); //划分位置
QuickSort(buf, low, pivotpos - 1); //将划分后的左表进入递归
QuickSort(buf, pivotpos + 1, high); //将划分后的右表进入递归
}
}
////////////////////////// 简单选择排序 ///////////////////////
void SelectSort(vector<int> &buf , int n = num)
{
for (int i = 0; i < n - 1; i++)
{
int min = i; //记录最小元素位置
for (int j = i + 1; j < n; j++) //在buf[i]到buf[n-1]中选择最小元素
{
if (buf[j] < buf[min])
{
min = j;//更新最小元素的位置
}
}
if (min != i)
{
swap(buf[i], buf[min]); //与第i个位置交换
draw(buf,0);
}
}
}
///////////////////////// 堆排序 //////////////////////
//堆排序--调整函数
void AdjustDown(vector<int> &buf, int k, int len)
{
buf[0] = buf[k]; //暂存入buf[0]
for (int i = 2 * k; i <= len; i *= 2) //沿key较大的子节点向下筛选
{
if (i < len&&buf[i] < buf[i + 1])
{
i++; //取key较大的子节点的下标
}
if (buf[0] >= buf[i])
{
break; //筛选结束
}
else
{
buf[k] = buf[i]; //将buf[i]调整到双亲结点上
k = i; //修改 k 值，以便继续向下筛选
}
}
buf[k] = buf[0]; //被筛选节点的值放入最终位置
}
//堆排序--建立大根堆
void BuildMaxHeap(vector<int> &buf,int len)
{
for (int i = len / 2; i > 0; i--) //从 n/2 到 1 ，反复调整堆
{
AdjustDown(buf, i, len);
}
}
//堆排序主体
void HeapSort(vector<int> &buf , int len = num)
{
BuildMaxHeap(buf, len); //初始建堆
for (int i = len; i > 1; i--) //n-1趟的交换和建堆过程
{
swap(buf[i], buf[1]); //输出堆顶元素（和堆底元素交换）
draw(buf, 1);
AdjustDown(buf, 1, i - 1); //把剩余的元素整理成为堆
}
}
/////////////////////// 归并排序 /////////////////////
//归并排序--合并算法
vector<int> buf_copy(20); //辅助数组
void Merge(vector<int> &buf, int low, int mid, int high)
{
int i, j, k;
for (int k = low; k <= high; k++)
{
buf_copy[k] = buf[k]; //将buf数组全部复制到buf_copy
}
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
{
if (buf_copy[i] <= buf_copy[j]) //比较buf_copy数组左右两段中的元素
{
buf[k] = buf_copy[i++]; //将较小值复制到buf中
draw(buf, 0);
}
else
{
buf[k] = buf_copy[j++];
draw(buf, 0);
}
}
while (i <= mid)
{
buf[k++] = buf_copy[i++]; //若前半段未检测完，则剩余部分全部复制进buf
draw(buf, 0);
}
while (j <= high)
{
buf[k++] = buf_copy[j++]; //若后半段未检测完，则剩余部分全部复制进buf
draw(buf, 0);
}
}
//归并函数主体
void MergeSort(vector<int> &buf, int low = 0, int high = num)
{
if (low < high)
{
int mid = (low + high) / 2; //从中间划分成两个子序列
MergeSort(buf, low, mid); //对左侧子序列进行递归调用
MergeSort(buf, mid + 1, high); //对右侧子序列进行递归调用
Merge(buf, low, mid, high); //归并
}
}
///////////////////////// 计数排序 ////////////////////////
//不属于比较排序，没有明显的位置交换过程，无可视化图形
void CountSort(vector<int>&buf)
{
int max = buf[0]; //定义max
for (int i = 0; i < buf.size(); i++) //遍历待排序列找到最大值max
{
if (buf[i] > max)
{
max = buf[i];
}
}
vector<int> buf_s(max + 1, 0); //创建一个大小为max+1的数组buf_s
for (int i = 0; i < buf.size(); i++) //遍历待排序列，录入buf_s数组
{
buf_s[buf[i]]++;
}
for (int i = 0, t = 0; i < max + 1; i++) //遍历buf_s存入buf数组
{
for (int j = buf_s[i]; j > 0; j--, t++)
{
buf[t] = i;
}
}
draw(buf);
}
////////////////// 主函数
int main()
{
int val; //val作为输入值录入数组
int flag = 2; //falg表示用户选择的数据生成方式
vector<int> buf; //待排数组
srand((int)time(0));
cout << "请输入数组个数：";
cin >> num;
cout << "请选择数据的生成方式：" << endl;
cout << "1,手动输入 2，随机生成" << endl;
cin >> flag;
if (flag == 1) //读取数据
{
for (int i = 0; i < num; i++)
{
cin >> val;
buf.push_back(val%MaxValue);
}
}
else if (flag == 2) //随机生成数据
{
for (int i = 0; i < num; i++)
{
val = rand()% MaxValue;
buf.push_back(val);
}
}
//使num等于最大下标
num = num - 1;
//调用排序函数
QuickSort(buf);
return 0;
}
欢迎大家检查补充，有问题可以在下面评论