#include <iostream>
#include <time.h>
#include <iomanip>
#include <math.h>
#include <queue>
using namespace std;
#define MAXSIZE 100
typedef int KeyTpye;
typedef struct
{
KeyTpye key;
}RedType;
typedef struct
{
RedType r[MAXSIZE + 1];
int length;
}SqList;
void Show(SqList &L)
{
for (int k = 1; k <= L.length; k++)
{
cout << setiosflags(ios::left) << setw(5) << L.r[k].key;
}
cout << endl << endl;
}
void InsertSort(SqList &L)
{
for (int i = 2; i <= L.length; i++)
{
if (L.r[i].key<L.r[i - 1].key)
{
L.r[0] = L.r[i];
L.r[i] = L.r[i - 1];
int j;
for (j = i - 2; L.r[0].key<L.r[j].key; j--)
L.r[j + 1] = L.r[j];
L.r[j + 1] = L.r[0];
}
cout << "第" << i - 1 << "躺:" << endl;
Show(L);
}
}
void SelectSort(SqList &L)
{
for (int i = 1; i<L.length; i++)
{
int k = i;
for (int j = i + 1; j <= L.length; j++)
{
if (L.r[j].key<L.r[k].key) k = j;
}
if (k != i)
{
RedType t = L.r[i];
L.r[i] = L.r[k];
L.r[k] = t;
}
cout << "第" << i << "躺:" << endl;
Show(L);
}
}
void BubbleSort(SqList &L)
{
int m = L.length - 1;
bool flag = 1;
while ((m>0) && (flag == 1))
{
flag = 0;
for (int j = 1; j <= m; j++)
{
if (L.r[j].key>L.r[j + 1].key)
{
flag = 1;
RedType t = L.r[j];
L.r[j] = L.r[j + 1];
L.r[j + 1] = t;
}
}
cout << "第" << L.length - m << "躺:" << endl;
Show(L);
--m;
}
}
int cnt = 1;
int Partition(SqList &L, int low, int high)
{
L.r[0] = L.r[low];
int 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];
//cout << "第" << cnt++ << "躺:" << endl;
//Show(L);
return low;
}
void QSort(SqList &L, int low, int high)
{
if (low<high)
{
int pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);
QSort(L, pivotloc + 1, high);
}
}
void QuickSort(SqList &L)
{
QSort(L, 1, L.length);
Show(L);
}
void ShellInsert(SqList &L, int dk)
{
for (int i = dk + 1; i <= L.length; i++)
{
if (L.r[i].key<L.r[i - dk].key)
{
L.r[0] = L.r[i];
int j;
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];
}
}
}
int dt[MAXSIZE];
void ShellSort(SqList &L, int dt[], int t)
{
for (int k = 0; k<t; k++)
{
ShellInsert(L, dt[k]);
cout << "第" << k + 1 << "躺:" << endl;
Show(L);
}
}
void HeapAdjust(SqList &L, int s, int m)
{
RedType rc = L.r[s];
int j;
for (j = 2 * s; j <= m; j *= 2)
{
if (j<m&&L.r[j].key<L.r[j + 1].key) ++j;
if (rc.key >= L.r[j].key) break;
L.r[s] = L.r[j];
s = j;
}
L.r[s] = rc;
}
void CreatHeap(SqList &L)
{
int n = L.length;
for (int i = n / 2; i>0; --i)
{
HeapAdjust(L, i, n);
}
}
void HeapSort(SqList &L)
{
CreatHeap(L);
for (int i = L.length; i>1; --i)
{
RedType x = L.r[1];
L.r[1] = L.r[i];
L.r[i] = x;
HeapAdjust(L, 1, i - 1);
cout << "第" << L.length - i + 1 << "躺:" << endl;
Show(L);
}
}
void Merge(RedType *R, RedType* &T, int low, int mid, int high)
{
int i = low;
int j = mid+1;
int k = 0;
while (i <= mid&&j <= high)
{
if (T[i].key <= T[j].key) R[k++] = T[i++];
else R[k++] = T[j++];
}
while (i <= mid) R[k++] = T[i++];
while (j<=high) R[k++] = T[j++];
for(int i=0;i<k;i++) T[low+i]=R[i];
}
void MSort(RedType *R, RedType* &T, int low, int high)
{
if (low == high) T[low] = R[low];
else
{
int mid = (low + high) / 2;
MSort(R, T, low, mid);
MSort(R, T, mid + 1, high);
Merge(R, T, low, mid, high);
}
}
void MergeSort(SqList &L)
{
RedType *p = new RedType[L.length+1];
RedType *t = L.r;
for (int i = 0; i <= 20; i++)
{
p[i].key=t[i].key;
}
MSort(p, t, 1, L.length);
Show(L);
delete[]p;
}
void RadixSort(SqList &L)
{
queue<RedType>q[11];
int cnt=3;
int id=10;
while(cnt--)
{
int pos=1;
for(int i=1;i<=L.length;i++)
{
q[L.r[i].key%id/(id/10)].push(L.r[i]);
}
for(int i=0;i<=9;i++)
{
while(!q[i].empty()) L.r[pos++]=q[i].front(),q[i].pop();
}
id*=10;
}
Show(L);
}
int main()
{
srand(time(0));
SqList L;
L.length = 20;
for (int i = 1; i <= 20; i++)
{
L.r[i].key = rand() % 1000;
}
/*L.r[1].key=49;
L.r[2].key=38;
L.r[3].key=65;
L.r[4].key=97;
L.r[5].key=76;
L.r[6].key=13;
L.r[7].key=27;
L.r[8].key=49;
L.length=8;*/
/*L.r[1].key=49;
L.r[2].key=38;
L.r[3].key=65;
L.r[4].key=97;
L.r[5].key=76;
L.r[6].key=13;
L.r[7].key=27;
L.r[8].key=49;
L.r[9].key=55;
L.r[10].key=4;
L.length=10;*/
cout << "原始数组:" << endl;
Show(L);
//cout<<"插入排序:"<<endl;
//InsertSort(L);
//cout<<"选择排序:"<<endl;
//SelectSort(L);
//cout<<"冒泡排序:"<<endl;
//BubbleSort(L);
//cout<<"快速排序:"<<endl;
//QuickSort(L);
//cout<<"希尔排序"<<endl;
/*int t=20;
int k=0;
while(t!=1)
{
t=(t+1)/2;
dt[k++]=t;
}
for(int i=0;i<k;i++) cout<<dt[i]<<" ";
ShellSort(L,dt,k);*/
//cout<<"堆排序"<<endl;
//HeapSort(L);
//cout << "归并排序" << endl;
//MergeSort(L);
cout<<"基数排序:"<<endl;
RadixSort(L);
return 0;
}
