#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include<malloc.h>
void swap(int *a,int *b);
void select_sort(int arr[],int n);
void tra_arr(int arr[],int n);
void insert_sort(int arr[],int n); 
void shell_sort(int arr[],int n);
void perc_down(int arr[],int i,int n);
void heap_sort(int arr[],int n);
void merge(int arr[],int temp_arr[],int left_start,int right_start
			,int right_end);
void m_sort(int arr[],int temp_arr[],int left,int right);
void merge_sort(int arr[],int n);
int get_pri(int arr[],int left,int right);
void q_sort(int arr[],int left,int right);
void quick_sort(int arr[],int n);
int main(){
	int arr[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	select_sort(arr,10);
	printf("\n簡單選擇排序結果\n");
	tra_arr(arr,10);
	
	int arr1[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	insert_sort(arr1,10);
	printf("\n插入排序結果\n");
	tra_arr(arr1,10);
	
	int arr2[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	shell_sort(arr2,10);
	printf("\n希爾排序結果\n");
	tra_arr(arr2,10);
	
	int arr3[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	heap_sort(arr3,10);
	printf("\n堆排序結果\n");
	tra_arr(arr3,10);
	
	int arr4[100]={
		 10,9,8,7,6,5,4,3,2,1
	};
	merge_sort(arr4,10);
	printf("\n歸并排序結果\n");
	tra_arr(arr4,10);
	
	int arr5[100]={
		 10,9,8,7,6,5,4,3,2,1
	};
	quick_sort(arr5,10);
	printf("\n快速排序結果\n");
	tra_arr(arr5,10);
	
	return 0;
}
void swap(int *a,int *b){
	//在函數(shù)內部，如果打算接收的是指針的地址，那就不要加*,
	//如果想要的是值，那就加*,我也很討厭指針，但是沒辦法 
	int t=*a;
	*a=*b;
	*b=t;
}
//簡單選擇排序 
void select_sort(int arr[],int n){
	int min;
	//這個過程一時半會講不清楚，看書會清楚一些 
	for(int i=0;i<n;i++){
		min=i;
		
		for(int j=i+1;j<n;j++){
			if(arr[i]>arr[j]){
				min=j;
			}
		} 
		//經(jīng)過上面的里層for，就找到了最小的元素的下表
		swap(&arr[i],&arr[min]) ;
	} 
}
//插入排序
void insert_sort(int arr[],int n){
	int temp,j;
	for(int i=1;i<n;i++){
		temp=arr[i];
		for(j=i;j>0&&arr[j-1]>temp;j--){
			//后挪
			arr[j]=arr[j-1];
		}
		//現(xiàn)在就找到空出來的插入位置了
		arr[j]=temp; 
	}
} 
//希爾排序
void shell_sort(int arr[],int n){
	int in,i,j,temp;
	//本來這個排序是很好理解的，就是這個外層的循環(huán)
	//故弄玄虛，你就把他理解成一個簡單的，遞減的數(shù)組就行
	//而且這個2的指數(shù)遞減的序列的時間復雜度是很壞的 
	//最好使用SED或者HIB序列會好很多,這里只是演示 
	//兩個里層的for就是插入排序,仔細看看就能看懂 
	
	for(in=n/2;in>0;in=in/2){
		for(i=in;i<n;i++){
			temp=arr[i];
			for(j=i;j>=in;j=j-in){
				if(arr[j-in]>temp){
					//后挪 
					arr[j]=arr[j-in];
				}
				else{
					//arr[j-in]<temp，說明找到了 
					break;
				}
			}
			//上面執(zhí)行完，肯定找到了插入位置
			arr[j]=temp; 
		}
	} 
} 
//首先是下濾操作
//i是根，n是heap的規(guī)模 
//這里的下濾針對最大堆 
void perc_down(int arr[],int i,int n){
	int child,temp;
	//仔細想想，其實和插入排序差不多
	//首先把i取出來，把i在堆里面所在的位置空出來 
	//這里和原來建堆的下濾又不一樣，這里沒有設置哨兵 
	for(temp=arr[i];(2*i+1)<n;i=child){
		child=2*i+1;
		//如果當前兒子不是最后一個，說明還有右兒子
		//兩者取最大 
		if(child!=(n-1)&&arr[child]<arr[child+1]){
			child++;
		}
		if(temp<arr[child]){
			arr[i]=arr[child];
		}
		else{
			//當前取出來的值終于大于兩個兒子時。 
			break;
		}
		
	} 
	//上面輪完之后，肯定找到了一個兒子比我們取出來的值還要小的
	arr[i]=temp; 
} 
void heap_sort(int arr[],int n){
	int i;
	//建堆
	for(i=n/2;i>=0;i--){
		perc_down(arr,i,n);
	}
	//取最大值放在最后已經(jīng)舍棄的位置上，下濾剩下的堆
	for(i=n-1;i>0;i--){
		//取最大值放在最后已經(jīng)舍棄的位置上
		swap(&arr[0],&arr[i]);
		// 濾剩下的堆
		perc_down(arr,0,i);
	}
}
//歸并排序
//第一步，寫一個將兩個已經(jīng)排好序列的歸并
void merge(int arr[],int temp_arr[],int left_start,int right_start
			,int right_end)
{
	int i,temp_start,elem_num,left_end;
	temp_start=left_start;
	left_end=right_start-1;
	elem_num=right_end-left_start+1;
	//歸并的核心
	while(left_start<=left_end&&right_start<=right_end){
		if(arr[left_start]<=arr[right_start]){
			temp_arr[temp_start++]=arr[left_start++];
		}
		else{
			temp_arr[temp_start++]=arr[right_start++];
		}
	}	
	while(left_start<=left_end){
		temp_arr[temp_start++]=arr[left_start++];
	}		
	while(right_start<=right_end){
		temp_arr[temp_start++]=arr[right_start++];
	}
	//重新拷回去，記住，這里歸并的只是原來數(shù)組的一部分，所以不能從頭開始
	for(i=0;i<elem_num;i++,right_end--) {
		arr[right_end]=temp_arr[right_end];
	}
} 
//第二步，遞歸調用歸并，將數(shù)組不斷分割
void m_sort(int arr[],int temp_arr[],int left,int right){
	//tra_arr(arr,10);
	int center;
	//遞歸結束條件
	if(left<right){
		center=(right+left)/2;
		m_sort(arr,temp_arr,left,center);
		m_sort(arr,temp_arr,center+1,right);
		merge(arr,temp_arr,left,center+1,right);
	} 
} 
//第三步，初始化臨時數(shù)組
void merge_sort(int arr[],int n){
	int *temp_arr;
	temp_arr=(int*)malloc(n*sizeof(int));
	m_sort(arr,temp_arr,0,n-1);
	free(temp_arr);
} 

//快速排序
//首先，實現(xiàn)三數(shù)中值分割法,取一個“裁判” （中值） 
int get_pri(int arr[],int left,int right){
	int center=(left+right)/2;
	if(arr[left]>arr[center]){
		swap(&arr[left],&arr[center]);
	}
	if(arr[left]>arr[right]){
		swap(&arr[left],&arr[right]);
	}
	if(arr[center]>arr[right]){
		swap(&arr[center],&arr[right]);
	}
	//把中值扔到倒數(shù)第二個，因為上述操作已經(jīng)讓倒數(shù)第一大于中值了 
		swap(&arr[center],&arr[right-1]);
		
	return arr[right-1];
	
} 
//其次，實現(xiàn)分而治之
void q_sort(int arr[],int left,int right){
	int i,j,pri;
	//如果規(guī)模已經(jīng)小于三了，就不要再分而治之了，沒得分了 
	if(right-left>=3){
		//取中值
		pri= get_pri(arr,left,right);
		//取左右往中間靠攏的兩個指針i,j
		i=left;
		j=right-1;
		//開始判斷
		while(1){
			//如果當前i對應的值小于裁判，繼續(xù)推進 
			while(arr[++i]<pri);
			// 如果當前i對應的值大于裁判，繼續(xù)推進
			while(arr[--j]>pri);
			//上面走完，肯定碰到硬杈了，在i和j沒有錯位的情況下
			//交換
			if(i<j){
				swap(&arr[i],&arr[j]);
			} 
			else{
				break;
			}
		} 
		swap(&arr[i],&arr[right-1]);
		//這個i的作用遠不止此,這個i還記錄了上一個裁判的位置
		//開始對分下來的兩個部分進行同樣的操作
		q_sort(arr,left,i-1);
		q_sort(arr,i+1,right); 
	}
	//如果遞歸到規(guī)模已經(jīng)無法再分了
	//就用普通的方法排序
	else{
		/*這里稍微講一下
		數(shù)組和指針實際上是一樣的東西
		到這里了，那肯定就剩一個或者兩個元素了
		所以數(shù)組的開頭變成left所指的位置，現(xiàn)在left所在位置的下標
		就是0，所以后面的n也要相應變化*/ 
		insert_sort(arr+left,right-left+1);
	}
	
} 
//最后包裝一下
void quick_sort(int arr[],int n){
	q_sort(arr,0,n-1);
} 
//遍歷數(shù)組
void tra_arr(int arr[],int n){
	for(int i=0;i<n;i++){
		printf("%d  ",arr[i]);
	}
	printf("\n");
}