＞第 11 章 排序与查找＞归并排序＞习题

int left[n1], right[n2];
由于n1,n2是不确定值
所以运行后将出现错误

#include <stdio.h>
int partition(int start, int end, int a[])
{
	int j = start, i, temp;
	for (i = start + 1; i <= end; i++)
		if (a[i] <= a[j]) {
			temp = a[i];
			a[i] = a[j + 1];
			a[j + 1] = temp;
			temp = a[j + 1];
			a[j + 1] = a[j];
			a[j] = temp;
			j++;
		}
	return j;
}

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

void main()
{
	int i,n;
	int list[100];
	printf("num,must be <100:\n");
	scanf("%d", &n);
	printf("oringal list:");
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;
		printf("%d  ", list[i]);
	}
	printf("\n");

	quitsort(0, n, list);
	printf("actally:");
	    for (i = 0; i < n; i++)
		printf("%d ", list[i]);
}

数组不能用变量申明大小，数组的大小必须在编译的时候就确定下来，不然会出现编译错误

1L和3L很好很强大。

在一个循环中移动a[start..end]的数据，将a[start..end]分成两半，
----------
这一节习题以及下一节习题都说分成两半，写为两部分应该好理解一些。“半”给人1/2的感觉。

你说得有一定道理，谢谢

看不懂算法怎么实现的啊。。。

主要是调用中的变量和顺序问题。。。。

我再倒回去看看递归吧 -__-

我的归并算法，这样写行不？
结果来看，好像是对的。

void merge_sort_merge(int start, int end) {
	printf("merge: [%d - %d]\n", start,  end);
	int mid = (start + end) / 2;
	int i,j,k;
	for (j = mid + 1; j <= end; j++){
		k = a[j];
		for (i = j-1; i >= 0; i--){
			if (a[i] > k)
				a[i+1] = a[i];
			else
				break;
		}
		a[i+1] = k;
	}
}

void merge_sort_sort(int start, int end){
	if ( start < end) {
		int mid = (start + end) / 2;
		printf("start: [%d - %d]\n", start, mid , end);
		merge_sort_sort(start, mid);
		merge_sort_sort(mid+1,end);
		merge_sort_merge(start, end);
	}
}



void merge_sort(void)
{
	merge_sort_sort(0, LEN - 1);
}

看起来，有点像归并和插入的结合体。。。
汗- -!

偶的快速排序答案：

#include<stdio.h>
#define N 8

int a[N] = { 3,6,1,2,4,11,67,23};
int t[N];

int partition(int start, int end)
{
/*	从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
	在一个循环中移动a[start..end]的数据，将a[start..end]分成两部分，
	使a[start..mid-1]比pivot元素小，a[mid+1..end]比pivot元素大，而a[mid]就是pivot元素;*/

	int pivot = (start + end) / 2;
	int len = end - start;
	int i,j,k,temp,mid;
	int left[len],right[len];

	j = k = -1;
	temp = a[pivot];

	for(i = start; i <= end; i++) {
		if(i != pivot){
			if(a[i] < temp){
				left[++j] = a[i];
			}else{
				right[++k] = a[i];
			}
		}			
	}

	i = start;
	if(j > -1){
		int num = 0;
		for(i = start; i<= start + j; i++){
			a[i] = left[num++];
		}
	}
	mid = i;
	a[i] = temp;
	if(k > -1){
		int num = 0;
		for(i = mid + 1; i<= mid + 1 + k; i++){
			a[i] = right[num++];
		}
	}
	
	return mid;
}

void quicksort(int start, int end)
{
	int mid;
	if (end > start) {
		mid = partition(start, end);
		quicksort(start, mid-1);
		quicksort(mid+1, end);
	}
}

int main(void)
{
	quicksort(0, N-1);
	printf("%d, %d, %d, %d, %d, %d, %d, %d \n",
			a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
	return 0;
}

偶的快速排序答案二：

#include<stdio.h>
#define N 8

int a[N] = { 3,6,1,2,4,11,67,23};
int t[N];

int partition(int start, int end)
{
/*	从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
	在一个循环中移动a[start..end]的数据，将a[start..end]分成两部分，
	使a[start..mid-1]比pivot元素小，a[mid+1..end]比pivot元素大，而a[mid]就是pivot元素;*/

	int pivot = start,i,temp;

	for(i = start+1; i <= end; i++) {
		if(a[i] < a[pivot]){
			temp = a[i];
			a[i] = a[pivot+1];
			a[pivot+1]=a[pivot];
			a[pivot] = temp;
			pivot++;
		}
	}
	return pivot;
}

void quicksort(int start, int end)
{
	int mid;
	if (end > start) {
		mid = partition(start, end);
		quicksort(start, mid-1);
		quicksort(mid+1, end);
	}
}

int main(void)
{
	quicksort(0, N-1);
	printf("%d, %d, %d, %d, %d, %d, %d, %d \n",
			a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
	return 0;
}

#include<stdio.h>

#define LEN 8
/*编辑器用的是emacs所以格式有点不太好看，呵呵，希望有心人改正*/
int a[LEN]={6,7,3,5,9,2,4,8,0};

int partition(int start,int end)
{
  int x=a[start],i,b[end-start+1],count=0,mid=-1;
  for(i=0;i<=end;i++)
    b[i]=a[i];
  for(i=0;i<=end;i++)
    {
        if(x>b[i])
	{	
	  a[count++]=b[i];
	}
    }
  mid=count;
  a[mid]=x;
  for(i=0;i<=end;i++)
    {
      if(x<b[i])
	a[++count]=b[i];
    }
  return mid;
}

void quicksort(int start,int end)
{
  int mid;
  if(end>start)
    {
      mid=partition(start,end);
      quicksort(start,mid-1);
      quicksort(mid+1,end);
    }
}

int main()
{
  int i;
  quicksort(0,8);
  for(i=0;i<=8;i++)
  printf("%d  ",a[i]);
  printf("\n");
}

如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！