数据结构(9)排序

1.基本概念:

          稳定性:等待排序的队列中有两个元素,排序前和后位置顺序不变。这个性质不是评价排序算法的标准,只在描述算法性质时使用。

2.插入排序:

   2.1直接插入排序:要将元素插入有序队列,需要先寻找位置,然后队列该位置后的其他元素后移,最后插入。

void InsertSort(ElemType A[],int n){
    int i,j;
    for(i=2;i<=n;i++)
        if(A[i]<A[i-1]){
            A[0]=A[i];              //当作哨兵,A[0]没有元素
            for(j=i-1;A[0]<A[j];--j)//从后向前寻找位置
                A[j+1]=A[j];        //后移
            A[j+1]=A[0];            //插入
        }
}

   2.2折半插入排序:折半查找后统一移动,最后插入。

void InsertSort(ElemType A[],int n){
    int i,low,high,j,mid;
    for(i=2;i<=n;i++){
        A[0]=a[i];
        low=1;high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid]>a[0]) high=mid-1;
            else low=mid+1;
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];
        A[high+1]=A[0];
    }
}

   2.3希尔排序(缩小增量排序):将排序表分割为若干个子表,把相隔x的数据分配在同一个子表,然后对子表进行直接插入排序,基本有序后再进行直接插入排序。

void ShellSort(ElemType A[],int n){
	for(dk=n/2;dk>=1;dk=dk/2)		//步长变化
		for(i=dk+1;i<=n;++i)
			if(A[i]<A[i-dk){		//插入A[i]
				A[0]=A[i];		    
				for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
					A[j+dk]=A[j];	//后移
				A[j+dk]=A[0];		//插入
			}
}

3.交换排序

   3.1冒泡排序:两两比较相邻元素,逆序则交换,最终有序。

void BubbleSort(ElemType A[],int n){
	for(i=0;i<n-1;i++)
		flag=false;					//交换标志
		for(j=n-1;j>i;j--)
			if(A[j-1]>A[j){			//如果是逆序
				swap(A[j-1],a[j]);	//交换
				flag=true;			
			}
		if(flag=false)
			return;
		}
}

   3.2快速排序:在待排序列中取一个作为基准,然后通过一趟排序将序列以基准分割为两部分,前部分都小于基准,后部分都大于基准。然后在前后部分各取元素作为基准继续分割。

void QuickSort(ElemType A[],int low,int high){
	if(low<high){
		int pivotpos=Partition(A,iow,high);//分割
		QuickSort(A,low,pivotpos-1);	   //对子表进行递归
		QuickSort(A,pivotpos+1,high);
	}	
}

int Partition(ElemType A[],int n){
	ElemType pivot=A[low];	//将第一个元素作为基准
	while(low<high){
		while(low<high && A[high]>=pivot) --high;
		A[low]=A[high];		//将小元素前移
		while(low<high && A[low]<=pivot) ++low;
		A[high]=A[low];		//将大元素后移
	}
	A[low]=pivot;			//将基准放置在最终的位置
	return low;				//将基准最终的位置返回
}

 

4选择排序

   4.1简单选择排序:第x次排序就将最小的元素与第x个位置的元素交换。

void SelectSort(ElemType A[],int n){
	for(i=0;i<n-1;i++){				//进行n-1次
		min=i;						//标记最小元素的位置
		for(j=i+1;j<n;j++)			//选择最小元素
			if(A[j]<A[min]) min=j;
		if(min!=i) swap(A[i],A[min]);
	}
}

   4.2堆排序:分为大根堆(最大的元素是根,其余节点均小于双亲节点),小根堆(与大根堆相反)。

//建立大根堆
void BuildMaxHeap(ElemType A[],int len){
	for(int i=len/2;i>0;i--)	//从n/2到1,反复调整
		HeadAdjust(A,i,len);		
}		
void HeadAdjust(ElemType A[],int len,int k){
	//k是根		
	A[0]=A[k];		//A[0]暂存根节点
	for(i=2*k;i<=len;i*=2){	//选择较大节点向下选择
		if(i,len&&A[i]<A[i+1])
			i++;			//选择较大节点的下标
		if(A[0]>A[i]) break;
		else{
			A[k]=A[i];		//将A[i]调整到双亲节点
			k=i;			//修改k值,继续选择
		}
	}
	A[k]=A[0];
}		
//堆排序算法
void HeapSort(ElemType A[],int len){
	BuildMaxHeap(A,len);	//建堆
	for(i=len;i>1;i--){		//n-1趟交换
		Swap(A[i],A[1]);	//交换堆顶元素,堆底元素
		HeadAdjust(A,1,i-1) //把其他n-1个元素调整
	}
}

5.两路归并排序:为了能够使多个有序表合并为一个,将它们两两合并。

//建立辅助数组B
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int mid,int high){
	for(int k=low;k=i;k++)	
		B[k]=A[k];			//复制A的所有元素到B
	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){	
		if(B[i]<=B[j])		//比较B的左右两段元素
			A[k]=B[i++];	//较小值复制到A
		else 	A[k]=B[j++];
	}
	while(i<=mid)  A[k++]=B[i++];//如果第一个表没有检测完毕,复制
	while(j<=high) A[k++]=B[j++];//如果第二个表没有检测完毕,复制
}		
		
//两路归并排序算法
void MergeSort(ElemType A[],int low,int high){
	if(low<high){
		int mid=(low+high)/2;		//分割成为两个子序列
		MergeSort(A,low,mid);		//对左子序列进行递归排序
		MergeSort(A,mid+1,high);	//对右子序列进行递归排序
		MergeSort(A,low,mid,high);  //归并
	}
}

6.基数排序:借助关键字大小进行排序。

7.外部排序:之前的所有排序方法都进行在内存,但是对大文件进行排序时无法将所有数据放入内存,所以需要将等待数据储存到磁盘,然后分批调入。

7.1归并排序:先根据内存大小进行分割,然后调入内存使用内部排序方法排序,然后重新写回外存(此时叫做归并段),最后将这些归并段进行逐趟排序。

8.排序算法比较:

数据结构(9)排序

上一篇:线性表->顺序存储


下一篇:数据结构——栈的编程实现