几种常用的排序算法 博客分类： 数据结构 算法

按照排序过程中所使用的内外存情况不同，可把排序分为内排序和外排序两大类；若排序过程全部在内存数据表（如数组）中进行，则成为内排序，若排序过程需要不断地进行内存数组和外村文件之间的数据交换，则成为外排序。对于大的数据文件，由于内存限制不能一次装入内存进行排序，只能进行外排序来完成。
常用的排序有：插入排序，选择排序，堆排序，快速排序，归并排序，二路归并的外排序等。
1、插入排序
将数组a中待排序的n个元素看成一个有序表和一个无序表，开始的时候有序表总只含有一个元素，无序表总含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把他插入到有序表中的适当位置，使之成为新的有序表，经过n-1次插入后，无序表就成为有序表了。
直接插入排序的平均时间复杂的为O(n^2)，但当待排序记录接近有序时，时间按复杂度接近O(n)，所以直接插入法排序适合于袁术数据基本有序的情况。排序过程中只使用一个临时工作单元x，其空间复杂度为O(1)。另外直接插入排序是稳定的，因为具有同一排序码的后一元素必然插在具有同一排序码的前一元素的后面，即相对次序保持不变。

//直接插入排序
	public static void insertSort(Object[]a,int n){
		//n是a中将要排序的个数，全部排序时，n=a.length
		if(n>a.length)
		{
			System.out.println("n值有误，停止执行");
			System.exit(0);
		}
		for(int i=0;i<n;i++){
			Object x=a[i];//x存的是待排序的值，用来比较
			int j;
			for(j=i-1;j>=0;j--){
				if(((Comparable)x).compareTo(a[j])<0){//发现第j个值比x大，因为升序排列所以将其后移
					a[j+1]=a[j];
				}
				else break;//查询到插入的位置时离开内循环，前面的值肯定都比x小
			}
			a[j+1]=x;//将原a[i]的值写入到下标为j+1的位置
		}
	}

2、选择排序（直接选择排序和堆排序两种）
（1）直接选择排序：每次从当前待排序的区间中选出最小排序码的元素，把该元素与该区间的第一个元素交换位置。
直接选择排序的时间复杂的为O(n^2)。由于选择排序存在着前后元素之间的互换，可能会改变相同排序码元素的前后相对位置，所以此方法是不稳定的。

//	直接选择排序
	public static void selectSort(Object[]a,int n){
		if(n>a.length){
			System.out.println("n取值有误，退出");
			System.exit(0);
		}
		for(int i=1;i<=n-1;i++){//i表示次数，工进行n-1次选择和排序
			int k=i-1;//k标志最小排序的元素的下标，初始值是i-1;
			int j;
			for(j=i;j<n;j++){
				if(((Comparable)a[k]).compareTo(a[j])>0){
					k=j;
				}
			}
			if(k!=i-1){//把a[k]对调到当前排序区间的第1个位置，即i-1位置
				Object x=a[i-1];
				a[i-1]=a[k];
				a[k]=x;
			}
		}
	}

（2）堆排序(heap sort)是利用堆的特性进行排序的过程。堆排序包括初始化堆和利用堆排序两个阶段。对堆中下标为i的元素进行筛选运算的过程是：首先把Ri元素的排序码Si与两个孩子中排序码较大者Sj（j=2i+1或j=2i+2）进行比较，若Si>Sj，则以Si为根的子树已经调整为堆，筛选运算完毕；否则Ri与Rj互换位置，互换后可能破坏以Rj（此时的Rj的值为原来的Ri的值）为根的堆，接着再把Rj与他的两个孩子中排序码较大者进行比较，以此类推，直到父节点的排序码大于等于还子结点中较大的排序码或者孩子结点为空时为止。这样，以Ri为根的子树就被调整为一个堆。在对Ri进行筛选运算中，若他的排序码较小则会被逐层下移，就像过筛子一项，小的漏下去，大的被选上来，所以把构成堆的过程形象地成为筛运算。

筛选运算：代码如下，结果是将当前区间最大的值放到最前

	public static void sift(Object[]a,int n,int i){
		//对a[n]数组中的a[i]元素进行筛运算
		Object x=a[i];//将待筛结点的值缓存于x中
		int j=2*i+1;//a[j]是a[i]的左孩子
		while(j<=n-1){
			if(j<n-1&&((Comparable)a[j]).compareTo(a[j+1])<0){//当左孩子不为空时执行循环
				j++;//若存在右孩子比左孩子排序码大，则把j修改为右孩子的下标
			}
			if(((Comparable)x).compareTo(a[j])<0){
				a[i]=a[j];//将a[j]调到双亲位置上
				i=j;j=2*i+1;//修改j和i的值，以便继续向下筛
			}
			else break;//查找到x的最终位置为i，退出循环
		}
		a[i]=x;//被筛选节点的值放入最终位置
		
	}

