C언어의 버블정렬, 삽입정렬, 선택정렬 알고리즘 비교

일반적으로 사용되는 정렬 알고리즘을 익히면 실제 프로젝트 개발에서 많은 시간을 절약할 수 있습니다. 각 정렬 알고리즘의 실행 효율성에는 차이가 있습니다. 이러한 작은 시간 차이는 일반적인 연결에서는 느껴지지 않을 수 있지만, 임베디드 시스템과 같이 비교적 많은 양의 데이터가 있는 시스템에서는 특히 중요합니다. 다음은 일반적으로 사용되는 세 가지 정렬 알고리즘에 대한 간략한 소개와 실행 효율성을 비교한 것입니다.

버블 정렬:

아이디어: 인접한 두 숫자를 비교하고 n개의 숫자가 있는 경우 더 작은 숫자를 앞으로 이동합니다. 비교, n- 첫 번째 비교에서는 1개의 쌍별 비교를 수행하고, j번째 비교에서는 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;
                }
            }
    }

삽입 정렬:

아이디어: 배열을 정렬한 후 배열을 두 부분으로 나눕니다. 요소는 부분이고 나머지 요소는 부분입니다. 그런 다음 배열의 두 번째 요소부터 시작하여 이 요소보다 큰 이전 요소가 없는 경우 요소의 위치를 ​​비교합니다. 이 요소보다 값이 큰 요소가 있는 경우 해당 위치를 기록합니다. 예를 들어 I, 요소의 위치는 k인 경우 i부터 k 위치까지의 모든 요소가 1비트 뒤로 이동합니다. 그러면 k 위치는 i 위치로 값이 이동됩니다. 이로써 K의 위치를 ​​알아낸다. 각 요소에 대해 이 작업을 수행하면 정렬된 배열이 생성됩니다.

구현 코드:

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;
            }
    }
}

선택 정렬:

아이디어:

먼저, 한 요소를 기반으로 한 방향에서 스캔을 시작합니다. A[0]을 벤치마크로 삼아 왼쪽에서 오른쪽으로 스캔한 다음 A[0]...A[9]에서 가장 작은 요소를 찾아 A[0]과 교환합니다. 그런 다음 해당 기준 위치를 오른쪽으로 한 위치 이동하고 위 동작을 반복합니다. 예를 들어 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;
                }
            }
        }
    }

효율성 비교 :

그 효과를 보다 명확하게 확인하기 위해 각 정렬 알고리즘을 10,000번 실행합니다. 다음은 테스트 프로그램의 주요 기능입니다.

#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 언어의 버블 정렬, 삽입 정렬, 선택 정렬 알고리즘 추가 비교 관련 글은 PHP 중국어 홈페이지를 주목해주세요!