C++ 排序的基本操作

发布时间： 更新时间： 总字数：1780 阅读时间：4m 作者： IP上海 分享 网址
专栏文章
  1. 顺序表的基本操作
  2. 链表
  3. C++ 单链表的基本操作
  4. 栈和队列的基本操作
  5. C++ 二叉树的基本操作
  6. 图的基本操作
  7. C++ 哈夫曼编码
  8. C++ 排序的基本操作（当前）
  9. C++ 双向链表的基本操作
  10. 顺序表的基本操作
  11. MFC中如何用ADO连接SQL Server 2005
  12. MFC使用ADO连接SQL Server数据库
  13. VC6 MFC中ClassView视图中无法显示某个类的问题
  14. rose生成C++源代码
  15. 解决<compilation debug="true" targetFramework="4.0"> 问题
  16. Cpp
  17. Clang 介绍
  18. Cpp
  19. CMake 使用介绍

C++ 排序的基本操作，实现简单选择排序、直接插入排序和冒泡排序；希尔排序；快速排序；堆排序；链式存储实现简单选择排序、直接插入排序和冒泡排序

实验八：排序的基本操作

输入一组关键字序列分别实现下列排序:

  1. 实现简单选择排序、直接插入排序和冒泡排序。
  2. 实现希尔排序算法。
  3. 实现快速排序算法。
  4. 实现堆排序算法。
  5. 采用链式存储实现简单选择排序、直接插入排序和冒泡排序。
  6. 在主函数中设计一个简单的菜单，分别测试上述算法。

综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。

源码

#include <stdio.h>
#include <stdlib.h>
#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; i <= L.length; i++ )
    {
        scanf( "%d", &L.r[i].key );
        if ( !(q = (pNode) malloc( sizeof(Node) ) ) )
            exit( -1 );
        q->data     = 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 <= L.length; i++ )
        if ( LT( L.r[i].key, L.r[i - 1].key ) )
        {
            L.r[0]  = L.r[i];
            L.r[i]  = L.r[i - 1];
            for ( j = i - 2; LT( L.r[0].key, L.r[j].key ); --j )
                L.r[j + 1] = L.r[j];
            L.r[j + 1] = L.r[0];
        }
}


bool LT( int a, int b )
{
    if ( a >= b )
        return(false);
    else
        return(true);
}


void traverse( SqList &L )
{
    for ( int i = 1; i <= L.length; i++ )
        printf( "%d ", L.r[i].key );
    printf( "\n\n" );
}


void SelectSort( SqList &L )
{
    int i, j;
    RedType t;
    for ( i = 1; i <= L.length; i++ )
    {
        j = SelectMinKey( L, i );
        if ( i != j )
        {
            t   = L.r[i];
            L.r[i]  = L.r[j];
            L.r[j]  = t;
        }
    }
}


int SelectMinKey( SqList &L, int j )
{
    int min, k;
    k   = j;
    min = L.r[k].key;
    for ( int i = j; i <= L.length; i++ )
    {
        if ( L.r[i].key < min )
        {
            min = L.r[i].key;
            k   = i;
        }
    }
    return(k);
}


void BubbleSort( SqList &L )
{
    int i, j;
    RedType t;
    for ( i = 1; i < L.length; i++ )
        for ( j = i + 1; j <= L.length; j++ )
        {
            if ( L.r[i].key > 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; k < t; k++ )
        ShellInsert( L, dlta[k] );
}


void ShellInsert( SqList &L, int dk )
{
    int i, j;
    for ( i = dk + 1; i <= L.length; i++ )
        if ( LT( L.r[i].key, L.r[i - dk].key ) )
        {
            L.r[0] = L.r[i];
            for ( j = i - dk; j > 0 &&
                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 < high )
    {
        pivotloc = Partition( L, low, high );
        Qsort( L, low, pivotloc - 1 );
        Qsort( L, pivotloc + 1, high );
    }
}


int Partition( SqList &L, int low, int high )
{
    int pivotkey;
    L.r[0]      = L.r[low];
    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];
    return(low);
}


void HeapSort( HeapType &H )
{
    int i;
    RedType t;
    for ( i = H.length / 2; i > 0; 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; j <= m; j *= 2 )
    {
        if ( j < m &&
             LT( H.r[j].key, H.r[j + 1].key ) )
            j++;
        if ( !LT( rc.key, H.r[j].key ) )
            break;
        H.r[s]  = H.r[j];
        s   = j;
    }
    H.r[s] = rc;
}


void Ltraverse( pNode &pHead )
{
    pNode p;
    p = pHead->pNext;
    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 < min )
        {
            min = p->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;
            }
        }
}
专栏文章
  1. 顺序表的基本操作
  2. 链表
  3. C++ 单链表的基本操作
  4. 栈和队列的基本操作
  5. C++ 二叉树的基本操作
  6. 图的基本操作
  7. C++ 哈夫曼编码
  8. C++ 排序的基本操作（当前）
  9. C++ 双向链表的基本操作
  10. 顺序表的基本操作
  11. MFC中如何用ADO连接SQL Server 2005
  12. MFC使用ADO连接SQL Server数据库
  13. VC6 MFC中ClassView视图中无法显示某个类的问题
  14. rose生成C++源代码
  15. 解决<compilation debug="true" targetFramework="4.0"> 问题
  16. Cpp
  17. Clang 介绍
  18. Cpp
  19. CMake 使用介绍
最近更新
相关文章
最新评论
Home Archives Categories Tags Statistics
本文总阅读量 次 本站总访问量 次 本站总访客数 人