原理:
快速排序,說白了就是給基準資料找其正確索引位置的程序.
如下圖所示,假設最開始的基準資料為陣列第一個元素23,則首先用一個臨時變數去存盤基準資料,即tmp=23;然后分別從陣列的兩端掃描陣列，設兩個指示標志:low指向起始位置，high指向末尾.
首先從后半部分開始，如果掃描到的值大于基準資料就讓high減1,如果發現有元素比該基準資料的值小(如上圖中18<=tmp)，就將high位置的值賦值給low位置 ,結果如下:
然后開始從前往后掃描,如果掃描到的值小于基準資料就讓low加1,如果發現有元素大于基準資料的值(如上圖46=>tmp)，就再將low位置的值賦值給high位置的值,指標移動并且資料交換后的結果如下:
然后再開始從后向前掃描,原理同上,發現上圖11<=tmp,則將low位置的值賦值給high位置的值,結果如下:
然后再開始從前往后遍歷,直到low=high結束回圈,此時low或high的下標就是基準資料23在該陣列中的正確索引位置.如下圖所示.
這樣一遍走下來,可以很清楚的知道,其實快速排序的本質就是把基準數大的都放在基準數的右邊,把比基準數小的放在基準數的左邊,這樣就找到了該資料在陣列中的正確位置.
以后采用遞回的方式分別對前半部分和后半部分排序，當前半部分和后半部分均有序時該陣列就自然有序了，
一些小結論
從上面的程序中可以看到:
①先從隊尾開始向前掃描且當low < high時,如果a[high] > tmp,則high–,但如果a[high] < tmp,則將high的值賦值給low,即arr[low] = a[high],同時要轉換陣列掃描的方式,即需要從隊首開始向隊尾進行掃描了
②同理,當從隊首開始向隊尾進行掃描時,如果a[low] < tmp,則low++,但如果a[low] > tmp了,則就需要將low位置的值賦值給high位置,即arr[low] = arr[high],同時將陣列掃描方式換為由隊尾向隊首進行掃描.
③不斷重復①和②,知道low>=high時(其實是low=high),low或high的位置就是該基準資料在陣列中的正確索引位置.
代碼：
#include<stdio.h>
void Swap(int arr[], int low, int high)
{
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int Partition(int arr[], int low, int high)
{
int base = arr[low];
while(low < high)
{
while(low < high && arr[high] >= base)
{
high --;
}
Swap(arr, low, high);
while(low < high && arr[low] <= base)
{
low ++;
}
Swap(arr, low, high);
}
return low;
}
void QuickSort(int arr[], int low, int high)
{
if(low < high)
{
int base = Partition(arr, low, high);
QuickSort(arr, low, base - 1);
QuickSort(arr, base + 1, high);
}
}
int main()
{
int n;
scanf("%d\n",&n);
int arr[n];
int i , j;
for(i = 0; i < n; i ++)
{
scanf("%d",&arr[i]);
}
printf("\n");
QuickSort(arr, 0, n-1);
for(j = 0; j < n; j ++)
{
printf("%4d",arr[j]);
}
return 0;
}
時間復雜度
O (nlogn)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/27168.html
標籤：嵌入式
下一篇：PE系統下的病毒入侵