#include "sort.h"
#include <iostream>
using namespace std;
void SWAP (int &a, int &b)
{
int tp = a;
a = b;
b = tp;
}
void SHELLSORT (keytype K[], int n)
{
int i, j, gap = n, cc = 0, flag;
while (gap > 1)
{
gap >>= 1;
do{
flag = 0;
for (i = 0; i < n - gap; i++)
{
j = i + gap;
if (K[i] > K[j])
{
SWAP (K[i], K[j]);
flag = 1;
}
}
} while (flag);
printf ("第 %d 趟 gap = %d 结果:", ++cc, gap);
for (i = 0; i < n; i++)
cout << K[i] << ' ';
cout << endl;
}
}
void QUICKSORT (keytype K[], int s, int t, int &cc, int &n)
{
int i, j;
if (s < t)
{
i = s, j = t + 1;
while (1)
{
do i++;
while (!(K[s] <= K[i] || i == t));
do j--;
while (!(K[s] >= K[j] || j == s));
if (i < j)
{
SWAP (K[i], K[j]);
printf ("第 %d 次交换 ", ++cc);
for (int x = 1; x <= n; x++)
cout << K[x] << ' ';
cout << endl;
}
else break;
}
if (s != j)
{
SWAP (K[s], K[j]);
printf ("第 %d 次交换 ", ++cc);
for (int x = 1; x <= n; x++)
cout << K[x] << ' ';
cout << endl;
}
QUICKSORT (K, s, j-1, cc, n);
QUICKSORT (K, j+1, t, cc, n);
}
}
void ADJUST (keytype K[], int i, int n)
{
int j;
keytype tp;
tp = K[i];
j = 2 * i;
while (j <= n)
{
if (j < n && K[j] < K[j+1]) j++;
if (tp >= K[j]) break;
K[j/2] = K[j];
j = 2 * j;
}
K[j/2] = tp;
}
void HEAPSORT (keytype K[], int n)
{
int i, j, cc = 0;
for (i = n/2; i >= 1; i--)
ADJUST (K, i, n);
for (i = n - 1; i >= 1; i--)
{
SWAP (K[1], K[i+1]);
printf ("第 %d 趟 ", ++cc);
for (j = 1; j <= n; j++)
cout << K[j] << ' ';
cout << endl;
ADJUST (K, 1, i);
}
}
void INSERTSORT (keytype K[], int n)
{
int i, j;
keytype tp;
for (i = 1; i < n; i++)
{
tp = K[i];
j = i - 1;
while (j >= 0 && tp < K[j])
K[j+1] = K[j--];
K[j+1] = tp;
printf ("第 %d 趟 ", i);
for (j = 0; j < n; j++)
cout << K[j] << ' ';
cout << endl;
}
}
void MERGE (keytype X[], keytype Z[], int s, int u, int v)
{
int i, j, q;
i = s;
j = u + 1;
q = s;
while (i <= u && j <= v)
{
if (X[i] <= X[j])
Z[q++] = X[i++];
else Z[q++] = X[j++];
}
while (i <= u) Z[q++] = X[i++];
while (j <= v) Z[q++] = X[j++];
}
void MPASS (keytype X[], keytype Y[], int n, int t)
{
int i = 1, j;
while (n - i + 1 >= 2 * t)
{
MERGE (X, Y, i, i+t-1, i+2*t-1);
i = i + 2*t;
}
if (n - i + 1 > t) MERGE (X, Y, i, i+t-1, n);
else for (j = i; j <= n; j++)
Y[j] = X[j];
}
void MERGESORT (keytype X[], keytype Y[], int n)
{
int t = 1, cc = 0;
while (t < n)
{
MPASS (X, Y, n, t);
t <<= 1;
printf ("第 %d 趟 ", ++cc);
for (int i = 1; i <= n; i++)
cout << ' ' << Y[i];
cout << endl;
if (t <= n)
{
MPASS (Y, X, n, t);
printf ("第 %d 趟 ", ++cc);
for (int i = 1; i <= n; i++)
cout << ' ' << X[i];
cout << endl;
}
t <<= 1;
}
}
void SELECTSORT (keytype K[], int n)
{
int i, j, mins, v;
for (i = 0; i < n; i++)
{
v = i, mins = K[i];
for (j = i + 1; j < n; j++)
{
if (K[j] < mins)
{
mins = K[j];
v = j;
}
}
if (v != i)
{
SWAP (K[i], K[v]);
printf ("第 %d 趟 ", i+1);
for (j = 0; j < n; j++)
cout << ' ' << K[j];
cout << endl;
}
}
}
void BUBBLESORT (keytype K[], int n)
{
int i, j, flag = 1, cc = 0;
i = n - 1;
while (i > 0)
{
flag = 0;
for (j = 0; j < i; j++)
{
if (K[j] > K[j+1])
{
SWAP (K[j], K[j+1]);
flag = 1;
}
}
if (!flag) break;
i--;
printf ("第 %d 趟 ", ++cc);
for (j = 0; j < n; j++)
cout << ' ' << K[j];
cout << endl;
}
}
void DOUBLEBUBBLESORT (keytype K[], int n)
{
int j, s = 0, e = n - 1, flag = 0, cc = 0;
while (s < e)
{
flag = 0;
for (j = s; j < e; j++)
{
if (K[j] > K[j+1])
{
SWAP (K[j], K[j+1]);
flag = 1;
}
}
if (!flag) break;
e--;
printf ("第 %d 趟 ", ++cc);
for (j = 0; j < n; j++)
cout << ' ' << K[j];
cout << endl;
flag = 0;
for (j = e; j > s; j--)
{
if (K[j] < K[j-1])
{
SWAP (K[j], K[j-1]);
flag = 1;
}
}
if (!flag) break;
s++;
printf ("第 %d 趟 ", ++cc);
for (j = 0; j < n; j++)
cout << ' ' << K[j];
cout << endl;
}
}
Node *H[2][Max], *R[Max];
void Del (Node *T)
{
if (T == NULL) return ;
if (T->nxt != NULL) Del (T->nxt);
delete T;
}
void RSORT (char K[][Digit], int n, int r, int d)
{
int s = 0, i, j, id;
for (i = 0; i < r; i++)
{
H[0][i] = new Node;
H[1][i] = new Node;
}
for (i = 0; i < r; i++) R[i] = H[0][i];
for (i = 0; i < n; i++)
{
Node *p = new Node;
strcpy (p->data, K[i]);
p->len = strlen (p->data);
id = K[i][p->len-1] - '0';
R[id]->nxt = p;
R[id] = p;
}
printf ("第 %d 趟 ", 1);
for (i = 0; i < r; i++)
{
Node *p = H[0][i]->nxt;
while (p)
{
printf (" %s", p->data);
p = p->nxt;
}
}
printf ("\n");
for (j = 1; j < d; j++)
{
for (i = 0; i < r; i++)
{
Del (H[!s][i]->nxt);
R[i] = H[!s][i];
}
for (i = 0; i < r; i++)
{
Node *p = H[s][i]->nxt, *pre = H[s][i];
while (p)
{
int si = p->len-j-1;
if (si < 0) id = 0;
else id = p->data[si] - '0';
R[id]->nxt = p;
R[id] = p;
pre->nxt = p->nxt;
p->nxt = NULL;
p = pre->nxt;
}
}
printf ("第 %d 趟 ", j+1);
for (i = 0; i < r; i++)
{
Node *p = H[!s][i]->nxt;
while (p)
{
printf (" %s", p->data);
p = p->nxt;
}
}
printf ("\n");
s = !s;
}
}
void test1 ()
{
cout << "希尔排序测试过程:" << endl;
int i, n = 10;
keytype a[] = {199, 4, 2, 1, 9, 113, 43, 88, 53, 91};
cout << "初始:";
for (i = 0; i < n; i++)
cout << a[i] << ' ';
cout << endl;
SHELLSORT (a, n);
cout << endl;
}
void test2 ()
{
cout << "快速排序测试过程:" << endl;
int i, cc = 0, n = 10;
keytype a[] = {0, 199, 4, 2, 1, 9, 113, 43, 88, 53, 91};
cout << "初始:";
for (i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << endl;
QUICKSORT (a, 0, n, cc, n);
cout << endl;
}
void test3 ()
{
cout << "堆排序测试过程:" << endl;
int i, n = 10;
keytype a[] = {0, 26, 5, 77, 1, 61, 11, 59, 15, 48, 19};
cout << "初始:";
for (i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << endl;
HEAPSORT (a, n);
cout << endl;
}
void test4 ()
{
cout << "归并排序过程:" << endl;
keytype a[] = {0, 25, 57, 48, 37, 12, 82, 75, 29, 16};
keytype b[] = {0, 25, 57, 48, 37, 12, 82, 75, 29, 16};
cout << "初始:";
int i, n = 9;
for (i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << endl;
MERGESORT (a, b, n);
cout << endl;
}
void test5 ()
{
cout << "直接插入排序过程:" << endl;
keytype a[] = {199, 4, 2, 1, 9, 113, 43, 88, 53, 91};
cout << "初始:";
int i, n = 10;
for (i = 0; i < n; i++)
cout << a[i] << ' ';
cout << endl;
INSERTSORT (a, n);
cout << endl;
}
void test6 ()
{
cout << "选择排序过程:" << endl;
keytype a[] = {49, 38, 65, 97, 76, 13, 27, 49};
cout << "初始:";
int i, n = 8;
for (i = 0; i < n; i++)
cout << a[i] << ' ';
cout << endl;
SELECTSORT (a, n);
cout << endl;
}
void test7 ()
{
cout << "冒泡排序过程:" << endl;
keytype a[] = {49, 38, 65, 97, 76, 13, 27, 49};
cout << "初始:";
int i, n = 8;
for (i = 0; i < n; i++)
cout << a[i] << ' ';
cout << endl;
BUBBLESORT (a, n);
cout << endl;
}
void test8 ()
{
cout << "双向冒泡排序过程:" << endl;
keytype a[] = {49, 38, 65, 97, 76, 13, 27, 49};
cout << "初始:";
int i, n = 8;
for (i = 0; i < n; i++)
cout << a[i] << ' ';
cout << endl;
DOUBLEBUBBLESORT (a, n);
cout << endl;
}
void test9 ()
{
cout << "基数排序过程:" << endl;
char a[][Digit] = {"5467", "3241", "91", "4477", "5432", "3363", "4587"};
cout << "初始:";
int i, n = 7, r = 10, d = 4;
for (i = 0; i