#include <cstdio>
#include <cstdlib>
#include <cmath>

//Bubble
void bubbleSort(int arr[],int len)
{
	int i,j,tmp;
	for(i=0;i<len-1;i++)
	{
		for(j=0;j<len-i-1;j++)
		{
			if(arr[j+1]<arr[j])
			{
				tmp=arr[j+1];
				arr[j+1]=arr[j];
				arr[j]=tmp;
			}
			
		}
	}
	
}

//Insert
void insertSort(int arr[],int len)
{
	int i,j,key;
	for(i=1;i<len;i++)
	{
		key=arr[i];
		j=i-1;
		while(j>=0 && arr[j]>key)
		{
			arr[j+1]=arr[j];
			j--;
		}
		arr[j+1]=key;		
	}
}

//Merge
void merge(int start,int mid,int end,int arr[])
{
	int i,j,k;
	int len1=mid-start+1;
	int len2=end-mid;
	int left[len1],right[len2];
	for(k=0;k<len1;k++)
		left[k]=arr[start+k];
	for(k=0;k<len2;k++)
		right[k]=arr[mid+1+k];
	k=start;
	i=j=0;
	while(i<len1 && j<len2)
	{
		if(left[i]<right[j])
			arr[k++]=left[i++];
		else
			arr[k++]=right[j++];
	}
	
	while(i<len1)
		arr[k++]=left[i++];
	while(j<len2)
		arr[k++]=right[j++];
	
	
}

void sort(int start,int end,int arr[])
{
	int mid;
	if(start<end)
	{
		mid=(start+end)/2;
		sort(start,mid,arr);
		sort(mid+1,end,arr);
		merge(start,mid,end,arr);
	}
	
}

void mergeSort(int arr[],int len)
{
	sort(0,len-1,arr);
}

//Quick
int partition(int start, int end, int arr[])
{
	//从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
	int pivot=arr[start];
	int l=start,r=end;
	
	while(l<r)
	{
		while(l<r && arr[r]>=pivot)
			r--;
		if(l<r)
		{
			arr[l]=arr[r];
			l++;
		}
		
		while(l<r && arr[l]<pivot)
			l++;
		if(l<r)
		{
			arr[r]=arr[l];
			r--;
		}
		
	}
	arr[l]=pivot;
	return l;
}

void quickSort(int start, int end, int arr[])
{
	int mid;
	if (end > start) {
		mid = partition(start, end ,arr);
		quickSort(start, mid-1, arr);
		quickSort(mid+1, end, arr);
	}
}


//Shell
void shellPass(int arr[],int len,int gap)
{
	int i,j,key;
	//步长不总为1的插入排序
	for ( i = gap; i < len; i++ )
        {
		j = i - gap;
		key = arr[i];             
		while (( j >= 0 ) && ( arr[j] > key ))
		{
			arr[j + gap] = arr[j];
			j = j - gap;			//在已排序序列中寻找合适位置插入key
		}
		arr[j + gap] = key;
        }
}

void shellSort(int arr[],int len)
{
	int gap=0;
	while(gap<=len)
		gap=gap*3+1;	//确保最终步长为1
	while(gap>0)
	{
		shellPass(arr,len,gap);
		gap=(gap-1)/3;
	}
}

//Heap
/*父結點*/
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}
 
/*左子結點*/
int left(int i)
{
    return (2 * i + 1);
}
 
/*右子結點*/
int right(int i)
{
    return (2 * i + 2);
}
 
/*單一子結點最大堆積樹調整*/
void Max_Heapify(int A[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int largest;
    int temp;
    if(l < heap_size && A[l] > A[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if(r < heap_size && A[r] > A[largest])
    {
        largest = r;
    }
    if(largest != i)
    {
        temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        Max_Heapify(A, largest, heap_size);
    }
}
 
/*建立最大堆積樹*/
void Build_Max_Heap(int A[],int heap_size)
{
    for(int i = (heap_size-2)/2; i >= 0; i--)
    {
        Max_Heapify(A, i, heap_size);
    }
}
 
/*印出樹狀結構*
void print(int A[], int heap_size)
{
    for(int i = 0; i < heap_size;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}*/
 
/*堆積排序程序碼*/
void HeapSort(int A[], int heap_size)
{
    Build_Max_Heap(A, heap_size);
    int temp;
    for(int i = heap_size - 1; i >= 0; i--)
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        Max_Heapify(A, 0, i);
    }
    //print(A, heap_size);
}