排序算法入門——快速排序

涵義

·        雖說快速排序是由冒泡排序改進而來，二者都是通過元素交換達到排序效果，但是在個人看來快速排序思想和冒泡完全不同。

時間複雜度

·        直接插入排序最好的時間複雜度為O(nlog2n)

·        直接插入排序的最壞時間複雜度為O(n2)

·        是以直接插入排序總的平均時間複雜度為O(nlog2n)

注：不穩定

排序原理

快速排序之是以比冒泡具有更高的效率，主要是它裡面用到的分治思想，如上圖所示，第一遍遞歸完成，比23小的與比23大的分到兩邊，再次遞歸則是對15-21進行一次與上圖相同的排序，31-44也是如此。

下面測試執行個體中，times中完成的就是上圖做的工作，每次排序完成在fastsort()中拿到index,即圖中23，然後對left到index-1，和index+1到right,分别遞歸（此處的low,high,我用的是left,right），而一開始用于比較的數稱為基準，一般取最左側或最右側值。

c++

#include<iostream>
#include<string>
using namespace std;
int times(int a[],int left,int right){
	int temp=a[left],tt;//聲明temp為基準，即用于做比較的數字
	while(left<right){//隻要左右兩邊向中間周遊沒有碰頭，就一直進行
		while(left<right&&a[right]>=temp){//先從右邊開始，因為基準是左邊
			right--;
		}
		tt=a[left];
		a[left]=a[right];
		a[right]=tt;
		while(left<right&&a[left]<=temp){
			left++;
		}
		tt=a[left];
		a[left]=a[right];
		a[right]=tt;
	}
	return left;//此時left=right,傳回值做下次周遊的切分處
}
void fastsort(int a[],int left,int right){
	if(left<right){
		int index=times(a,left,right);
		fastsort(a,left,index-1);//對index左邊和右邊分别遞歸調用，開始局部排序
		fastsort(a,index+1,right);
	}
}
void print(int a[],int n){
	for(int i=0;i<10;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
int main(){
	int a[10]={7,5,1,6,3,2,9,8,4,11};
	fastsort(a,0,9);//快速排序
	print(a,9);//列印結果
	return 0;
}


           

運作截圖