iOS算法(一)置快速排序算法

快速排序是當(dāng)遇到較大數(shù)據(jù)時(shí),排序快,高效的方法(公司面試時(shí),基本上會(huì)被問(wèn)到...)

該方法的基本思想是：

1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。

2．分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。

3．再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。

簡(jiǎn)單地理解就是,找一個(gè)基準(zhǔn)數(shù)(待排序的任意數(shù),一般都是選定首元素),把比小于等于基準(zhǔn)數(shù)的元素放到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)的右邊.排完之后,在把基準(zhǔn)數(shù)的左邊和右邊各看成一個(gè)整體, 左邊:繼續(xù)選擇基準(zhǔn)數(shù)把小于等于基準(zhǔn)數(shù)的元素放到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)的右邊,右邊也是一樣..直到各區(qū)間只有一個(gè)數(shù)位置.

快速排序之所比較 快，因?yàn)橄啾让芭菖判?，每次交換是跳躍式的。每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基 準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然 就提高了。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個(gè)數(shù)進(jìn)行了交換。因此快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是O(N²)，它的平均時(shí)間復(fù)雜度為O(NlogN)。

圖片詮釋上面的思想

<書面語(yǔ)解釋>

1、算法思想
    　快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。

（1）分治法的基本思想
    　分治法的基本思想是：將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。

（2）快速排序的基本思想
    　設(shè)當(dāng)前待排序的無(wú)序區(qū)為R[low..high]，利用分治法可將快速排序的基本思想描述為：
①分解： 
    　在R[low..high]中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上，它無(wú)須參加后續(xù)的排序。
  注意：
    　劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos。劃分的結(jié)果可以簡(jiǎn)單地表示為(注意pivot=R[pivotpos])：
    　R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
                  其中low≤pivotpos≤high。
②求解： 
   　 通過(guò)遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

③組合： 
    　因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。

代碼實(shí)現(xiàn):

//

//  main.m

// 快速排序算法

//

//  Copyright (c) 2014年 summer2014mht@sina.com. All rights reserved.

//

#import <Foundation/Foundation.h>

#define COUNT 100      //定義數(shù)組元素的個(gè)數(shù)

int a[COUNT], n; //定義全局變量，這兩個(gè)變量需要在子函數(shù)中使用

//給快速排序方法連個(gè)參數(shù),開始位置(左),和結(jié)束位置(右)

void quicksort(int left, int right){

    int i, j, t, temp;

    if(left > right)  //開始位置坐標(biāo)大于結(jié)束位置坐標(biāo)時(shí),直接return,結(jié)束下面的操作

        return;

    temp = a[left];  //temp中存的就是基準(zhǔn)數(shù)(基準(zhǔn)數(shù)是隨機(jī)的,但一般都是第一個(gè)元素)

    i = left;

    j = right;

    while(i != j)

    {

        //順序很重要，要先從右邊開始找

        while(a[j] >= temp && i<j)

            j--;

        //再找左邊的

        while(a[i] <= temp && i<j)

            i++;

        //交換兩個(gè)數(shù)在數(shù)組中的位置

        if(i < j)

        {

            t = a[i];

            a[i] = a[j];

            a[j] = t;

        }

    }

    //此時(shí)i = j,最終將基準(zhǔn)數(shù)歸位

    a[left] = a[i];

    a[i] = temp;

    //遞歸調(diào)用

    quicksort(left, i-1);//繼續(xù)處理左邊的，這里是一個(gè)遞歸的過(guò)程

    quicksort(i+1, right);//繼續(xù)處理右邊的，這里是一個(gè)遞歸的過(guò)程

}

int main(int argc, const char * argv[])

{

    int i;

    //讀入數(shù)據(jù)

    scanf("%d", &n);

    for(i = 1; i <= n; i++){

        scanf("%d", &a[i]);

    }

    quicksort(1, n); //快速排序調(diào)用

    //輸出排序后的結(jié)果

    for(i = 1;i <= n; i++){

        printf("%d ", a[i]);

    }

    return 0;

}

//額外補(bǔ)充:算法復(fù)雜度及穩(wěn)定性一覽表