排序过程：先完成堆的初始化，将大的值放到前边，在通过n-1次循环（结点对调，将当前区间中最大的值放到最后边），完成排序

	public static void heapSort(Object []a,int n){
		//利用堆排序的方法对数组a中的n个元素进行排序
		if(n>a.length){
			System.out.println("n值有误，停止");
			System.exit(1);
		}
		for(int i=n/2-1;i>=0;i--){//建立初始堆
			sift(a,n,i);
		}
		for(int i=1;i<=n-1;i++){//进行n-1次循环，完成堆排序
			//将树根节点的值同当前区间内最后一个结点的值兑换
			Object x=a[0];a[0]=a[n-i];a[n-i]=x;
			//筛a[0]结点，得到前n-i个节点的堆
			sift(a,n-i,0);
		}
	}

Object[] c={36,25,48,12,65,43,20,58};
		heapSort(c,c.length);
		for(int i=0;i<c.length;i++){
			System.out.print(c[i]+",");
		}

整个堆排序过程中，进行n+n/2+1次筛运算，每次筛运算进行父子或兄弟节点的排序码的比较次数和记录的移动次数都不会超过完全二叉树的高度，所以每次筛运算的时间按复杂度是O(log2n),故整个堆排序的时间复杂度为O(nlog(2n))；堆排序在过程中要交换位置元素所以是不稳定排序，其空间复杂度为O(1)
3、交换排序（包括冒泡排序和快速排序）
（1）冒泡排序是一种简单排序。通过相邻元素之间的比较和交换使排序码较小的元素卓教案从底层移向顶层。每趟排序将排序码最小的一位值前移到最前（由于相邻元素都经过两两比较所以每趟都能取出当前待排序序列号中最小值），共需要n-1趟。

public static void bubbleSort(Object []a,int n){
		if(n>a.length){
			System.out.println("error");
			System.exit(1);
		}
		for(int i=0;i<n;i++){
			boolean flag=false;//可能进行一次排序后变成有序序列，用flag判断
			for(int j=n-1;j>i;j--){
				Object x=a[j];
				if(((Comparable)x).compareTo(a[j-1])>0){//相邻元素交换
					a[j]=a[j-1];
					a[j-1]=x;
					flag=true;
				}
			}
			if(flag==false) return;
		}
	}

