数据结构之常见的排序算法2

继续快速排序，简单选择排序和堆排序

一，快速排序

算法思想

a,先从一个数列中取出一个数作为基数

b,分区过程，将比这个数大的放在右边，小于等于这个数的放到左边

c,再对左右区间重复第二步，直到各个区间只剩一个数

2，代码

void QuickSort(int[]s,int l,int r){//l,r是指快排的范围，从s[l]到s[r]
		int i=l;
		int j=r;
		int temp;
		if(l<r){
			temp=s[l];
			while(i!=j){
				while(j>i&&s[j]>temp){//从右向左找小于temp的数
					j--;
				}
				if(i<j){
					s[i]=s[j];
					i++;
				}
				while(i<j&&s[i]<temp){//从左向右找大于temp的数
					i++;
				}
				if(i<j){
					s[j]=s[i];
					j--;
				}
			}
			s[i]=temp;
			QuickSort(s, l, i-1);
			QuickSort(s, i+1, r);
		}
	}

二，简单选择排序

1，算法思想

选择类排序的主要动作是“选择”，简单选择排序采用最简单的选择方式，从头至尾顺序扫描排列，找出最小的一个记录，和第一个记录交换，

接着从剩下的记录中继续这种选择和交换，最终使序列有序。

void SelectSort(int r[],int n){
		int i,j,k;
		int temp;
		for(i=1;i<=n;i++){
			k=i;
			//算法关键处，从无需序列中挑出一个最小的元素
			for(j=i+1;j<=n;j++){
				if(r[k]>r[j]){
					k=j;
				}
				temp=r[i];
				r[i]=r[k];
				r[k]=temp;
			}
		}
	}

三，堆排序

warning：学堆排序之前，应该了解堆的相关知识;)

算法思想还是上杰宝吧...

代码如下咯：

/*调整为最小堆*/
	void Sift(int R[],int low,int high){
		int i=low,j=2*i;//R[j]是R[i]的左孩子节点
		int temp=R[i];
		while(j<=high){
			if(j<high&&R[j]<R[j+1]){
				j++;
			}
			if(temp<R[j]){
				R[i]=R[j];
				i=j;
				j=2*i;
			}else{
				break;
			}
		}
		R[i]=temp;
	}
	/*堆排序函数*/
	void heapSort(int R[],int n){
		int i;
		int temp;
		for(i=n/2;i>=1;--i){
			Sift(R,i,n);
			for(i=n;i>=2;--i){
				/*以下3句换出了根节点中元素将其放入最终位置*/
				temp=R[1];
				R[1]=R[i];
				R[i]=temp;
				Sift(R,1,i-1);//在减少了一个无需序列中进行调整
			}
		}
	}

数据结构之常见的排序算法2

相关推荐