#include <iostream>
#include"time.h"
using namespace std;
typedef int KeyType;
struct LElemType //顺序表元素
{
KeyType key;
};
struct SList
{
LElemType *r;
int length;
};
bool ListCreate(SList &L,int n,KeyType a[]);//创建顺序表
void Listshow(SList &L);//显示表
void InsertSort(SList L,int &fz,int &bj);//直接插入排序法
void SelectSort(SList L, int &fz, int &bj);//简单选择排序
int Partition(SList &L, int a, int b, int &fz, int &bj);
void QuickSort(SList L, int &fz, int &bj); //快速排序
void QSort(SList &L, int a, int b, int &fz, int &bj);
void HeapSort(SList H,int &fz,int &bj); //堆排序
void HeapSort(SList H,int &fz,int &bj);
void Merge(SList &L, int a, int m, int b,int &fz,int &bj);
void MergeSort(SList L,int &fz,int &bj); //归并排序
int main()
{
SList L; const int n = 1000; int fz, bj;
KeyType *a = new KeyType[n+1]; srand((unsigned)time(NULL));
for (int i = 1; i <= n; i++) {
a[i] = rand()%n;
}
ListCreate(L, n, a);
InsertSort(L, fz, bj);
cout << "直接插入排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
ListCreate(L, n, a);
SelectSort(L, fz, bj);
cout << "简单选择排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
ListCreate(L, n, a);
QuickSort(L, fz, bj);
cout << "快速排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
ListCreate(L, n, a);
HeapSort(L, fz, bj);
cout << "堆排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
ListCreate(L, n, a);
MergeSort(L, fz, bj);
cout << "归并排序" << "\n赋值次数：" << fz << " 比较次数：" << bj << endl << endl;
return 0;
}
bool ListCreate(SList &L,int n,KeyType a[])
{
L.r = new LElemType[n+1];
if (!L.r) {
return false;
}
L.length = n;
for (int i = 1; i <= n; i++) {
L.r[i].key = a[i];
}
return true;
}
void Listshow(SList &L)
{
int i=L.length;
for(int j=1;j<=i;j++)
{
cout<<L.r[j].key<<" ";
}
}
void InsertSort(SList L,int &fz,int &bj) {
fz = 0; bj = 0;
int i, j; LElemType x;
for (i = 2; i <= L.length; i++) {
for (fz++,x = L.r[i], j = i - 1; j >= 1 && (bj++, x.key < L.r[j].key); j--) {
L.r[j + 1] = L.r[j]; fz++;
}
L.r[j + 1] = x; fz++;
}
}
void SelectSort(SList L, int &fz, int &bj) {
fz = 0; bj = 0;
int i, j, k; LElemType x;
for (i = 1; i <= L.length-1; i++) {
k = i;
for (j = i + 1; j <= L.length; j++) {
if (bj++,L.r[j].key < L.r[k].key) k = j;
}
if (k > i) {
x = L.r[i]; fz++;
L.r[i] = L.r[k]; fz++;
L.r[k] = x; fz++;
}
}
}
int Partition(SList &L, int a, int b, int &fz, int &bj) {
LElemType x = L.r[a]; fz++;
while (a < b) {
while (a < b && (bj++,L.r[b].key >= x.key)) {
b--;
}
L.r[a] = L.r[b]; fz++;
while (a < b && (bj++,L.r[a].key <= x.key)) {
a++;
}
L.r[b] = L.r[a]; fz++;
}
L.r[a] = x; fz++; return a;
}
void QSort(SList &L, int a, int b, int &fz, int &bj) {
int p;
if (a >= b)return;
p = Partition(L, a, b,fz,bj);
QSort(L, a, p - 1,fz,bj); QSort(L, p + 1, b,fz,bj);
}
void QuickSort(SList L, int &fz, int &bj) {
fz = 0; bj = 0;
QSort(L, 1, L.length, fz, bj);
}
void HeapAdjust(SList &H, int s, int m,int &fz,int &bj) {
//设L.r[s+1:m]满足堆的条件，本算法调整H使H.r[s:m]为堆
int j; LElemType x;
x = H.r[s]; fz++; j = 2 * s;
while (j <= m) {
if (j < m && (bj++,H.r[j].key < H.r[j + 1].key)) j++;
if (bj++,x.key >= H.r[j].key) break;
H.r[s] = H.r[j]; fz++; s = j; j = 2 * j;
}
H.r[s] = x; fz++;
}
void HeapSort(SList H,int &fz,int &bj) {
fz = 0; bj = 0;
int i; LElemType x;
for (i = H.length / 2; i >= 1; i--) HeapAdjust(H, i, H.length,fz,bj);
//将H.r[1:H.length]建成堆
for (i = H.length; i >= 2; i--) {
x = H.r[1]; H.r[1] = H.r[i]; H.r[i] = x; fz += 3;
HeapAdjust(H, 1, i - 1,fz,bj);
}
}
void Merge(SList &L, int a, int m, int b,int &fz,int &bj) {
int i, j, k, s; LElemType *t;
t = new LElemType[m - a + 1]; i = 0; j = m + 1; k = a - 1;
for (s = a; s <= m; s++) { t[s - a] = L.r[s]; fz++; }
while (i <= m - a&&j <= b) {
k++;
if (bj++, t[i].key <= L.r[j].key) { L.r[k] = t[i]; fz++; i++; }
else { L.r[k] = L.r[j]; fz++; j++; }
}
while (i <= m - a) { k++; L.r[k] = t[i]; fz++; i++; }
delete[]t;
}
void MergeSort(SList L,int &fz,int &bj) {
fz = 0; bj = 0;
int a, b, m, h;
for (h = 1; h < L.length; h *= 2) {
for (a = 1;; a += 2 * h) {
m = a + h - 1; if (m >= L.length)break;
b = m + h; if (b > L.length) b = L.length;
Merge(L, a, m, b, fz, bj);
}
}
}