会python真的可以为所欲为0(回)
349天前
这里还有人吗1(回)
534天前这里还有人吗0(回)
534天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
759天前到处都是羊，不想上班0(回)
839天前
鸽子
0(回)
843天前#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); |
} |
} |
} |
