【移動應用開發(fā)技術】iOS算法(一)置快速排序算法

快速排序是當遇到較大數(shù)據(jù)時,排序快,高效的方法(公司面試時,基本上會被問到...)該方法的基本思想是：1．先從數(shù)列中取出一個數(shù)作為基準數(shù)。2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。3．再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)。簡單地理解就是,找一個基準數(shù)(待排序的任意數(shù),一般都是選定首元素),把比小于等于基準數(shù)的元素放到基準數(shù)的左邊,把大于基準數(shù)的元素放在基準數(shù)的右邊.排完之后,在把基準數(shù)的左邊和右邊各看成一個整體,

左邊:繼續(xù)選擇基準數(shù)把小于等于基準數(shù)的元素放到基準數(shù)的左邊,把大于基準數(shù)的元素放在基準數(shù)的右邊,右邊也是一樣..直到各區(qū)間只有一個數(shù)位置.快速排序之所比較

快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設置一個基準點，將小于等于基準點的數(shù)全部放到基準點的左邊，將大于等于基準點的數(shù)全部放到基

準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然

就提高了。當然在最壞的情況下，仍可能是相鄰的兩個數(shù)進行了交換。因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N2)，它的平均時間復雜度為O(NlogN)。圖片詮釋上面的思想<書面語解釋>1、算法思想

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

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

設當前待排序的無序區(qū)為R[low..high]，利用分治法可將快速排序的基本思想描述為：①分解：

在R[low..high]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區(qū)劃分為左、右兩個較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區(qū)間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序。

注意：

劃分的關鍵是要求出基準記錄所在的位置pivotpos。劃分的結(jié)果可以簡單地表示為(注意pivot=R[pivotpos])：

R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

其中l(wèi)ow≤pivotpos≤high。②求解：

通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。③組合：

因為當"求解"步驟中的兩個遞歸調(diào)用結(jié)束時，其左、右兩個子區(qū)間已有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。代碼實現(xiàn):////

main.m//

快速排序算法////

Copyright(c)2014年summer2014mht@.Allrightsreserved.//#import<Foundation/Foundation.h>#defineCOUNT100

//定義數(shù)組元素的個數(shù)inta[COUNT],n;

//定義全局變量，這兩個變量需要在子函數(shù)中使用//給快速排序方法連個參數(shù),開始位置(左),和結(jié)束位置(右)voidquicksort(intleft,intright){

inti,j,t,temp;

if(left>right)

//開始位置坐標大于結(jié)束位置坐標時,直接return,結(jié)束下面的操作

return;

temp=a[left];

//temp中存的就是基準數(shù)(基準數(shù)是隨機的,但一般都是第一個元素)

i=left;

j=right;

while(i!=j)

{

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

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

j--;

//再找左邊的

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

i++;

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

if(i<j)

{

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

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

a[left]=a[i];

a[i]=temp;

//遞歸調(diào)用

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

quicksort(i+1,right);//繼續(xù)處理右邊的，這里是一個遞歸的過程}intmain(intargc,constchar*argv[]){

inti;

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

scanf("%d",&n);

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

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

}

quicksort(