前言

查找和排序是數(shù)據(jù)結(jié)構(gòu)與算法中不可或缺的一環(huán)，是前輩們?cè)谒惴ǖ缆飞狭粝碌闹匾曳奖愕囊恍┘记?，學(xué)習(xí)這些經(jīng)典的查找和排序也能讓我們更好和更快的解決問(wèn)題。在這個(gè)專欄中我們會(huì)學(xué)習(xí)六大查找和十大排序的算法與思想，而本篇將詳細(xì)講解其中的交換排序——冒泡排序和快速排序；

注意：本文中所有排序按照升序排序，降序只需要把邏輯反過(guò)來(lái)即可！

一、冒泡排序

1.基本思想

對(duì)于很多同學(xué)來(lái)說(shuō)冒泡排序是再熟悉不過(guò)了，冒泡的思想在于：不斷的比較兩個(gè)元素并交換，大的在右邊，小的在左邊；

 有一個(gè)數(shù)組{5, 1, 4, 2, 8, 4}

第一輪

• arr[0] = 5和 arr[1] = 1比較 5 > 1，交換；
• arr[2] = 4和 arr[1] = 5比較 5 > 4，交換；
• arr[2] = 5和 arr[3] = 2比較 5 > 2，交換；
• arr[3] = 5和 arr[4] = 8比較 5 < 8，不交換；
• arr[4] = 8和 arr[5] = 4比較 8 > 4，交換；

第二輪

從arr[1]開(kāi)始重復(fù)上述的步驟；

... ...直到循環(huán) N - 1 次，排序結(jié)束；

#include <stdio.h>
#include<stdlib.h>
 
//冒泡排序
void bubbleSort(int a[], int n)
{
    //一共要掃描n-1趟
    for(int i = 0; i < n - 1; i++)
    {
        //用來(lái)比較 交換
        for(int j = 0; j < n - i - 1; j++)
        {
            if(a[j] > a[j + 1])
            {
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp; 
            }
        }
    }
}
 
int main()
{
    int arr[] = {5, 1, 4, 2, 8, 4};
    int length = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, length);
    for(int i = 0; i < length; i++)
    {
        printf("%d", arr[i]);
    }
    system("pause");
    return 0;
}

那么問(wèn)題來(lái)了，問(wèn)題一：這里我們發(fā)現(xiàn)對(duì)于這個(gè)數(shù)組而言在第二輪排序就已經(jīng)排好了整體甚至穩(wěn)定的有序，剩下的循環(huán)就相當(dāng)于浪費(fèi)了，那么有沒(méi)有一種方法能夠判斷數(shù)組已經(jīng)有序？

還有這樣一個(gè)數(shù)組{4, 2, 1, 5, 6, 8}

問(wèn)題二：我們發(fā)現(xiàn){5, 6, 8}的部分是已經(jīng)有序了的，對(duì)于已經(jīng)有序的部分還要繼續(xù)比較，那么能不能確定出有序的部分和無(wú)序的部分的邊界呢？

2.優(yōu)化

針對(duì)問(wèn)題一，我們可以添加一個(gè)標(biāo)志，用來(lái)標(biāo)識(shí)數(shù)組是否有序：當(dāng)某一輪排序沒(méi)有發(fā)生交換，就可以認(rèn)為數(shù)組已經(jīng)有序了；

針對(duì)問(wèn)題二，我們可以記錄冒泡排序的過(guò)程中最后一次發(fā)生交換的地方index，如在下圖中index==1，每一次后面的排序只要從第一個(gè)到index就可以了；

值得注意的是，不管怎樣去優(yōu)化，最壞情況的時(shí)間復(fù)雜度都是O(n^2)，即數(shù)組逆序的情況；

3.擴(kuò)展

雖然用棧實(shí)現(xiàn)冒泡排序可能在實(shí)際中沒(méi)有應(yīng)用場(chǎng)景（也沒(méi)必要用），但是可能會(huì)有面試的時(shí)候要求用?；蛘咂渌慕Y(jié)構(gòu)去實(shí)現(xiàn)冒泡排序來(lái)考查對(duì)算法和思想熟練度，所以這里也提供用棧實(shí)現(xiàn)冒泡排序的思路；

void bubbleSort(int a[], int n)
{
    //定義兩個(gè)棧S1和S2
    stack<int>stk1, stk2;
    //將數(shù)組中的所有元素入棧S1
    for (int i = 0; i < n; i++)
    {
        stk1.push(a[i]);
    }
    //循環(huán)N次 每一次找出最大的元素（就像真冒泡一樣 最大的元素浮在最上面）
    for (int i = 0; i < n; i++)
    {
        //如果S1不為空
        while (!stk1.empty())
        {
            //如果S2為空就把棧S1頂?shù)脑厝霔2
            if (stk2.empty())
            {
                stk2.push(stk1.top());
                stk1.pop();
            }
            else
            {
                int temp = 0;//用于接收需要交換的元素
                if (stk1.top() < stk2.top())
                {
                    //如果S1的棧頂小于S2的棧頂 把S1的棧頂壓在S2的棧頂下面
                    temp = stk2.top();
                    stk2.pop();
                    stk2.push(stk1.top());
                    stk1.pop();
                    stk2.push(temp);
                }
                else
                {
                    stk2.push(stk1.top());
                    stk1.pop();
                }
            }
        }
        //把最大的元素從后往前更新回原數(shù)組中
        a[n - i - 1] = stk2.top();
        stk2.pop();
        //把剩下的元素倒棧 重復(fù)
        for (int j = stk2.size(); j > 0; j--)
        {
            stk1.push(stk2.top());
            stk2.pop();
        }
    }
}

