冒泡排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define Maxsize 30

typedef int ValueType;
typedef int FlagType;
typedef int LengthType;

typedef struct BubbleTable{
    ValueType *ValueTable;
    LengthType RealLength;
}BubbleTable;

void InitTable(BubbleTable *BTable, ValueType Table[])
{
    BTable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            BTable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    BTable->RealLength=Length;
}

void BubbleSort(BubbleTable *BTable)
{
    if (BTable->RealLength<=1){return;}
    ValueType TempValue;
    FlagType Flag;
    for (int i=BTable->RealLength; i>=1; i--){
        Flag=0;
        for (int j=1; j<i; j++){
            if (BTable->ValueTable[j]<BTable->ValueTable[j-1]){
                TempValue=BTable->ValueTable[j];
                BTable->ValueTable[j]=BTable->ValueTable[j-1];
                BTable->ValueTable[j-1]=TempValue;
                Flag=1;
            }
        }
        if (Flag==0){return;}
    }
}

void ThroughTable(BubbleTable BTable)
{
    for (int i=0; i<BTable.RealLength; i++){
        printf("%d ", BTable.ValueTable[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    BubbleTable BTable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&BTable, Table);
    ThroughTable(BTable);
    BubbleSort(&BTable);
    ThroughTable(BTable);
}

 插入排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define Maxsize 30

typedef int ValueType;
typedef int IndexType;
typedef int LengthType;

typedef struct InsertTable{
    ValueType *ValueTable;
    LengthType RealLength;
}InsertTable;

void InitTable(InsertTable *ITable, ValueType Table[])
{
    ITable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            ITable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    ITable->RealLength=Length;
}

void InsertSort(InsertTable *ITable)
{
    if (ITable->RealLength<=1){return;}
    IndexType i, j;
    ValueType TempValue;
    for (i=1; i<ITable->RealLength; i++){
        TempValue=ITable->ValueTable[i];
        for (j=i-1; j>=0; j--){
            if (ITable->ValueTable[j]<TempValue){  // < 逆序; > 正序
                ITable->ValueTable[j+1]=ITable->ValueTable[j];
                continue;
            }
            break;
        }
        ITable->ValueTable[j+1]=TempValue;
    }
}

void BinInsertSort(InsertTable *ITable)
{
    if (ITable->RealLength<=1){return;}
    IndexType i, j, Low, Mid, High;
    ValueType TempValue;
    for (i=1; i<ITable->RealLength; i++){
        TempValue=ITable->ValueTable[i];
        Low=0, High=i-1;
        while(Low<=High){
            Mid=(Low+High)/2;
            if (ITable->ValueTable[Mid]>TempValue){
                High=Mid-1;
            }else{
                Low=Mid+1;
            }
        }
        for (j=i-1; j>=High+1; j--){
            ITable->ValueTable[j+1]=ITable->ValueTable[j];
        }
        ITable->ValueTable[High+1]=TempValue;
    }
}

void ThroughTable(InsertTable ITable)
{
    for (int i=0; i<ITable.RealLength; i++){
        printf("%d ", ITable.ValueTable[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    InsertTable ITable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&ITable, Table);
    ThroughTable(ITable);
    InsertSort(&ITable);
    ThroughTable(ITable);

    BinInsertSort(&ITable);
    ThroughTable(ITable);
    return 0;
}

归并排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <limits.h>

#define Maxsize 30

typedef int ValueType;
typedef int IndexType;
typedef int LengthType;

typedef struct MergeTable{
    ValueType *ValueTable;
    LengthType RealLength;

    ValueType *TempValueTable;   // Merge()
    ValueType *LeftValueTable;   // MERGE()
    ValueType *RightValueTable;
}MergeTable;

void InitTable(MergeTable *MTable, ValueType Table[])
{
    MTable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    MTable->TempValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    MTable->LeftValueTable=(ValueType *)malloc(sizeof(ValueType)*(Maxsize/2+1)); // 需要多出一个位置存储INT_MAX
    MTable->RightValueTable=(ValueType *)malloc(sizeof(ValueType)*(Maxsize/2+1));
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            MTable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    MTable->RealLength=Length;
}

// 两个有序序列合并
void Merge(MergeTable *MTable, IndexType Low, IndexType Mid, IndexType High)
{
    IndexType MoveLeft, MoveRight, MoveIndex;
    for (MoveIndex=Low; MoveIndex<=High; MoveIndex++){
        MTable->TempValueTable[MoveIndex]=MTable->ValueTable[MoveIndex];
    }
    for (MoveLeft=Low, MoveRight=Mid+1, MoveIndex=MoveLeft; MoveLeft<=Mid&&MoveRight<=High; MoveIndex++){
        if (MTable->TempValueTable[MoveLeft]<=MTable->TempValueTable[MoveRight]){
            MTable->ValueTable[MoveIndex]=MTable->TempValueTable[MoveLeft++];  // 先用在自增
        }else{
            MTable->ValueTable[MoveIndex]=MTable->TempValueTable[MoveRight++];
        }
    }
    while (MoveLeft<=Mid){
        MTable->ValueTable[MoveIndex++]=MTable->TempValueTable[MoveLeft++];
    }
    while (MoveRight<=High){
        MTable->ValueTable[MoveIndex++]=MTable->TempValueTable[MoveRight++];
    }
}

void MSort(MergeTable *MTable, IndexType Low, IndexType High)
{
    if (Low<High){
        IndexType Mid=(Low+High)/2;
        MSort(MTable, Low, Mid);
        MSort(MTable, Mid+1, High);
        Merge(MTable, Low, Mid, High);
    }
}


void MergeSort(MergeTable *MTable)
{
    if (MTable->RealLength<=1){return;}
    MSort(MTable, 0, MTable->RealLength-1);
}

// 算法导论
void MERGE(MergeTable *MTable, IndexType Low, IndexType Mid, IndexType High)
{
    LengthType LeftLength=Mid-Low+1;
    LengthType RightLength=High-Mid;
    IndexType LeftIndex, RightIndex, MoveIndex;
    for (LeftIndex=0; LeftIndex<LeftLength; LeftIndex++){
        MTable->LeftValueTable[LeftIndex]=MTable->ValueTable[LeftIndex+Low];
    }
    for (RightIndex=0; RightIndex<RightLength; RightIndex++){
        MTable->RightValueTable[RightIndex]=MTable->ValueTable[RightIndex+Mid+1];
    }
    MTable->LeftValueTable[LeftLength]=INT_MAX;
    MTable->RightValueTable[RightLength]=INT_MAX;
    LeftIndex=0, RightIndex=0;
    for (MoveIndex=Low; MoveIndex<=High; MoveIndex++){
        if (MTable->LeftValueTable[LeftIndex]<=MTable->RightValueTable[RightIndex]){
            MTable->ValueTable[MoveIndex]=MTable->LeftValueTable[LeftIndex++];
        }else{
            MTable->ValueTable[MoveIndex]=MTable->RightValueTable[RightIndex++];
        }
    }
}

void MSORT(MergeTable *MTable, IndexType Low, IndexType High)
{
    if (Low<High){
        IndexType Mid=(Low+High)/2;
        MSORT(MTable, Low, Mid);
        MSORT(MTable, Mid+1, High);
        MERGE(MTable, Low, Mid, High);
    }
}

void MERGESORT(MergeTable *MTable)
{
    if (MTable->RealLength<=1){return;}
    MSORT(MTable, 0, MTable->RealLength-1);
}

void ThroughTable(MergeTable MTable)
{
    for (int i=0; i<MTable.RealLength; i++){
        printf("%d ", MTable.ValueTable[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    MergeTable MTable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&MTable, Table);
    ThroughTable(MTable);
    MergeSort(&MTable);
    ThroughTable(MTable);

    MERGESORT(&MTable);
    ThroughTable(MTable);
    return 0;
}

快速排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define Maxsize 30

typedef int ValueType;
typedef int IndexType;
typedef int LengthType;

typedef struct QuickTable{
    ValueType *ValueTable;
    LengthType RealLength;
}QuickTable;

void InitTable(QuickTable *QTable, ValueType Table[])
{
    QTable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            QTable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    QTable->RealLength=Length;
}

// 中值划分数组
IndexType Partition(QuickTable *QTable, IndexType Low, IndexType High)
{
    ValueType PivotValue=QTable->ValueTable[Low];
    while (Low<High){
        while (Low<High&&QTable->ValueTable[High]>=PivotValue){
            High--;
        }
        QTable->ValueTable[Low]=QTable->ValueTable[High];
        while (Low<High&&QTable->ValueTable[Low]<=PivotValue){
            Low++;
        }
        QTable->ValueTable[High]=QTable->ValueTable[Low];
    }
    QTable->ValueTable[Low]=PivotValue;
    return Low;
}

void QSort(QuickTable *QTable, IndexType Low, IndexType High)
{
    IndexType PivotIndex;
    if (Low<High){
        PivotIndex=Partition(QTable, Low, High);
        QSort(QTable, Low, PivotIndex-1);
        QSort(QTable, PivotIndex+1, High);
    }
}

void QuickSort(QuickTable *QTable)
{
    if (QTable->RealLength<=1){return;}
    QSort(QTable, 0, QTable->RealLength-1);
}

// 算法导论
IndexType PARTITION(QuickTable *QTable, IndexType Low, IndexType High)
{
    ValueType PivotValue=QTable->ValueTable[High], TempValue;
    IndexType LessPivotIndex=Low-1;
    for (int i=Low; i<High; i++){
        if (QTable->ValueTable[i]<=PivotValue){
            LessPivotIndex++;
            TempValue=QTable->ValueTable[i];
            QTable->ValueTable[i]=QTable->ValueTable[LessPivotIndex];
            QTable->ValueTable[LessPivotIndex]=TempValue;
        }
    }
    LessPivotIndex=LessPivotIndex+1;
    QTable->ValueTable[LessPivotIndex]=PivotValue;
    return LessPivotIndex;
}

void QSORT(QuickTable *QTable, IndexType Low, IndexType High)
{
    IndexType PivotIndex;
    if (Low<High){
        PivotIndex=Partition(QTable, Low, High);
        QSort(QTable, Low, PivotIndex-1);
        QSort(QTable, PivotIndex+1, High);
    }
}

void QUICKSORT(QuickTable *QTable)
{
    if (QTable->RealLength<=1){return;}
    QSORT(QTable, 0, QTable->RealLength-1);
}

void ThroughTable(QuickTable QTable)
{
    for (int i=0; i<QTable.RealLength; i++){
        printf("%d ", QTable.ValueTable[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    QuickTable QTable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&QTable, Table);
    ThroughTable(QTable);
    QuickSort(&QTable);
    ThroughTable(QTable);
    QUICKSORT(&QTable);
    ThroughTable(QTable);
    return 0;
}

基数排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <limits.h>

#define QueueSize 10

typedef int ValueType;
typedef int PosType;
typedef int LengthType;
typedef int IndexType;
typedef int DividendType;
typedef int FlagType;

typedef struct LinkListNode{
    ValueType Value;
    struct LinkListNode *Next;
}LinkListNode;

typedef struct LinkList
{
    LinkListNode *Front, *Rear;
}LinkList;

typedef struct LinkListQueue{
    LinkListNode *Next, *Rear;
}LinkListQueue[QueueSize];

void CreateLListQueue(LinkListQueue *LListQueue)
{
    for (int i=0; i<QueueSize; i++){
        (*LListQueue)[i].Next=NULL;
        (*LListQueue)[i].Rear=NULL;
    }
}

void CreateLinkList(LinkList *LList, ValueType ValueTable[], LengthType Length)
{
    if (Length<=0){
        LList->Front=NULL;
        LList->Rear=NULL;
        return;
    }
    LList->Front=(LinkListNode *)malloc(sizeof(LinkListNode));  // 带头节点链表
    LList->Rear=LList->Front;
    LinkListNode *NewNode;
    for (int i=0; i<Length; i++){
        NewNode=(LinkListNode *)malloc(sizeof(LinkListNode));
        NewNode->Value=ValueTable[i];
        NewNode->Next=NULL;
        LList->Rear->Next=NewNode;
        LList->Rear=NewNode;
    }
}

void RadixSort(LinkList *LList, LinkListQueue *LListQueue)
{
    if (LList->Front==NULL&&LList->Rear==NULL){return;}
    IndexType Index, i;
    FlagType Flag=0;
    ValueType MaxValue=INT_MIN;
    LinkListNode *NowNode;
    DividendType Dividend=1;
    while (1){
        if (Flag==1&&MaxValue/Dividend%10==0){break;}
        NowNode=LList->Front->Next;
        while (NowNode){  //分配
            if (Flag==0&&NowNode->Value>MaxValue){
                MaxValue=NowNode->Value;
            }
            Index=NowNode->Value/Dividend%10;
            if ((*LListQueue)[Index].Next){
                (*LListQueue)[Index].Rear->Next=NowNode;
                (*LListQueue)[Index].Rear=(*LListQueue)[Index].Rear->Next;
            }else{
                (*LListQueue)[Index].Next=NowNode;
                (*LListQueue)[Index].Rear=(*LListQueue)[Index].Next;
            }
            NowNode=NowNode->Next;
            (*LListQueue)[Index].Rear->Next=NULL;
            LList->Front->Next=NowNode;
        }
        LList->Rear=LList->Front;
        for (i=0; i<QueueSize; i++){
            if ((*LListQueue)[i].Next){
                LList->Rear->Next=(*LListQueue)[i].Next;
                LList->Rear=(*LListQueue)[i].Rear;
                (*LListQueue)[i].Next=NULL;
                (*LListQueue)[i].Rear=NULL;
            }
        }
        Flag=1;
        Dividend=Dividend*10;
    }
}

void ThroughLinkList(LinkList LList)
{
    LinkListNode *NowNode=LList.Front->Next;
    while (NowNode){
        printf("%d ", NowNode->Value);
        NowNode=NowNode->Next;
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    // 收集队列
    LinkListQueue LListQueue;
    CreateLListQueue(&LListQueue); // --end
    // 数据链表
    LinkList LList;
    ValueType ValueTable[]={123, 234, 432, 654, 358, 190, 112, 789, 920, 531, 334, 555, 904, 109, 308, 652, 25, 9, 18};
    LengthType Length=sizeof(ValueTable)/sizeof(ValueType);
    CreateLinkList(&LList, ValueTable, Length); // --end 数据链表创建
    ThroughLinkList(LList);

    RadixSort(&LList, &LListQueue);
    ThroughLinkList(LList);
    return 0;
}

选择排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define Maxsize 30

typedef int ValueType;
typedef int IndexType;
typedef int LengthType;

typedef struct SelectTable{
    ValueType *ValueTable;
    LengthType RealLength;
}SelectTable;

void InitTable(SelectTable *SelTable, ValueType Table[])
{
    SelTable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            SelTable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    SelTable->RealLength=Length;
}

void SelectSort(SelectTable *SelTable)
{
    if (SelTable->RealLength<=1){return;}
    IndexType MinIndex;
    ValueType MinValue;
    for (int i=0; i<SelTable->RealLength; i++){
        MinIndex=i;
        MinValue=SelTable->ValueTable[MinIndex];
        for (int j=i+1; j<SelTable->RealLength; j++){
            if (MinValue>SelTable->ValueTable[j]){
                MinValue=SelTable->ValueTable[j];
                MinIndex=j;
            }
        }
        if (MinIndex!=i){
            SelTable->ValueTable[MinIndex]=SelTable->ValueTable[i];
            SelTable->ValueTable[i]=MinValue;
        }
    }
}

void ThroughTable(SelectTable SelTable)
{
    for (int i=0; i<SelTable.RealLength; i++){
        printf("%d ", SelTable.ValueTable[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    SelectTable SelTable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&SelTable, Table);
    ThroughTable(SelTable);
    SelectSort(&SelTable);
    ThroughTable(SelTable);
    return 0;
}

希尔排序

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define Maxsize 30

typedef int ValueType;
typedef int IndexType;
typedef int LengthType;

typedef struct ShellTable{
    ValueType *ValueTable;
    LengthType RealLength;
}ShellTable;

void InitTable(ShellTable *STable, ValueType Table[])
{
    STable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            STable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    STable->RealLength=Length;
}

void ShellSort(ShellTable *STable)   // 事实上会比插入排序快一点点
{
    IndexType i, j;
    ValueType TempValue;
    for (int step=STable->RealLength/2; step>=1; step=step/2){
        for (i=step; i<STable->RealLength; i++){
            if (STable->ValueTable[i]<STable->ValueTable[i-step]){
                TempValue=STable->ValueTable[i];
                for (j=i-step; j>=0&&STable->ValueTable[j]>TempValue; j-=step){
                    STable->ValueTable[j+step]=STable->ValueTable[j];
                }
                STable->ValueTable[j+step]=TempValue;
            }
        }
    }
}

void ThroughTable(ShellTable STable)
{
    for (int i=0; i<STable.RealLength; i++){
        printf("%d ", STable.ValueTable[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    ShellTable STable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&STable, Table);
    ThroughTable(STable);
    ShellSort(&STable);
    ThroughTable(STable);
}