3、随机产生100 个整数构成的序列,
分别以直接插入、希尔、快速、归并等排序算法排序,
并统计各自的比较次数
#include <iostream>
using namespace std;
typedef int KeyType;
typedef int InfoType;
# define Maxsize 200 //待排序序列中记录的最大个数
# define T 7
int InsertSortCount = 0, ShellSortCount = 0, QSortCount = 0, MergeSortCount = 0;
// 待排序表中每个数据元素的数据类型定义
typedef struct
{
KeyType key; //表示排序关键字
//InfoType otherinfo; //排序记录中的其他所有数据项
} RedType;
// 待排序数据表的数据类型定义
typedef struct
{
RedType r[Maxsize + 1]; //存放待排序全体记录
int length; //排序记录个数
} SqList;
//直接插入排序
void InsertSort(SqList& L)
{
int i, j;
for (i = 2; i <= L.length; i++)
{
InsertSortCount++;
if (L.r[i].key < L.r[i - 1].key) //小于时,将R[i]插入有序表
{
L.r[0] = L.r[i]; // R[0]作监测哨兵
L.r[i] = L.r[i - 1];
for (j = i - 2; L.r[0].key < L.r[j].key; j--) {
InsertSortCount++;
L.r[j + 1] = L.r[j]; //记录后移
}
L.r[j + 1] = L.r[0]; //插入到正确位置
}
}
}
//希尔排序
void ShellInsert(SqList& L,int dk) //步长为dk的插入排序
{
int i, j;
for (i = dk + 1; i <= L.length; i++) {
ShellSortCount++;
if (L.r[i].key < L.r[i - dk].key) //小于时,需将r[i]插入有序表
{
L.r[0] = L.r[i]; //为统一算法设置监视哨
for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk) {
L.r[j + dk] = L.r[j]; //记录后移
}
L.r[j + dk] = L.r[0]; //插入到正确位置
}
}
}
void ShellSort(SqList& L,int dita[],int t)
{ //按增量序列dlta[0,1…,t-1]对顺序表S作希尔排序
for (int k = 0;k < t;k++)
ShellInsert(L,dita[k]);
}
//快速排序
int Partition(SqList& L, int low, int high)
{
L.r[0] = L.r[low]; //以子表的第一个记录作为轴值记录
int pivotkey = L.r[low].key; //取轴值记录关键字
while (low < high) //从表的两端交替地向中间扫描
{
QSortCount++;
while (low < high && L.r[high].key >= pivotkey) high--;
if (low < high) L.r[low++] = L.r[high];
//将比轴值记录小的交换到低端
while (low < high && L.r[low].key <= pivotkey) low++;
if (low < high) L.r[high--] = L.r[low];
} //将比轴值记录大的交换到高端
L.r[low] = L.r[0]; //轴值（支点）记录到位
return low; //返回轴值（支点）记录所在位置
}
void QSort(SqList& L, int low, int high)
{ //对顺序表L中的子序列L.r[low…high]作快速排序
if (low < high)
{
int pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1); //对小于轴值序列实现递归排序
QSort(L, pivotloc + 1, high);
} //对大于轴值序列实现递归排序
}
//归并排序算法
void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{
int j, k;
for (j = m + 1, k = i; i <= m && j <= n; k++) {
MergeSortCount++;
if (SR[i].key <= SR[j].key) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
while (i <= m) TR[k++] = SR[i++];
while (j <= n) TR[k++] = SR[j++];
}
void Msort(RedType p1[], RedType p2[], int n, int l)
{
int i = 1, j;
while (i + 2 * l - 1 <= n)
{
Merge(p1, p2, i, i + l - 1, i + 2 * l - 1);
i = i + 2 * l;
}
if (i + l <= n) Merge(p1, p2, i, i + l - 1, n);
else for (j = i; j <= n; j++) p2[j] = p1[j];
}
void MergeSort(SqList& L)
{
int l = 1;
RedType s[101];
while (l < 100)
{
Msort(L.r, s, L.length, l);
l = l * 2;
Msort(s, L.r, L.length, l);
l = l * 2;
}
}
void display(SqList L) {
for (int i = 1; i <= 100; i++) {
cout << L.r[i].key << "\t";
if (i % 10 == 0) {
cout << endl;
}
}
}
int main() {
//int a[800];
///*
//rand() % n +a;
//其中的a是起始值，n-1+a是终止值，n是整数的范围
//*/
//for (int i = 0; i < 100; i++) {
// a[i] = rand() % 200 + 1;
//}
SqList L;
L.length = 100;
for (int i = 1; i <= 100; i++) {
L.r[i].key = rand() % 200 + 1;
}
cout << "随机生成的100个数：" << endl;
display(L);
int dita[T] = { 49,37,29,23,19,11,1 };
int c = 1;
while (c)
{
cout << "+=====================================+" << endl;
cout << "| 1.直接插入排序 |" << endl;
cout << "| 2.希尔 |"<< endl;
cout << "| 3.快速 |"<< endl;
cout << "| 4.归并 |" << endl;
cout << "| 0.退出 |" << endl;
cout << "+=====================================+" << endl;
cout << "请选择：";
cin >> c;
switch (c)
{
case 1:
cout << endl << "直接插入排序：" << endl;
InsertSort(L);
display(L);
cout << "比较次数：" << InsertSortCount << endl;
cout << endl;
break;
case 2:
cout << endl << "希尔:" << endl;
ShellSort(L, dita, T);
display(L);
cout << "比较次数：" << ShellSortCount << endl;
cout << endl;
break;
case 3:
cout << endl << "快速:" << endl;
QSort(L, 0, 100);
display(L);
cout << "比较次数：" << QSortCount << endl;
cout << endl;
break;
case 4:
cout << endl << "归并:" << endl;
MergeSort(L);
display(L);
cout << "比较次数：" << MergeSortCount << endl;
cout << endl;
break;
default:
break;
}
}
//int dita[10];
//int t = 10;
//for (int i = 0; i < t; i++) {
// if (i == 0) {
// dita[0] = 49;
// }
// else {
// dita[i] = dita[i - 1] / 2 + 1;
// if (dita[i] <= 1) {
// dita[i] = 1;
// }
// }
//}
return 0;
}
