快速排序是對(duì)冒泡排序的一種改進(jìn).
快速排序算法的基本思想是: 將所要進(jìn)行排序的數(shù)分為左右兩個(gè)部分, 其中一部分的所要數(shù)據(jù)都比另外一部分的數(shù)據(jù)小, 然后將所分得的兩部分?jǐn)?shù)據(jù)進(jìn)行同樣的劃分, 重復(fù)執(zhí)行以上劃分操作, 知道所有要進(jìn)行排序的數(shù)據(jù)變?yōu)橛行驍?shù)據(jù)為止.
代碼
#include <stdio.h>
void patiton(int arr[], int low, int high) { //分別定義low和high為要進(jìn)行排序的其實(shí)元素 和最后一個(gè)元素的下標(biāo), 第一次low和high的取值分別為0何n-1
int key; //定義key作為基準(zhǔn)將數(shù)組分為左右兩個(gè)部分
key = arr[low];
while(low < high) {
while(low<high && arr[high] >= key)
high--;
if(low < high)
arr[low++] = arr[high];
while(low < high && arr[low] <= key)
low++;
if(low < high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end) {
int pos;
if(start < end) {
pos = partition(arr, start, end);
quick_sort(arr, start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}
int main () {
int arr[] = {32, 12, 8, 76, 21, 17, 24, 49, 78, 3};
quick_sort(arr, 0, 9);
for(int i= 0; i < 10; i++)
printf("%d ", arr[i]);
}
運(yùn)行結(jié)果:
性能
快速排序的時(shí)間復(fù)雜度為O(NlogN, 空間復(fù)雜度為O(logN), 但最壞情況下, 時(shí)間復(fù)雜度為O(N^2), 空間復(fù)雜度為O(N); 且排序是不穩(wěn)定的, 但每次都能確定一個(gè)元素所在序列中的最終位置, 復(fù)雜度和初始序列有關(guān).
==~ end ~==