『プログラミング珠玉』第11章ソート

久しぶりにブログを书いて、最近とても忙しくて、忙しくて交际することができなくて、しかしよく考えてみると、またすべてでたらめで忙しくて、ぼんやりしていて、自分がいったい何を忙しくしているのか分からないで、またいったいどんな収获があります.自問自答して、自分は多くの時間を浪費した.いずれにしても、自分がしっかり把握しなければならない.志のある者は常に自分の行為を制約しなければならない.私はこのように自分を厳しく要求しなければならない.他人がどう見ても、自分がどんなに苦しくても、堅持しなければならない.もちろん、ブログを書くのも同じで、毎日知識を勉強して、総括をして、同じように後の計画をします.
さて、くだらないことは言わないで、今日は久しぶりに見た「プログラミング珠玉」を見て、11章で、ソートについて、よく知っているものです.下は私が書いたいくつかのソートに関するプログラムを貼って、算術の自分の小さな総括です.

void Initialization(int *c)
{
	//produce a sequence unsorted
    for(int i = 0;i < N;i ++)
		c[i] = rand()%N;
  
}
void Display(int *c)
{
	//display the current sequence
	for(int i = 0;i < N;i ++)
		cout<<c[i]<<" ";
	cout<<endl;
}
/*Select Sort*/
void SelectSort(int *c,int n)
{
	/*find the smaller to the left half in the current right half*/
	int tmp;
	for(int i=0;i < n-1;i ++)
		for(int j=i+1;j < n;j ++)
			if (c[j] < c[i])
			{
				//put the smaller one to left
				tmp = c[i];
				c[i] = c[j];
				c[j] = tmp;
			}
}
/*Insert Sort*/
void InsertSort(int *c,int n)
{
	//n numbers
	int i,j,tmp;
	for(i = 1;i < n;++ i)
	{
		//sort the c[i]
        tmp = c[i];
		for(j = i;j > 0&&c[j-1] > tmp;-- j)
			//move the bigger ones right
			c[j] = c[j-1];
		c[j] = tmp;
	}
}
void QuickSort(int * c,int l,int u)
{
	//quick sort---Version 1
	if (l >= u) return;
	int m = l;
	int tmp;
	for (int i = l+1;i <= u;i ++)
		if (c[i] < c[l])
		{
			//swap c[++m] c[i]
            tmp = c[++m];
			c[m] = c[i];
			c[i] = tmp;
		}
	Display(c);
	/*put c[l] in the middle*/
	tmp = c[l];
	c[l] = c[m];
	c[m] = tmp;
    /*quick sort the left and right ones*/
	QuickSort(c,l,m-1);
	QuickSort(c,m+1,u);
}
void _QuickSort(int *c,int l,int u)
{
	//improve the above algorithm while all the elements are the same
	if (l >= u) return;
	int t,i,j,tmp;
	t = c[l];
	i = l+1;
	j = u;
	while (true)
	{
		while(i < u && c[i] <= t) ++ i; cout<<i<<endl;
		while (c[j] > t) -- j; cout<<j<<endl;
		if (i >= j) break;
		/*swap the small and big ones*/
        tmp = c[i];
		c[i] = c[j];
		c[j] = tmp;
		Display(c);
	}
	/*put c[l] in the middle*/
	tmp = c[j];
	c[j] = c[l];
	c[l] = tmp;
	/*sort the left and right ones*/
	Display(c);
	_QuickSort(c,l,j-1);
	_QuickSort(c,j+1,u);
}

int get_k_smaller(int *c,int l,int u,int k)
{
	//get the k smallest number
    //if(l >= u) return;
	int t = c[l];
	int i,j,tmp;
	i = l+1;j=u;
	while(true)
	{
		//cut it to two pieces
		while(i < u&&c[i] <= t) ++ i;
		while(c[j] > t) -- j;
		if (i >= j) break;/*swap all the datas*/
		//swap the smaller one and the bigger one
        tmp = c[i];
		c[i] = c[j];
		c[j] = tmp;
	}
	/*put the c[l] int the middle*/
	tmp = c[l];
	c[l] = c[j];
	c[j] = tmp;
	/*from c[l+1] to c[j] is smaller than t*/
	if (j-l+1 == k)                          /*the same numbers which is k*/
		return c[j];
	else if (j-l+1 > k)                      /*the numbers that small than c[l] is more than k*/
		 get_k_smaller(c,l,j-1,k);           /*find the k_smaller in the smaller piece*/
	else get_k_smaller(c,j+1,u,k-j+l-1);     /*find the last number without the before (j-l+1)s in the smaller one*/
}

/*Shell Sort*/
void ShellSort(int *c,int n)
{
	//
	int h,tmp;
	for(h = 0; h < n;h = 3*h + 1)
		;
	while (1)
	{
        h /= 3;
		cout<<"h:"<<h<<endl;
		if (h < 1) break;
		for (int i = h;i < n;++ i)
			for(int j = i;j >= h;j -= h)
			{
				if (c[j-h] < c[j]) break;
				//swap
                tmp = c[j-h];
				c[j-h] = c[j];
				c[j] = tmp;
				cout<<i<<" "<<j<<endl;
				Display(c);
			}
	}
}