冒泡排序算法的时间复杂的为O(n^2），由于冒泡排序通常比直接插入排序和直接选择排序需要移动比较多的次数，所以他是3种简单排序中速度最慢的一个，另外冒泡排序树稳定的。
（2）快速排序（quick Sort）又称为划分排序。是对冒泡排序的一种改进方法，在快速排序中，记录的比较和交换是从两端向中间进行的，排序码较大的记录一次就能够交换到后面的单元，排序码较小的记录一次就能够交换到前面的单元，记录每次移动的距离较远，因而总的比较和移动次数较少。
快排的过程：首先从待排序区间中选取第一个元素作为比较的基准元素，通过从区间两端向中间顺序进行比较和交换，把在前面向后扫描到的大于基准元素排序码同在后面向前扫描到的小于基准元素排序码的元素交换位置，当所有元素都比较一遍后，把基准元素交换到前后两部分单元的交界处。结果是前面单元的元素均小于基准元素，后面的元素均大于基准元素，而且基准元素的位置就是最终的排序位置，然后对划分好的区间再次划分排序，直到一个区间为空或只含一个元素时，即结束该区间上的快速排序过程。
划分过程：

public static int partition(Object a[],int s,int t){
		//对数组a中的下标从s到t区间内的元素济宁一次划分，返回中间位置j
		int i=s,j=t;//给i，j赋初始值
		Object x=a[i++];//现将基准元素存到空间中，在将位置后移一位
		while(i<=j){
			while(i<=j&&((Comparable)x).compareTo(a[i])>0){
				i++;//将i的位置后移，直到遇到大于基准元素的元素，或者i>j
			}
			while(j>=i&&((Comparable)x).compareTo(a[j])<0){
				j--;//将j的位置前移，直到遇到小于基准元素的元素
			}
			if(i<j){//i,j还没相遇，即没有遍历完一遍
				Object y=a[j];
				a[j]=a[i];
				a[i]=y;
			}
			//遍历完后将基准元素和j位置的元素交换，此时j位置的元素是最后一个小于基准元素的元素，所以将他们对调
			
		}
		
		return j;//j的位置就是现在基准元素的位置
	}

迭代过程：

public static void quickRecursion(Object a[],int s,int t){
		int j=partition(a, s, t);//对当前排序区间内进行一次划分；
		if(s<j-1)
			quickRecursion(a, s, j-1);//在左区间内超过一个元素时递归排序最区间
		if(j+1<t)
			quickRecursion(a, j+1, t);//在右区间内超过一个元素时递归排序区间
	}

排序过程：

//	对数组a中n个元素进行快速排序
	public static void quickSort(Object []a,int n){
		if(n>a.length){
			System.out.println("error!");
			System.exit(1);
		}
		quickRecursion(a, 0, n-1);//调用上面的方法，从第0个开始，最后一个结束，遍历排序
	}

快速排序是不稳定的，平均情况下快速排序算法的时间复杂度是O(nlog2n)。实践证明：当n较大时，快速排序是目前为止在平均情况下最快的一种排序方法。空间复杂的为O(log2n)，比之前讨论的方法多占用一些辅助存储空间。
最好的情况：时间复杂的O(nlog2n)
最差的情况：时间复杂的O(n^2)，空间复杂度O(n），此时快速排序就变成了“慢排序”
4、归并排序
归并（ merge）就是将两个或多个有序表合成一个有序表的过程。
将两个有序的表归位一个有序表叫二路归并，思路：比较两个表的第一个元素的大小，将二者较小的值复制到排序表中，将序号后移，比较下一对待比较元素，直到其中一个表元素复制完，将另一个表中剩余元素复制到排序表中
归并排序（merge Sort）就是利用归并操作把一个无序表排列成一个有序表的过程。利用二路归并操作排序的过程：首先将待排序区间中的每一个元素都看作一个有序表，则n个元素构成n个有序表，接着两两归并，即第一个与第二个，第三个与第四个。。。若最后剩下一个表则直接进入下一趟归并；然后再两两归并，如此下去直到归并第log2n向上取整趟后得到一个长度为n的有序表为止。
两两归并过程：

public static void twoMerge(Object[]a,Object[]r,int s,int m,int t){
		//把相邻有序表a[s]-a[m]和a[m+1]-a[t]归并为一个有序表a[s]-s[t]
		int i=s,j=m+1,k=s;//分别给知识指示每个有序表元素位置的指针赋初值
		while(i<=m&&j<=t){//当两个表中的元素不为空时
			if(((Comparable)a[i]).compareTo(a[j])<=0){
				r[k]=a[i];i++;k++;
			}else{
				r[k]=a[j];j++;k++;
			}
		}
		while(i<=m){//当还有可能为归并的元素
			r[k]=a[i];i++;k++;
		}
		while(j<=t){//当还有可能为归并的元素
			r[k]=a[j];j++;k++;
		}
	}

每一趟归并过程：

//进行一趟二路归并过程算法
	public static void mergePass(Object []a,Object []r,int n,int len){
		//将数组a[n]中每个长度为len的有序表两两归并到数组r[n]中
		int p=0;
		while(p+2*len-1<=n-1){
			twoMerge(a,r,p,p+len-1,p+2*len-1);
			p=p+2*len;
		}
		//归并最后两个长度不等的有序表
		if(p+len-1<=n-1){//剩下的元素个数大于len个小于2*len，还可以划分两个表
			twoMerge(a,r,p,p+len-1,n-1);
		}else{//剩下的元素个数小于len,将最后一个表中的数据复制到r中
			for(int i=p;i<=n-1;i++)r[i]=a[i];//赋值元素
		}
	}

归并排序过程：

public static void mergeSort(Object[]a,int n){
		//采用归并排序对数组a中的n个记录进行排序
		Object []r=new Object[n];
		int len=1;
		while(len<n){
			//从a归并到r中，得到每个有序表的长度为2*len
			mergePass(a,r,n,len);
			len=len*2;
			//从r归并到a中得到每个有序表的长度为2*len
			mergePass(r,a,n,len);
			len=len*2;
		}
	}

二路归并时间复杂度等于归并趟数与每一趟时间复杂度的乘积，O(nlog2n)，空间复杂度O(n），二路归并排序是稳定的，因为在每两个有序表归并时，若分别在两个有序表中有相同排序码的元素，twoMerge算法可以使前一个有序表中同一排序码的元素先被复制

5、外排序
外排序就是对外存文件中的记录进行排序的过程，排序结果任然被放到外存文件中。
外存文件的排序中最适合采用归并排序的方法。
减少归并趟数和访问外存的次数，提高外村排序速度需要提高初始归并段的长度，要求在对磁盘文件归并排序之前首先利用一种排序方法，按照初始归并段确定的长度在原文件上依次建立好每个有序表，然后再调用对文件的归并排序算法完成排序。
进行外排序需要4个文件，对原待排序文件f1按照初始归并段进行内排序，把内排序好的数据段交替写入两个数据文件f2,f3中，进行归并排序并把归并好的文件内容交替写入f4,f5,同样再对f4,f5文件中的数据进行归并排序并将数据交替写入f2,f3，这样每归并一趟，其归并长度就增加一倍，直到f2中含有一个归并段，且包含全部记录，f3的内容为空为止，此时f2中就得到了对f1中的全部记录的有序文件。