排序算法总结及java实现

十种排序算法的基本特性：

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
快速排序	Ο（nlogn)	Ο（nlogn)	Ο（n2)	Ο（logn)	in-place	不稳定
归并排序	Ο（nlogn)	Ο（nlogn)	Ο（nlogn)	Ο（n)	out-place	稳定
堆排序	Ο（nlogn)	Ο（nlogn)	Ο（nlogn)	Ο（1)	in-place	不稳定
shell排序	Ο（nlogn)	Ο（nlog2n)	Ο（nlog2n)	Ο（1)	in-place	不稳定
插入排序	Ο（n2)	Ο（n)	Ο（n2)	Ο（1)	in-place	稳定
冒泡排序	Ο（n2)	Ο（n)	Ο（n2)	Ο（1)	in-place	稳定
选择排序	Ο（n2)	Ο（n2)	Ο（n2)	Ο（1)	in-place	不稳定
计数排序	Ο（n+k)	Ο（n+k)	Ο（n+k)	Ο（k)	out-place	稳定
桶排序	Ο（n+k)	Ο（n+k)	Ο（n2)	Ο（n+k)	out-place	稳定
基数排序	Ο（n*k)	Ο（n*k)	Ο（n*k)	Ο（n+k)	out-place	稳定

*稳定性：多个相同的值的相对位置在算法结束时是否产生变动。

一、快速排序

• 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 原理：

  设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。

  1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

  2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

  3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；

  4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；

  5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

• 变种：1）随机化快排       2）平衡快排      3）外部快排

实现：

//递归法
private static int quickOne(int data[],int left,int right)
	{
		if(data==null) return -1;
		int key=data[left];
		while(left<right)
		{
			while(left<right && data[right]>=key) right--;
			data[left]=data[right];
			while(left<right && data[left]<key) left++;
			data[right]=data[left];
		}
		data[left]=key;
		return left;
	}
	private static void quickTwo(int data[],int left,int right)
	{
		if(data==null) return ;
		int mid=quickOne(data,left,right);
		if(left<mid-1) quickTwo(data,0,mid-1);
		if(mid+1<right) quickTwo(data,mid+1,right);
	}
	public static void quickSort1(int data[])
	{
		if(data==null) return ;
		quickTwo(data,0,data.length-1);
	}
           

public static void quickSort2(int data[])
	{
		if(data==null) return ;
		ArrayQueue queue = new ArrayQueue();
		queue.inQueue(0);              //最开始序列的首下标为0
		queue.inQueue(data.length-1);    //最开始序列的尾下标为传入数组的最后一个元素下表
		while(!queue.isEmpty())
		{
			int left=queue.outQueue();
			int right=queue.outQueue();
			int mid=quickOne(data,left,right);
			if(left<mid-1)     //左序列有两个以上元素时，将左序列的首尾下标入队
			{
				queue.inQueue(left);
				queue.inQueue(mid-1);
			}
			if(mid+1<right)     //右序列有两个以上元素时，将右序列的首尾下标入队
			{
				queue.inQueue(mid+1);
				queue.inQueue(right);
			}
		}
	}
           

二、归并排序

• 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

• 原理：

  第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

  第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

  第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

  重复步骤3直到某一指针超出序列尾

  将另一序列剩下的所有元素直接复制到合并序列尾

• 归排一般用于对总体无序，但是各子项相对有序的数列
• 改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。

三、堆排序

四、Shell排序

• 希尔排序是一种快速排序法，又称作缩小增量排序

• 基本思想：

  　　不断把待排序的对象分成若干个小组，对同一小组内的对象采用直接插入法排序，当完成了所有对象都分在一个组内的排序后，排序过程结束。每次比较指定间距的两个数据项，若左边的值小于右边的值，则交换它们的位置。间距d按给定公式减少： di+1 =（di +1）/2 ，直到d等于1为止。

实现：

public static void shellSort(int data[])
	{
		if(data==null) return ;
		int k=data.length/2+1;
		while(k>0)
		{
			for(int i=0;i<data.length-k;i++)
			{
				if(data[i]>data[i+k])
				{
					int t=data[i];
					data[i]=data[i+k];
					data[i+k]=t;
				}			
			}
		k--;
		}
	}
           

五、插入排序

• 原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 具体算法：

  从第一个元素开始，该元素可以认为已经被排序

  取出下一个元素，在已经排序的元素序列中从后向前扫描

  如果该元素（已排序）大于新元素，将该元素移到下一位置

  重复上述步骤，直到找到已排序的元素小于或者等于新元素的位置

  将新元素插入到该位置后

• 变种：

  二分查找插入排序：查找插入位置部分使用二分查找法

  伪冒泡插入排序：插入部分使用冒泡排序法

实现：

//普通插入排序
	public static void insertionSort(int data[])
	{
		if(data==null) return ;
		for(int i=1;i<data.length;i++)
		{
			int j=0;
			int t=data[i];
			for(j=0;j<i;j++)			
				if(t<=data[j]) break;   //将数据插入第一个比它大的数之前
			for(int k=i;k>j;k--)
			{
				data[k]=data[k-1];
			}
			data[j]=t;				
			
		}
	}
           

//折半插入排序
	public static void binarySort(int data[])
	{
		if(data==null) return ;
		for(int i=1;i<data.length;i++)
		{
			int key=data[i];
			int low = 0;
	        int high = i-1;
			for(int j=0;j<i;j++)
			{
				while (low<=high) 
				{
		        	int mid = (low+high)/2;
		            if(data[mid]== key)
		            {
		            	high=mid;
		            	break;
		            }     
		            else if (data[mid] < key) low = mid+1;
		            else if (data[mid] > key) high = mid-1;
		        }				
			}
			high++;
			for(int k=i;k>high;k--)
				data[k]=data[k-1];
			data[high]=key;	
		}		       
	}
           

//伪冒泡插入排序
public static void insertionSort2(int data[])
	{
		if(data==null) return;
		for(int i=1;i<data.length;i++)
		{
			for(int j=i;j>0;j--)
			{
				if(data[j]<data[j-1])        //伪冒泡交换
				{
					int t=data[j];
					data[j]=data[j-1];
					data[j-1]=t;
				}
				else break;
			}	
		}
	}
           

六、冒泡排序

• 算法描述：
  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。因此，最后的元素为最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 重复上述过程，直至所有元素有序

实现：

public static void bobSort(int data[])
	{
		if(data==null) return;   //保证程序的健壮性！
		
		int len = data.length-1;
		while(len>0){		
			for(int i=0;i<len;i++)
			{
				if(data[i]>data[i+1])
				{
					int t = data[i];
					data[i] = data[i+1];
					data[i+1] = t;
				}
			}
			len--;
		}
	}
           

七、选择排序

• 基本算法：

  每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

实现：

//选择排序
	public static void selectionSort(int data[])
	{
		for(int i=0;i<data.length;i++)
			{
				for(int j=i+1;j<data.length;j++)
				{
					if(data[j]<data[i])
					{
						int t = data[j];
						data[j] = data[i];
						data[i] = t;
					}	
				}
			}
	}