いくつかのC言語で実施される順序付けアルゴリズム

6014 ワード

データ構造 C言語ソートアルゴリズム

並べ替えはデータ構造の中で常に試験する内容で、本文はいくつかの常用する並べ替えに対して整理を行って、それによって調べます.
最初に並べ替えを行う配列を定義します.

#define MAXSIZE 10
#include<stdio.h>

typedef struct
{
    int a[MAXSIZE];
    int length;
}List;

印刷配列関数


void Print(List *L)
{
    int i;
    for(i=0; i<L->length; i++)
        printf("%d ", L->a[i]);
    printf("
");
}

交換関数


void swap(List *L, int i, int j)
{
    int tmp = L->a[i];
    L->a[i] = L->a[j];
    L->a[j] = tmp;
}

並べ替えを選択


/***********    ***********
void SelectSort(List *L)
{
    int i, j;
    int min;
    for(i=0; i<L->length; i++)
    {
        min = i;
        for(j=i; j<L->length; j++)
        {
            if(L->a[min]>L->a[j])
            {
                min = j;
            }
        }
        if(i != min)
            swap(L, i, min);
    }

}

並べ替えを選択

/***********    ***********/
void InsertSort(List *L)
{
    int i, j;
    for(i=1; i<L->length; i++)
    {
        if(L->a[i] < L->a[i-1])
        {
            int key = L->a[i];
            for(j=i-1; L->a[j]>key && j>=0; j--)
                L->a[j+1] = L->a[j];
            L->a[j+1] = key;
        }
    }
}

/***********    ***********/
void ShellSort(List *L)
{
    int i, j;
    int increment = L->length;
    do
    {
        increment = increment/3;
        for(i=increment; i<L->length; i++)
        {
            if(L->a[i]<L->a[i-increment])
            {
                int tmp = L->a[i];
                for(j=i-increment; j>=0&&tmp<L->a[j]; j-=increment)
                    L->a[j+increment]=L->a[j];
                L->a[j+increment] = tmp;
            }
        }
    }while(increment);
}

クイックソート

/***********    ***********/

int Partation(List *L, int low, int high)
{
    int key = L->a[low];
    while(low<high)
    {
        while(low<high && key<=L->a[high])
            high --;
        swap(L, low, high);
        while(low<high && key>=L->a[low])
            low ++;
        swap(L, low, high);
    }
    return low;
}


void QuickSort(List *L, int low, int high)
{
    int mid;
    if(low<high)
    {
        mid = Partation(L, low, high);
        QuickSort(L, low, mid-1);
        QuickSort(L, mid+1, high);
    }
}

/************    ***********/

メイン関数

/*************   ***********/
int main()
{
    List L = {{9, 5, 3, 1, 2, 6, 7, 4, 8}, 9};
    InsertSort(&L);
// ShellSort(&L);
// QuickSort(&L);
// SelecttSort(&L);
// Print(&L);
}

Go channelはソース分析を実現します.