丁香综合在线,欧美日本另类精品久久,亚洲精品WWW久久久久久

類型：視頻轉換大�。�1.7M語言：中文評分：5.5
標簽：

立即下載

對于冒泡排序，大家肯定都熟知，每一輪的冒泡都將最大的數(shù)排到最前面，每一輪的時間復雜度是O(n)，如果要排序的數(shù)組大小為n，要經(jīng)過n輪才能將數(shù)組中所有元素排序，所以總共的時間復雜度為O(n2)。

關于冒泡排序的源碼如下：

迭代型冒泡排序
#include <stdio.h>

#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0

void BubbleSort(int *a, int len) //待排數(shù)組a以及它的長度len
{
    int ordered = false;
    int temp, i;

    while(len && !ordered)
    {
        ordered = true; //也許一趟排序過程中沒有發(fā)生交換，說明數(shù)組已有序
        for(i = 1; i < len; i++) //此時i從1開始比從0開始更好
        {
            if(a[i-1] > a[i])
            {
                ordered = false;
                temp = a[i];
                a[i] = a[i-1];
                a[i-1] = temp;
            }
        }
        len--;
    }
}

int main()
{
    int a[5] = {5,1,2,3,4};
    int i = 0;
    int len = length(a);
    BubbleSort(a,len);
    for(i = 0; i < len; i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

對于快速排序，選出一個樞紐元素，然后將這個樞紐元素和數(shù)組所有元素進行比較，把彼樞紐元素大的元素放在樞紐元素右邊，把比樞紐元素小的放在樞紐元素左邊，而對于一趟快速排序要比較n次，每一趟快排的時間復雜度是O(n)，接下來你要對快排劃分出來的兩個子數(shù)組進行遞歸快排，如果每一趟快排很平均的將數(shù)組劃分為兩個子數(shù)組，那么遞歸快排的深度就是O(lgn),所以總的時間復雜度就是O(nlgn)。

但是快排可以退化成冒泡，如果一旦每一趟快排，不幸的選擇出最大或最小元素作為樞紐元素，那么遞歸深度將變成n，則時間復雜度變成了O(n2)，此時快排的效率降到最低，退化為冒泡，所以快排對于樞紐元素的選擇上很關鍵，如果能選擇出每趟平均劃分數(shù)組的樞紐元素，那么快排的效率最高，如何選擇樞紐元素將成為衡量快排的關鍵，我推薦使用三者取中法來選擇，每趟快排前，先將數(shù)組開始位置，中間位置，以及結尾位置的三個元素進行比較，選擇其中的中間大的數(shù)做為樞紐元素，這樣可以降低退化成冒泡的風險，也可以使用任取一個數(shù)做為樞紐元素，這樣也可以降低風險。

我準備開始寫遞歸型的冒泡排序和遞歸型的快速排序，你會發(fā)現(xiàn)兩者的區(qū)別，以及為什么快排會比冒泡好的原因，以及如何將程序從冒泡寫成快排。

遞歸型冒泡排序
#include <stdio.h>

#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0

int Sort(int *a, int len)
{
    int ordered = true; //也許一趟排序過程中沒有發(fā)生交換，說明數(shù)組已有序
    int temp, i;
    for(i = 1; i < len; i++)  //由此可以看出Sort()的時間復雜度是O(n)，跟待排數(shù)組的長度有關。
    {
        if(a[i-1] > a[i])
        {
            ordered = false;
            temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
        }
    }
    return ordered;
}

void BubbleSort(int *a, int len) //冒泡排序的遞歸算法
{   
    if(len == 1) //如果只有一個元素，它就是最大的元素，無須在冒泡
        return;
    else
    {
        int ordered = Sort(a,len); //選出最大的元素，將所有比最大元素小的元素放在最大元素的左邊，而快排是將使用一個樞紐元素，將比樞紐元素大的放在樞紐右邊，小的放在左邊
        if(ordered)  //如果一趟冒泡，沒有交換元素，說明已有序
            return;
        BubbleSort(a,len-1); //遞歸冒泡出最大元素后面的所有元素，如果快排將作為快排的左遞歸
        //如果快排會有右遞歸
    }
}

int main()
{
    int a[10] = {10,1,5,2,4,3,6,7,9,8};
    int i = 0;
    int len = length(a);
    BubbleSort(a,len);
    for(i = 0; i < len; i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

遞歸快速排序
#include <stdio.h>

#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0

int Sort(int *a, int low, int high)
{
    int pivot = a[low]; //這里每次的樞紐元素都取了待排數(shù)組的第一個元素，記住是a[low],而不是a[0]
    if(low < high)  //時間復雜度是O(n),n是數(shù)組長度
    {
        while(a[high] >= pivot && low < high)
            high --;
        a[low] = a[high];

        while(a[low] <= pivot && low <high)
            low ++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

void QuickSort(int *a, int low, int high)
{
    if(low >= high)
        return ;
    else
    {
        int mid = Sort(a,low,high); //劃分子遞歸數(shù)組
        QuickSort(a,low,mid-1); //左遞歸
        QuickSort(a,mid+1,high); //右遞歸，一旦右遞歸mid+1=high，將退化成冒泡，遞歸深度將變成n，n為數(shù)組長度
    }
}
int main()
{
    int a[5] = {3,1,5,2,4};
    int i = 0;
    int len = length(a);
    QuickSort(a,0,len-1);
    for(i = 0; i < len; i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

由上可以看出，遞歸型的冒泡就是一個只有右子樹的遞歸樹，遞歸深度為O(n)，而好的快速排序，將產生一個平衡的二叉樹，遞歸深度為O(lgn)，所以快排是對冒泡的一個巨大的改進。