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

快速排序是當遇到較大數據時,排序快,高效的方法(公司面試時,基本上會被問到...)

該方法的基本思想是：

1．先從數列中取出一個數作為基準數。

2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。

3．再對左右區間重復第二步，直到各區間只有一個數。

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

快速排序之所比較 快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設置一個基準點，將小于等于基準點的數全部放到基準點的左邊，將大于等于基準點的數全部放到基 準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了。因此總的比較和交換次數就少了，速度自然 就提高了。當然在最壞的情況下，仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N²)，它的平均時間復雜度為O(NlogN)。

圖片詮釋上面的思想

<書面語解釋>

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

（1）分治法的基本思想
    　分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

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

③組合： 
    　因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。

代碼實現:

//

//  main.m

// 快速排序算法

//

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

//

#import <Foundation/Foundation.h>

#define COUNT 100      //定義數組元素的個數

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

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

void quicksort(int left, int right){

    int i, j, t, temp;

    if(left > right)  //開始位置坐標大于結束位置坐標時,直接return,結束下面的操作

        return;

    temp = a[left];  //temp中存的就是基準數(基準數是隨機的,但一般都是第一個元素)

    i = left;

    j = right;

    while(i != j)

    {

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

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

            j--;

        //再找左邊的

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

            i++;

        //交換兩個數在數組中的位置

        if(i < j)

        {

            t = a[i];

            a[i] = a[j];

            a[j] = t;

        }

    }

    //此時i = j,最終將基準數歸位

    a[left] = a[i];

    a[i] = temp;

    //遞歸調用

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

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

}

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

{

    int i;

    //讀入數據

    scanf("%d", &n);

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

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

    }

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

    //輸出排序后的結果

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

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

    }

    return 0;

}

//額外補充:算法復雜度及穩定性一覽表