【排序结构2】交换排序

1、起泡排序  O(N^2)

 

起泡排序的过程很简单，首先将第一个关键字和第二个关键字比较，若为逆序，则将两个记录交换。然后再用第二个关键字和第三个关键字比较，以此类推，知道第n-1个关键字和第n个比较完，这样最大的关键字将被交换到第n个位置上。这个过程称做第一趟气泡排序。然后对前n-1进行第二趟气泡排序，将第二大的关键字交换到第n-1个位置上。当第n-1趟气泡排序完成之后，有序序列也就随之产生了。

#include<iostream.h>
/**************************
 * 起泡排序 Bubble Sort   * 
 **************************/  
class BubbleSort{
public:
	static void inc_sort(int keys[],int size);
};

void BubbleSort :: inc_sort(int keys[], int size){
	for(int i=size-1;i>=0;i--)
		for(int j=0;j<i;j++){
			if(keys[j]>keys[j+1]){
				int temp=keys[j];
				keys[j]=keys[j+1];
				keys[j+1]=temp;
			}
		}
	for(int k=0;k<size;k++)
		cout<<keys[k]<<" ";
	cout<<endl;
}
//Test BubbleSort
void main(){
	int raw[]={49,38,65,97,76,13,27,49};  
	int size=sizeof(raw)/sizeof(int);  
	BubbleSort::inc_sort(raw,size);  
}

显然，气泡排序的时间复杂度为O(N^2)，其空间复杂度为O(1) ，而且是稳定的 。

 

2、快速排序 O(N*logN)

 

快速排序是对起泡排序的一种改进。它的基本思想就是：通过一趟排序将待排记录分割成独立的两个部分，其中一个部分的关键字都比另一个部分关键字小，然后可以分别再对这两个部分继续快排，已达到整个序列有序。

 

具体的做法是：对待排序列keys[n]确定两个指针(low=0，high=n-1)。然后取第一个关键字keys[0]作为pivotkey(枢轴)。首先从high所指的位置起向前搜索找到第一个关键字小于pivotkey的记录，并将这个记录的关键字与pivotkey交换。然后从low所指的位置向后搜索，找到第一个关键字大于pivotkey的记录，并交换。轮流重复这两个步骤直到low=high位置。这样一个过程我们叫做一次快排(又叫一次划分)。

 

对划分后的序列的两个部分继续分别快排，知道所有序列有序位置，整个过程就是快排。

#include<iostream.h>

class QuickSort{
private:
	//一次快排(划分)
	static int partition(int parts[],int low, int high);
	//快排
	static void quick_sort(int parts[],int low, int high);
public:
	//递增排序
	static void inc_sort(int keys[],int size);
};

int QuickSort :: partition(int parts[], int low, int high){	
	int pivotkey=parts[low];	//将第一个元素作为枢轴
	while(low<high){
		while(low<high && parts[high]>=pivotkey) --high; //将比枢轴小的关键字记录移动到低端
		parts[low]=parts[high];
		while(low<high && parts[low]<=pivotkey) ++low; //将比枢轴大的关键字记录移动到高端
		parts[high]=parts[low];
	}
	parts[low]=pivotkey;
	return low; //返回枢轴的位置
}

void QuickSort :: quick_sort(int parts[],int low,int high){
	if(low<high){
		int pivotloc=QuickSort::partition(parts,low,high);
		QuickSort::quick_sort(parts,low,pivotloc-1);
		QuickSort::quick_sort(parts,pivotloc+1,high);
	}
}

void QuickSort :: inc_sort(int keys[],int size){
	QuickSort::quick_sort(keys,0,size-1);
	
	for(int k=0;k<size;k++)
		cout<<keys[k]<<" ";
	cout<<endl;
}

void main(){
	int raw[]={49,38,65,97,76,13,27,49};    
	int size=sizeof(raw)/sizeof(int);    
	QuickSort::inc_sort(raw,size);    
}

 

//快速排序非递归算法
#include<iostream.h>
#include<malloc.h>

void quick_sort(int *pArr, int size){
	int * beginIdxs=(int *)malloc(size * sizeof(int)); //记录待调整子序列的首地址
	int * endIdxs=(int *)malloc(size * sizeof(int));//记录待调整子序列的尾地址
	beginIdxs[0]=0;
	endIdxs[0]=size-1;
	int curIdx=0;
	while(curIdx>-1){
		int low=beginIdxs[curIdx];
		int high=endIdxs[curIdx];
		int pivotkey=pArr[low]; //将第一个元素作为枢轴  
		while(low<high){
			while(low<high && pivotkey<=pArr[high]) --high;
			pArr[low]=pArr[high];
			while(low<high && pivotkey>=pArr[low]) ++low;
			pArr[high]=pArr[low];
		}
		pArr[low]=pivotkey;
		int pivotidx=low;
		int begin=beginIdxs[curIdx];
		int end=endIdxs[curIdx];
		curIdx--;
		if(begin<pivotidx-1){
			beginIdxs[++curIdx]=begin;
			endIdxs[curIdx]=pivotidx-1;
		}
		if(end>pivotidx+1){
			beginIdxs[++curIdx]=pivotidx+1;
			endIdxs[curIdx]=end;
		}
	}
	
	//打印结果
	for(int k=0;k<size;k++){
		cout<<pArr[k]<<" ";
	}
}
void main(){
	int raw[]={49,38,65,97,76,13,27,49};      
	int size=sizeof(raw)/sizeof(int);      
	quick_sort(raw,size);      
}

 

快速排序的平均时间复杂度为O(N*logN) 。但快速排序在待排关键字序列有序或基本有序的情况下， 快速排序将蜕化成起泡排序，其 时间复杂度降为O(N^2) 。 经验证明，在所有O(N*logN)级的此类排序算法中，快速排序是目前被认为最好的一种内部排序方法。但是快排需要一个栈空间来实现递归。若每一趟划分都能够均匀的分割成长度相接近的两个子序列，则栈的最大深度为[logN]+1。因此空间复杂度为O(logN)。快排也是不稳定的。

 

快速排序有一个最坏的可能性，因此也就有很多优化来改进这个算法。

 

随机化快排： 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取 第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较 常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情 况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。 实际上，随机化快速排序得到理论最坏情况的可能性仅为 1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可 以满足一个人一辈子的人品需求。 ”
　　随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直 接减弱。对 于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。 解决方法是用一种方法进行扫描，使没有交换的情况下主 元保留在原位置。

 

平衡快排（Balanced Quicksort） ：每次尽可能地选择一个能够 代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。通常来说， 选择这个数据的方法是取开头、结尾、中间3个数据，通过比较选出其 中的中值。 取这3个值的好处是在实际问题（例如信息学竞赛……）中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近 似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微 打乱，破坏退化的结构。

对于快排优化的问题可以看看Java API(JDK)中的例子，参见《 java.util.Arrays的排序研究 》