实验八：排序的基本操作
输入一组关键字序列分别实现下列排序:
（1）实现简单选择排序、直接插入排序和冒泡排序。
（2）实现希尔排序算法。
（3）实现快速排序算法。
（4）实现堆排序算法。
（5）采用链式存储实现简单选择排序、直接插入排序和冒泡排序。
（6）在主函数中设计一个简单的菜单，分别测试上述算法。
综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。
# include
# include
#define MAXSIZE 20
typedef int KeyType;
typedef struct
{
KeyType key;
//InfoType otherinfo;
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
typedef SqList HeapType;
typedef struct Node
{
int data;
struct Node * pNext;
}Node, *pNode;
void printMenu();
void InsertSort(SqList &);
bool LT(int ,int );
void traverse(SqList &);
void SelectSort(SqList &);
int SelectMinKey(SqList &, int);
void BubbleSort(SqList &);
void ShellSort(SqList &L, int dlta[], int t);
void ShellInsert(SqList &L, int);
void Qsort(SqList &, int ,int);
int Partition(SqList &, int ,int);
void HeapSort(HeapType &);
void HeapAdjust(HeapType &, int ,int );
void Ltraverse(pNode &);
void LSelectSort(pNode &);
pNode LSelectMinkey(pNode &);
void LBubbleSort(pNode &);
int main()
{
int n;
SqList L;
pNode pHead, p, q;
if( !(pHead=(pNode)malloc(sizeof(Node)) ))
exit (-1);
pHead->pNext = NULL;
int dlta[99] = {3, 2, 1};
printf("请输入数组长度L.length = ");
scanf("%d", &L.length);
p = pHead;
for(int i=1; idata = L.r[i].key;
p->pNext = q;
p = q;
}
p->pNext = NULL;
printMenu();
while(scanf("%d", &n)!=EOF)
{
switch(n)
{
case 1:
SelectSort(L);
printf("---排序后的数组为：");
traverse(L);
break;
case 2:
InsertSort(L);
printf("---排序后的数组为：");
traverse(L);
break;
case 3:
BubbleSort(L);
printf("---排序后的数组为：");
traverse(L);
break;
case 4:
ShellSort(L, dlta, 2);
printf("---排序后的数组为：");
traverse(L);
break;
case 5:
Qsort(L, 1, L.length);
printf("---排序后的数组为：");
traverse(L);
break;
case 6:
HeapSort(L);
printf("---排序后的数组为：");
traverse(L);
break;
case 7:
LSelectSort(pHead);
Ltraverse(pHead);
break;
case 8:
BubbleSort(L);
traverse(L);
break;
case 9:
LBubbleSort(pHead);
Ltraverse(pHead);
break;
default:
printf("---输入有误，请重新输入！！---n");
}
printMenu();
}
return 0;
}
void printMenu()
{
printf("------排序菜单如下------n");
printf("1.简单选择排序n");
printf("2.直接插入排序n");
printf("3.冒泡排序n");
printf("4.希尔排序n");
printf("5.快速排序n");
printf("6.堆排序n");
printf("7.链式存储实现简单选择排序n");
printf("8.链式存储实现简单直接插入排序n");
printf("9.链式存储实现简单冒泡排序n");
printf("---请选择排序方式：");
}
void InsertSort(SqList &L)
{
int i, j;
for( i=2; i=b )
return false;
else
return true;
}
void traverse(SqList &L)
{
for( int i=1; i L.r[j].key)
{
t = L.r[i];
L.r[i] = L.r[j];
L.r[j] = t;
}
}
}
void ShellSort(SqList &L, int dlta[], int t)
{
int k;
for(k=0; k0 && LT(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 Qsort(SqList &L, int low, int high)
{
int pivotloc;
if(low=pivotkey)
--high;
L.r[low] = L.r[high];
while(low0; i--)
HeapAdjust( H, i, H.length );
for( i = H.length; i>1; i--)
{
t = H.r[1];
H.r[1] = H.r[i];
H.r[i] = t;
HeapAdjust(H, 1, i-1);
}
}
void HeapAdjust(HeapType &H, int s,int m)
{
int j;
RedType rc;
rc = H.r[s];
for( j=2*s; jpNext;
while( NULL != p)
{
printf("%d ", p->data);
p = p->pNext;
}
printf("n");
}
void LSelectSort(pNode &pHead)
{
pNode p, q;
int t;
q = (pNode)malloc(sizeof(Node));
for( p = pHead->pNext->pNext; NULL != p->pNext; p = p->pNext)
{
q = LSelectMinkey( p );
if( p->data != q->data)
{
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
pNode LSelectMinkey(pNode &p)
{
pNode q;
q = p;
int min;
min = q->data;
while( p != NULL)
{
if( p->data data;
q = p;
}
p = p->pNext;
}
return q;
}
void LBubbleSort(pNode &pHead)
{
int t;
pNode p,q;
//RedType t;
for( p=pHead->pNext; p->pNext->pNext != NULL; p = p->pNext)
for( q=p->pNext; q->pNext!=NULL; q=q->pNext)
{
if(p->data > q->data)
{
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
