C言語におけるバブルソート、挿入ソート、選択ソートアルゴリズムの比較-PHP开发-php.cn

C言語におけるバブルソート、挿入ソート、選択ソートアルゴリズムの比較

高洛峰

リリース： 2016-12-19 13:29:04

オリジナル

1937 人が閲覧しました

一般的に使用される並べ替えアルゴリズムをマスターすると、実際のプロジェクト開発にかかる時間を大幅に節約できます。各ソートアルゴリズムの実行効率には差があります。これらの小さな時間差は、通常の接続では感じられないかもしれませんが、組み込みシステムなど、比較的大量のデータやリソースが不足しているシステムでは特に重要です。以下に、一般的に使用される 3 つのソートアルゴリズムの簡単な紹介と、それらの実行効率の比較を示します。

を使用してを使用してを使用して - out out out out out out out out out through out of into into office through -1 番目の比較では、n-j のペア比較が実行されます。

実装コード:

void BublleSort (int arr [], int count)
    {
        int i, j, temp;
        for(j=0; j<count-1; j ) /* 冒泡法要排序n-1次*/
            for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
            {
                if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
                {
                    temp=arr[i 1];
                    arr[i 1]=arr[i];
                    arr[i]=temp;
                }
            }
    }

ログイン後にコピー

挿入ソート:

アイデア: ソート対象の配列を取得した後、配列を 2 つの部分に分割します。配列の最初の要素が 1 つの部分で、残りの要素が 1 つの部分です。 from 配列の 2 番目の要素から開始して、この要素より前のすべての要素と比較します。この要素より大きい値を持つ要素が存在する場合、要素の位置は変更されません。要素の位置を記録します。たとえば、要素の位置が k の場合、i から k の位置にあるすべての要素が 1 ビット前に移動され、k 位置の値が i の位置に移動されます。。このようにして、Ｋの位置が求められる。これを要素ごとに行うと、ソートされた配列が完成します。

実装コード:

void InsertSort ( int arr[],int count)
    {
            int i,j,temp;
        for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
        {
            temp = arr[i];//操作当前元素，先保存在其它变量中
            for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
            {
                arr[i] = arr[j];
                arr[j] = temp;
            }
    }
}

ログイン後にコピー

outアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトアウトスルースルースルースルースルースルースルースルースルースルー‐‐

0] につながります….A[9] は最小の要素を見つけて A[0] と交換します。次に、基準位置を 1 つ右に移動し、上記の操作を繰り返します。たとえば、A[1] を基準として、A[1] ～ A[9] の中で最小のものを見つけ、それを A[1] に置き換えます。。並べ替えは、基本位置が配列の最後の要素に移動すると終了します。

実装コード:

void SelectSort(int arr[], int count)
    {
        int i,j,min,temp;
        for(i=0; i<count; i )
            {
            min = arr[i];//以此元素为基准
            for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
            {
                if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中 
                {
                    temp = arr[j];
                    arr[j] = min;
                    min = temp;
                }
            }
        }
    }

ログイン後にコピー

効率比較:

一緒に外へ概要

への外へ ‐ アウトスルーアウトスルー 10000-,以下はテストプログラムの主な機能です:

#include <stdio.h>
#include<stdlib.h>
#include <sys/time.h>
#include <unistd.h>

#define MAX 6

int array[MAX];
int count = MAX;

/********创建数组，并输入元素************/
void BuildArray()
{
    int a,i=0;
    printf("请输入数组元素: ");
    for(; i<count; i )
    {
        scanf("%d", &a);
        array[i] = a;
    }
    printf("\n");
}
/**********遍历输出数组元素*************/
void Traverse(int arr[], int count)
{
    int i;
    printf("数组输出: ");
    for(i=0; i<count; i )
        printf("%d\t", arr[i]);
    printf("\n");
}
void BublleSort(int arr[], int count)
{
    int i,j,temp;
    for(j=0; j<count-1; j ) /* 气泡法要排序n-1次*/
        for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
        {
            if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
            {
                temp=arr[i 1];
                arr[i 1]=arr[i];
                arr[i]=temp;
            }
        }
}

void InsertSort(int arr[],int count)
{
    int i,j,temp;
    for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
    {
        temp = arr[i];//操作当前元素，先保存在其它变量中
        for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
        {
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

void SelectSort(int arr[], int count)
{
    int i,j,min,temp;
    for(i=0; i<count; i )
    {
        min = arr[i];//以此元素为基准
        for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
        {
            if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中 
            {
                temp = arr[j];
                arr[j] = min;
                min = temp;
            }
        }
    }
}

int main()
{ 
    int i;
    struct timeval tv1,tv2;
    struct timezone tz;
    BuildArray();//创建数组
    Traverse(array, count);//输出最初数组
    gettimeofday(&tv1,&tz);
    for(i=0;i<10000;i++)
        BublleSort(array, count);//冒泡排序
    gettimeofday(&tv2,&tz);
    printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
    Traverse(array, count);//输出排序后的数组
    
    gettimeofday(&tv1,&tz);
    for(i=0;i<10000;i++)
        InsertSort(array, count);//插入排序
    gettimeofday(&tv2,&tz);
    printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
    Traverse(array, count);//输出排序后的数组
     
    gettimeofday(&tv1,&tz);
    for(i=0;i<10000;i++)
        SelectSort(array, count);//插入排序
    gettimeofday (&tv2,&tz);
    printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec); 
    Traverse(array, count);//输出排序后的数组
    return 0;
}

ログイン後にコピー

コンパイル: gcc –g –Wall sort_test.c –o sort_test

実行: ./sort_test

結果は次のとおりです:

c语言中冒泡排序、插入排序、选择排序算法比较