webdancer's Blog

排序算法

       我的算法可以说应该是很烂,归结起来:(1)不善总结,无法融汇贯通,与性格有关。(2)经常忘记,无法应用的好,与智商有关。我觉得:智商不高,还可以在计算机世界里混,但是若是性格不好,不能坚持,我觉得难有成绩。现在,该录正题了。       

      排序到底有什么用呢?对于我来说,我以前没有认真思考过这个问题,在Tao里,作者总结了一下,这里记录一下:

(1)解决“一起性”问题,把具有相同标志的项目连在一起。其实,sort在英文中就有 分类 的意思。把相同的东西归到一起,排序实在是好呀!

(2)匹配在两个文件或更多的文件中的项。 排好序就可以顺序的扫描,而不用跳来跳去。

(3)通过键码查询信息。很多的检索算法用得到排序,向我们熟悉的二分查找,不就是对已经排好序的序列。

     排序分为:内部排序和外部排序。所有的数据都可以放入主存中时,采用内部排序;当不能完全的放入主区,则只能采用外部排序。我还是先学习一下内部排序。

(1)直接插入排序。这种排序思想简单,就是在已经排好序的序列中,插入元素。

/*直接插入*/
void chsort(int a[],int n){
	int j,k;
	for(j=1;j<n;j++){
		k=a[j];
		int i=j-1;
		while(a[i]>k){
			a[i+1]=a[i];
			i--;
		}
		a[i+1]=k;
	}
}

(2)通过交换排序。

冒泡排序:

/*冒泡排序*/
void bsort(int a[],int n){
     int isch=1 , i,j;
     for(i=n-1;i>0&&isch;i--){
	     isch=0;
	     for(j=0;j<=i;j++){
		     if(a[j]>a[j+1]){
			     int t;
			     t=a[j];
			     a[j]=a[j+1];
			     a[j+1]=t;
			     isch=1;
		     }
	     }
     }
}

快速排序:

/*快速排序的划分方式,a[r] 有最大的值。*/
void sortone(int a[],int l,int r){
	if(l>=r) return;
	int i=l+1,j=r;
	int base=a[l];
	while(i<j){
	while(a[i]<base)
		i++;
	while(a[j]>base)
		j--;
	if(i<j){
	int t=a[i];
	a[i]=a[j];
	a[j]=t;
	}
	}
 	a[l]=a[j];
	a[j]=base;
	/*递归的调用sortone*/
	sortone(a,l,j-1);//  First, the wrong is: sortone(a,l,j).
	sortone(a,j+1,r);
}
/*为了排序的接口统一*/
void qusort(int a[],int n){
	sortone(a,0,n-1);
}

快速排序分析:

//使用快排对a[0...n-1]进行排序。

从a[0...n-1]中选择支点,把剩下的分为两段:left ,right;左边的都小于支点,右边的都大于支点。然后,递归的来对left,right进行排序,最后的结果为:left ,支点,right。

如何选择支点进行划分left,right会严重的影响快排的效率,我选择了教科书上的给出支点a[0]。但是,不是很好呀! 快排对已经有序的序列进行排序,时间复杂度会上升的O(n2),偏爱无序的序列。

不知道C函数库中的:

 

void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

如何实现的。

(3)选择排序。

 

/*直接选择排序*/
void xzsort(int a[],int n){
	int j;
	for(j=n-1;j>0;j--){
		int maxIndex=0,i;
		for(i=1;i<=j;i++)
			if(a[i]>a[maxIndex])
				maxIndex=i;
		int t;
		t=a[maxIndex];
		a[maxIndex]=a[j];
		a[j]=t;
	}
}

利用MAXHEAP来实现选择排序应该是一种很好的方法。MaxHeap数据结构的构建还是比较复杂的,涉及到构建堆,插入,删除MAX等。感觉在构建复杂的数据类型时,c++/java等引入了类的语言还是简单呀!




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee