希尔排序，快速排序，堆排序，归并排序，基数排序的实现
#include<iostream>using namespace std;
typedef int KeyType;
typedef int OtherType;
typedef int elem;
#define Max_size 50
typedef struct
{
KeyType key;//关键字域
OtherType other_data;
}ElemType;
typedef struct{//顺序表结构类型定义
ElemType *r;//表基址
int length;//表长
}SSTable,*Sqlist;
void InitList(Sqlist &L)
{
L = (SSTable*)malloc(sizeof(SSTable));//给顺序表分配空间
L->r = (ElemType*)malloc(Max_size*sizeof(ElemType));
L->length = 0;
}
void CreateList(Sqlist &L)
{
cout << "请输入待排数据个数" << endl;
cin >> L->length;
cout << "请输入待排元素" << endl;
for (int i = 1; i <= L->length; i++)
{
cin >> L->r.key;//依次存入顺序表
}
}
void display(Sqlist &L)
{
for (int i = 1; i <= L->length; i++)
{
cout<< L->r.key<<",";//依次输出
}
}
void ShellInsert(Sqlist &L, int dk)
{//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
int i, j;
for (i = dk + 1; i <= L->length; i=i+dk)
{
if (L->r.key < L->r.key)
{
L->r = L->r;//r存储较小的那个
for (j = i - dk; j>0 && (L->r.key < L->r.key); j = j - dk)//让<i的“部分”有序
L->r = L->r;
L->r = L->r;
}
}
}
void ShellSort(Sqlist &L, int dlta[], int t)
{
//按增量序列dlta对顺序表L作希尔排序
int k;
for (k = 0; k < t; ++k)
{
ShellInsert(L, dlta);//一趟增量为dlta的插入排序
}
}//ShellSort
//快速排序
int Partition(Sqlist &L, int low, int high)
{
int pivotkey;
L->r = L->r;
pivotkey = L->r.key;
while (low < high)
{
while (low < high&&L->r.key >= pivotkey)--high;//比较后面部分，直到遇到比中心点小的
L->r = L->r;
while (low < high && L->r.key <= pivotkey)++low;//换前面
L->r = L->r;
}
L->r = L->r;
return low;
}
void QSort(Sqlist &L, int low, int high)
{
int pivotloc;
if (low < high)//长度》1
{
pivotloc = Partition(L, low, high);
//将L.r一分为2，pivotloc为枢轴元素排好序的位置
QSort(L, low, pivotloc - 1);//对低子表递归排序
QSort(L, pivotloc + 1, high);//对高子表递归排序
}//endif
}//QSort
void Createarray(elem R[],int n)
{
cout << "请输入待排元素" << endl;
for (int i = 1; i <= n; i++)
{
cin >> R;
}
}
//堆排序
void HeapAdjust(elem R[], int s, int m)
{//R中的关键字除了R外均满足堆定义，本函数调整R的关键字，使R成为一个大根堆
int rc,j;
rc = R;
for (j = 2 * s; j <= m; j *= 2)//沿key较大的孩子结点向下筛选
{
if (j<m&&R<R)++j;//j为key较大的记录下标
if (rc >= R)break;
R = R; s = j;//rc应插入在s位置
}//for
R = rc;//插入
}//HeapAdjust
void HeapSort(elem R[], int n)//对R到R进行堆排序
{
int i,t;
for (i = n / 2; i >= 1; i--)
HeapAdjust(R, i, n);//建初始堆
for (i = n; i > 1; i--)
{//进行n-1趟排序
t = R;//根与最后一个元素交换
R = R;
R = t;
//Swap(R, R);//根与最后一个元素交换
HeapAdjust(R, 1, i - 1);//对R到R重新建堆
}//for
}//HeapSort
void display1(elem R[], int n)
{
for (int i = 1; i <= n; i++)
{
cout << R << ",";//依次输出
}
cout << endl;
}
void Merge(int input[], int output[], int low, int mid, int high)
{//input[]为排序前数组，output[]为排序后数组
int i = low;//第一块开始下标
int j = mid + 1;//第二块开始下标
int k = low;//充当合并块下标
while ((i <= mid) && (j <= high))//判断两个分块矩阵结束
{
if (input <= input)//第一块中i个值比第二块小
output = input;//较小者存入输出组（第一块）
else
output = input;//较小者存入输出组（第二块）
}//while
while (i <= mid)//第一块没遍历完第二块结束了
{
output = input;//剩下的直接存入out数组
}
while (j <= high)//第二块没遍历完第一块结束了
{
output = input;//剩下的直接存入out数组
}
}//Merge
void MergePass(int input[], int output[], int length, int size)//第一个为输入，第二个为输出
{
int i = 1;
while (i + 2 * length - 1 <= size)//分块
{
Merge(input, output, i, i + length - 1, i + 2 * length - 1);//归并分块排序
i = i + 2 * length;//归并间隔，指向下一个分块起始点
}//while
if (i + length - 1 < size)
{//不足分成两个块，但前一个满足length，后一个用剩余数据
Merge(input, output, i, i + length - 1, size);
}//if
else
{//前一个都不够，直接复制到output
for (int j = i; j <= size; j++)
{
output = input;
}//for
}//else
}//MergePass
void MergeSort(elem R1[], int size)
{
int R2 = { 0 };
int length = 1;
while (length < size)
{
int u=1;
MergePass(R1, R2, length, size); // 归并，结果在 R2 中
length = 2 * length; // 改变归并长度，一般是二路归并
cout << "R2";
display1(R2, size); // 打印 R2
MergePass(R2, R1, length, size); // 归并，结果在 R1 中
length = 2 * length; // 改变归并长度
cout << "R1";
display1(R1, size); // 打印 R1
u++;
}
}
////基数排序
//int maxbit(int R[], int n)//求数据的最大位数
//{
//
//int maxData = R;//存放最大数
////先求最大数，再求位数
//for (int i = 2; i <= n; i++)
//{
//if (maxData < R)
//maxData = R;
//}//for
//int d = 1;//存放位数
//int p = 10;
////cout << maxData<<endl;
//while (maxData >= p)
//{
//maxData /= 10;
//++d;
//}
////cout << d;
//return d;
//}
////排序
//void radixsort(int R[], int n)
//{
//int d = maxbit(R, n);
////cout << d;
//int *tmp = new int;
//int *count = new int;//计数器
//int i, j, k;
//int radix = 1;//控制个，十，百，，，位数
//for (i = 1; i <= d; i++)//进行d次排序
//{
//cout <<"i:"<< i << endl;
//for (j = 0; j < 10; j++)
//count = 0;//清空计数器
//
//for (j = 1; j <= n; j++)//统计每个桶中的记录
//{
//k = (R / radix) % 10;
//count++;
//}
//
//for (j = 1; j < 10; j++)
//count = count + count; //将tmp中的位置依次分配给每个桶
//
//for (j = n ; j > 0; j--) //将所有桶中记录依次收集到tmp中
//{
//cout << "n:" << n << endl;
//cout << "ftmpi:" << i << endl;
//k = (R / radix) % 10;
//tmp - 1] = R;
//cout << "1112" << endl;
//count--;
//cout << "j" << j << endl;
//}
//cout << "fori:" << i << endl;
//for (j = 1; j <= n; j++) //将临时数组的内容复制到R中
//R = tmp;
//radix = radix * 10;
//cout << "111";
//}
//delete[]tmp;
//delete[]count;
//}
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
int maxData = data; // 最大数
/// 先求出最大数，再求其位数
for (int i = 1; i < n; ++i)
{
if (maxData < data)
maxData = data;
}
int d = 1;
int p = 10;
while (maxData >= p)
{
maxData /= 10;
++d;
}
return d;
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int *tmp = new int;
int *count = new int; //计数器
int i, j, k;
int radix = 1;
for (i = 1; i <= d; i++) //进行d次排序
{
for (j = 0; j < 10; j++)
count = 0; //每次分配前清空计数器
for (j = 0; j < n; j++)
{
k = (data / radix) % 10; //统计每个桶中的记录数
count++;
}
for (j = 1; j < 10; j++)
count = count + count; //将tmp中的位置依次分配给每个桶
for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data / radix) % 10;
tmp - 1] = data;
count--;
}
for (j = 0; j < n; j++) //将临时数组的内容复制到data中
data = tmp;
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
int main()
{
char ch1, ch2;
int delta = { 5, 3, 2, 1 };
int R1, n1, R2, n2, R3, n3;
Sqlist L;
ch1 = 'y';
while (ch1 == 'y')
{
cout << "----------希尔排序和快速排序----------" << endl;
cout << "------1.顺序表创建------" << endl;
cout << "------2.希尔排序 ------" << endl;
cout << "------3.快速排序 ------" << endl;
cout << "------4.堆排序 ------" << endl;
cout << "------5.归并排序 ------" << endl;
cout << "------6.基数排序 ------" << endl;
cout << "------0.退出 ------" << endl;
cout << "------请选择菜单号 ------" << endl;
cin >> ch2;
getchar();
cout << endl;
switch (ch2)
{
case'1':
//顺序表创建
InitList(L);
CreateList(L);
cout << "创建成功,当前顺序：" << endl;
display(L);
cout << endl;
break;
case'2':
//希尔排序
ShellSort(L, delta, 4);
cout << "排序完成，当前顺序：" << endl;
display(L);
cout << endl;
break;
case '3':
//快排
QSort(L, 1, L->length);
cout << "排序完成，当前顺序：" << endl;
display(L);
cout << endl;
break;
case'4':
//堆排序
cout << "输入待排个数：" << endl;
cin >> n1;
Createarray(R1, n1);
HeapSort(R1, n1);
display1(R1, n1);
break;
case'5':
//归并排序
cout << "输入待排个数：" << endl;
cin >> n2;
Createarray(R2, n2);
cout << "创建成功,当前顺序：" << endl;
display1(R2,n2);
MergeSort(R2, n2);
break;
case'6':
//基数排序
cout << "输入待排个数：" << endl;
cin >> n3;
cout << "请输入待排元素" << endl;
for (int i = 0; i < n3; i++)
{
cin >> R3;
}
//Createarray(R3, n3);
cout << "创建成功,当前顺序：" << endl;
for (int i = 0; i < n3; i++)
{
cout << R3 << ",";//依次输出
}
cout << endl;
//display1(R3, n3);
radixsort(R3, n3);
cout << "排序完成,当前顺序：" << endl;
for (int i = 0; i < n3; i++)
{
cout << R3 << ",";//依次输出
}
cout << endl;
//display1(R3, n3);
break;
case'0':
ch1 = 'n';
//delete[]ha;
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}
笔记：希尔排序，快速排序，堆排序_wx601562e1506ae的技术博客_51CTO博客
文档来源：51CTO技术博客https://blog.51cto.com/u_15098794/3319412
页:
[1]