挑戰二--第七章高等排序（二）

7.2分割

具體來說，分割并不算排序，具體功能就是将一個數組分成兩部分，前半部分均小于 數組中其中一個值，後半部分均大于這個值，（但是這兩部分并不是有序的） 函數傳回值傳回這個值的下标。

具體實作操作：

定義一個變量i記錄比規定值（以下稱這個規定分割值為 a[r]) 小或者大的分界下标。

定義一個變量從頭向後周遊，決定每一個元素是屬于那個部分：

    如果大于a[r]則不必移動元素，隻需将該變量向後移，将該元素納入“大于組”

    如果小于a[r]組先讓i變量向後移動一個位置，然後交換上一個元素，這樣該元素則進入“小于組”，而前一個元素還在“大于組”。

最後将最規定值與找到的分界下标所對應的值交換 傳回分界下标。

算法複雜度：O(n) 

分割也會交換不相鄰的元素 是以具體排序用到分割時，這種排序（下一章的快速排序....）将不穩定。

代碼實作

int partition(int a[],int p,int r){
	int x=a[r];
	int i=p-1;
	for(int j=p;j<r;j++){
		if(a[j]<=x){
			i++;
			swap(a[i],a[j]);
		}
	
	}
	swap(a[i+1],a[r]);
	 
	return i+1;
}
           

我我我。。。這個語言表達能力 。。。。文字表達能力 。。。确實。。。需要加強。。。哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。。。。