落絮飞雁

顺流而下,把梦做完

排序——基本操作

实验八:排序的基本操作

输入一组关键字序列分别实现下列排序:
(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;
                            }
                   }
}