排序算法是算法的入門知識，在面試中經(jīng)常被問到排序算法及相關的問題，因此在學習的同時做一次總結。歡迎訪問作者的個人博客

冒泡排序

基本思想：是從左到右兩兩比較相鄰數(shù)據(jù)，若反序則進行交換。第一輪比較從0~N-1；第二輪0~N-2……最后一輪比較0~1。

時間復雜度：O(n)~O(n^2)

C代碼：

void bubble_sort(int a[], int N)
{
    for (int i=0; i<N-1; i++)
    {
        for (int j=0; j<N-1-i; j++)
        {
            if (a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

優(yōu)化：設置標志位，若某一輪沒有任何元素位置發(fā)生變化，則排序完成。

優(yōu)化代碼：

void bubble_sort(int a[], int N)
{
    int sort = 1;
    for(int i=0; i<N-1; i++)
    {
        for(int j=0; j<N-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                sort = 0;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
        if(sort) break;
    }
}

選擇排序

基本思路：在0~N-1選最小值放在0位置；在1~N-1選最小值放在1位置……在N-2~N-1選最小值放在N-2位置。

時間復雜度：O(n^2)

C代碼：

void select_sort(int a[], int N)
{
    for(int i=0; i<N-2; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            if(a[i] > a[j])
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

插入排序

基本思路：先比較位置0、1兩數(shù)，小值置左；再將位置2的數(shù)與已排好序的隊列從右向左依次比較，小值置左；再將位置3的數(shù)與已排好序的隊列從右向左依次比較，小值置左……最后將位置N-1的數(shù)與已排好序的隊列從右向左依次比較，小值置左。

時間復雜度：O(n^2)

C代碼：

void insert_sort(int a[], int N)
{
    for(int i=0; i<N-1;i++)
    {
        for(int j=i+1; j>0; j--)
        {
            if(a[j-1] > a[j])
            {
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
    }
}

同樣可以設置標志位進行優(yōu)化：

void insert_sort(int a[], int N)
{
    int sort = 1;
    for(int i=0; i<N-1;i++)
    {
        for(int j=i+1; j>0; j--)
        {
            if(a[j-1] > a[j])
            {
                sort = 0;
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
            if(sort) break;
        }
    }
}

結語

本篇文章總結了時間復雜度為O(n^2)的排序算法。如果對您有所幫助，歡迎對作者進行打賞，萬分感謝！