二、快速排序

1.基本思想

選取一個(gè)基準(zhǔn)（可以認(rèn)為是要放到排序以后正確的位置的元素，可以是第一個(gè)元素、最后一個(gè) 中間的、隨機(jī)的都可以）；

把數(shù)組中的元素做一個(gè)劃分，每一趟劃分將作為基準(zhǔn)的值x放到排序后數(shù)組正確的位置，并將所有比x小的放到左邊，比x大的放到右邊；

有一個(gè)數(shù)組{1, 8, 3, 9, 4, 5, 4, 7}

假定選擇元素arr[7] = 7為基準(zhǔn)，就是要把7放在正確的位置，那么只有兩種情況：

要么7本身就是正確的位置，要么就在前面；

第一步：初始化指針 i = -1，j = 0，把 j 指向的元素和7比較 ，當(dāng)1 < 7，將 i++， 交換 i 和 j 指向的元素，j++；

第二步：把 j 指向的元素和7比較 ，當(dāng)8 > 7，將 j++；

第三步：把 j 指向的元素和7比較 ，當(dāng)3 < 7，將 i++， 交換 i 和 j 指向的元素，j++；

第四步：把 j 指向的元素和7比較 ，當(dāng)4 < 7，將 i++， 交換 i 和 j 指向的元素，j++；

第五步：把 j 指向的元素和7比較 ，當(dāng)5 < 7，將 i++， 交換 i 和 j 指向的元素，j++；

第五步：把 j 指向的元素和7比較 ，當(dāng)4 < 7，將 i++， 交換 i 和 j 指向的元素，j++；

第六步：當(dāng)j到7遍歷結(jié)束，讓i++的位置和7交換，第一趟排序結(jié)束；

如此一來(lái)，基準(zhǔn)7就找到了它在數(shù)組中的正確位置，并且把數(shù)組劃分成了兩邊【0，5）和（5,7】這時(shí)再選一個(gè)基準(zhǔn)再進(jìn)行上述步驟，如下圖所示： 

是不是覺(jué)得很眼熟？沒(méi)錯(cuò)這就是一棵二叉樹(shù)：

2.優(yōu)化

既然是二叉樹(shù)，那么排出一棵斜樹(shù)自然就是最壞的情況；要緩解這個(gè)問(wèn)題，可以以中間的值為基準(zhǔn)來(lái)減少這種情況的發(fā)生；

即復(fù)雜度與數(shù)組長(zhǎng)度和基準(zhǔn)的選擇有關(guān)，尾基準(zhǔn)是O(n^2)因?yàn)閚趟每一趟劃分需要O(n)，而平衡樹(shù)是O(nlogn)，通過(guò)數(shù)學(xué)方法能夠得到更優(yōu)的基準(zhǔn)選擇，但無(wú)論選什么為基準(zhǔn)都應(yīng)該能滿足：基準(zhǔn)左邊小、右邊大；

我們之前說(shuō)過(guò)，快速排序其實(shí)是一個(gè)不穩(wěn)定排序（不穩(wěn)定的排序就意味著交換的次數(shù)多，如果需要按多條件排序就會(huì)亂），而我們又說(shuō)過(guò)任何一個(gè)不穩(wěn)定的排序算法都有辦法使其變得穩(wěn)定，用到的是以空間換時(shí)間的思想；

也就是我們可以用一個(gè)變量對(duì)原來(lái)的順序做標(biāo)記；

3.代碼

既然是通過(guò)不斷劃分?jǐn)?shù)組來(lái)減少比較的次數(shù)，這一聽(tīng)就知道用到了分治的思想，也就是可以用遞歸來(lái)實(shí)現(xiàn)代碼：

#include <stdio.h>
#include<stdlib.h>
 
//快排
void quickSort(int a[], int low, int high)
{
   if(low < high)
   {
        int i = low;//這里以i下標(biāo)的值為基準(zhǔn)
        int j = high;
        int k = a[low];//k是用來(lái)記錄基準(zhǔn)的值
        while(i < j)
        {
            //從右往左找第一個(gè)比k要小的值
            while(i < j && a[j] >= k)
            {
                j--;
            }
            if(i < j)
            {
                a[i++] = a[j];
            }
            //從左往右找第一個(gè)比k要大的值
            while(i < j && a[i] < k)
            {
                i++;
            }
            if(i < j)
            {
                a[j--] = a[i];
            }
        }
        a[i] = k;
        //遞歸
        quickSort(a, low, i - 1);
        quickSort(a, i + 1, high);
   }
}
 
int main()
{
    int arr[] = {1, 8, 3, 9, 4, 5, 4, 7};
    int length = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, length - 1);
    for(int i = 0; i < length; i++)
    {
        printf("%d ", arr[i]);
    }
    system("pause");
    return 0;
}

運(yùn)行結(jié)果

到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)交換排序算法(冒泡,快速排序)的示例代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言交換排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論