评论

收藏

[C++] 希尔排序,快速排序,堆排序,归并排序,基数排序的实现

编程语言 编程语言 发布于:2021-08-09 21:16 | 阅读数:408 | 评论:0

#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[i].key;//依次存入顺序表
}
}
void display(Sqlist &L)
{
for (int i = 1; i <= L->length; i++)
{
cout<< L->r[i].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[i].key < L->r[i - dk].key)
{
L->r[0] = L->r[i];//r[0]存储较小的那个
for (j = i - dk; j>0 && (L->r[0].key < L->r[j].key); j = j - dk)//让<i的“部分”有序
L->r[j + dk] = L->r[j];
L->r[j + dk] = L->r[0];
}
}
}
void ShellSort(Sqlist &L, int dlta[], int t)
{
//按增量序列dlta[0...t-1]对顺序表L作希尔排序
int k;
for (k = 0; k < t; ++k)
{
ShellInsert(L, dlta[k]);//一趟增量为dlta[k]的插入排序
}
}//ShellSort
//快速排序
int Partition(Sqlist &L, int low, int high)
{
int pivotkey;
L->r[0] = L->r[low];
pivotkey = L->r[low].key;
while (low < high)
{
while (low < high&&L->r[high].key >= pivotkey)--high;//比较后面部分,直到遇到比中心点小的
L->r[low] = L->r[high];
while (low < high && L->r[low].key <= pivotkey)++low;//换前面
L->r[high] = L->r[low];
}
L->r[low] = L->r[0];
return low;
}
void QSort(Sqlist &L, int low, int high)
{
int pivotloc;
if (low < high)//长度》1
{
pivotloc = Partition(L, low, high);
//将L.r[low..high]一分为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[i];
}
}
//堆排序
void HeapAdjust(elem R[], int s, int m)
{//R[s...m]中的关键字除了R[s]外均满足堆定义,本函数调整R[s]的关键字,使R[s...m]成为一个大根堆
int rc,j;
rc = R[s];
for (j = 2 * s; j <= m; j *= 2)//沿key较大的孩子结点向下筛选
{
if (j<m&&R[j]<R[j + 1])++j;//j为key较大的记录下标
if (rc >= R[j])break;
R[s] = R[j]; s = j;//rc应插入在s位置
}//for
R[s] = rc;//插入
}//HeapAdjust
void HeapSort(elem R[], int n)//对R[1]到R[n]进行堆排序
{
int i,t;
for (i = n / 2; i >= 1; i--)
HeapAdjust(R, i, n);//建初始堆
for (i = n; i > 1; i--)
{//进行n-1趟排序
t = R[1];//根与最后一个元素交换
R[1] = R[i];
R[i] = t;
//Swap(R[1], R[i]);//根与最后一个元素交换
HeapAdjust(R, 1, i - 1);//对R[1]到R[i-1]重新建堆
}//for
}//HeapSort
void display1(elem R[], int n)
{
for (int i = 1; i <= n; i++)
{
cout << R[i] << ",";//依次输出
}
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[i] <= input[j])//第一块中i个值比第二块小
output[k++] = input[i++];//较小者存入输出组(第一块)
else
output[k++] = input[j++];//较小者存入输出组(第二块)
}//while
while (i <= mid)//第一块没遍历完第二块结束了
{
output[k++] = input[i++];//剩下的直接存入out数组
}
while (j <= high)//第二块没遍历完第一块结束了
{
output[k++] = input[j++];//剩下的直接存入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[j] = input[j];
}//for
}//else
}//MergePass
void MergeSort(elem R1[], int size)
{
int R2[Max_size] = { 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[1];//存放最大数
////先求最大数,再求位数
//for (int i = 2; i <= n; i++)
//{
//if (maxData < R[i])
//maxData = R[i];
//}//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[n];
//int *count = new int[10];//计数器
//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[j] = 0;//清空计数器
//
//for (j = 1; j <= n; j++)//统计每个桶中的记录
//{
//k = (R[j] / radix) % 10;
//count[k]++;
//}
//
//for (j = 1; j < 10; j++)
//count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
//
//for (j = n ; j > 0; j--) //将所有桶中记录依次收集到tmp中
//{
//cout << "n:" << n << endl;
//cout << "ftmpi:" << i << endl;
//k = (R[j] / radix) % 10;
//tmp[count[k] - 1] = R[j];
//cout << "1112" << endl;
//count[k]--;
//cout << "j" << j << endl;
//}
//cout << "fori:" << i << endl;
//for (j = 1; j <= n; j++) //将临时数组的内容复制到R中
//R[j] = tmp[j];
//radix = radix * 10;
//cout << "111";
//}
//delete[]tmp;
//delete[]count;
//}
int maxbit(int data[], int n) //辅助函数,求数据的最大位数
{
int maxData = data[0];        // 最大数
/// 先求出最大数,再求其位数
for (int i = 1; i < n; ++i)
{
if (maxData < data[i])
maxData = data[i];
}
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[n];
int *count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for (i = 1; i <= d; i++) //进行d次排序
{
for (j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for (j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for (j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
int main()
{
char ch1, ch2;
int delta[4] = { 5, 3, 2, 1 };
int R1[Max_size], n1, R2[Max_size], n2, R3[Max_size], 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[i];
}
//Createarray(R3, n3);
cout << "创建成功,当前顺序:" << endl;
for (int i = 0; i < n3; i++)
{
cout << R3[i] << ",";//依次输出
}
cout << endl;
//display1(R3, n3);
radixsort(R3, n3);
cout << "排序完成,当前顺序:" << endl;
for (int i = 0; i < n3; i++)
{
cout << R3[i] << ",";//依次输出
}
cout << endl;
//display1(R3, n3);
break;
case'0':
ch1 = 'n';
//delete[]ha;
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}
DSC0000.jpg

DSC0001.jpg

DSC0002.jpg

DSC0003.jpg

DSC0004.jpg

笔记:希尔排序,快速排序,堆排序_wx601562e1506ae的技术博客_51CTO博客


关注下面的标签,发现更多相似文章