c語言中冒泡排序、插入排序、選擇排序演算法比較

     掌握良好常用的排序演算法，在實際的專案開發中可以節省很多的時間。每一種排序演算法在執行的效率上是存在差別的，這些微小的時間差，也許在平常的聯繫當中感覺不到，但是涉及到數據量比較大或者是在資源比較緊張的系統中就顯得尤其的重要，例如嵌入式系統。以下簡要介紹三種常用的排序演算法以及他們的執行效率的比較。

       冒泡排序：

       思路：將鄰近的兩個數字相比較，將較小的數調到前頭；有n個數就要進行n-1趟，第一次比較中要進行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位置上的所有元素往後移動一位，然後將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;
                }
            }
        }
    }

      效率比較：

       為了能夠更明顯的檢視其效果，而每個排序演算法則是將每個排序次執行。以下是測試程式主函數：

#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中文網！ 🎜