快速排序是一種不穩定排序,它的時間復雜度為O(n?lgn),最壞情況為O(n2);空間復雜度為O(n?lgn)。
這種排序方式是對于冒泡排序的一種改進,它采用分治模式,將一趟排序的數據分割成獨立的兩部分,其中一組數據的每個值都小于另一組。每一趟在進行分類的同時實現排序。
其中每一趟的模式通過設置key當基準元素,key的選擇可以是數據的第一個,也可以是數據的最后一個。這里以每次選取數據的第一個為例:
具體代碼實現:
#include<stdio.h>#define N 6 int fun(int arr[],int low,int high) { int key; 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=fun(arr,start,end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); }}int main(){ int i; int arr[N]={32,12,7,78,23,45}; for(i=0;i<N;i++) { printf("%d ",arr[i]); } printf("/n"); quick_sort(arr,0,N-1); for(i=0;i<N;i++) { printf("%d ",arr[i]); } return 0; }
由于是第一次撰寫博客,許多地方沒有一個良好的習慣,還請讀者見諒。創建這個博客的目的實際上是為了讓自己對于數據結構與算法加深印象,通過博客的形式展現出來一方面方便自己查閱,另一方面以希望能夠通過自己的微薄之力幫助到有需要的朋友。
也希望自己能夠堅持下去,認真的去做這么一件事。
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選