各种排序算法Java实现

校招快要开始了，复习一下以前的排序知识，下面的代码都是以前写的，今天翻出来又重新看了一下，贴上来。也算是复习吧。

插入排序,稳定排序（稳定是指相同的两个数在排序之后它们的相对位置不变。）：

//插入排序
	 public static void insertSort(int[] a){
		 int len = a.length;
		//遍历数组
		 for(int i=1;i<len;i++){
			 int temp = a[i];
			 int j=i-1;
			 while(j>=0&&temp<a[j]){
				//循环比较插入，即向后移动...
				 a[j+1]=a[j];
				 j--;
			 }
			 a[j+1]=temp;
		 }
	 }

希尔排序，不稳定的排序：

 //希尔排序，本质上是插入排序
		public static void shellSort(int[] a){
			int[] s = {1,3,5};
			int j,temp;
			int k=0;
			//x为希尔间隔参数,最外环的遍历，以希尔间隔参数遍历三次，当然希尔参数可以有很多，x为希尔间隔参数
			for(int x=s[2];x>=0;x-=2){
				//第二层循环：以当前的希尔变量循环一次一部分数组
				while(k<x){
					//以下是插入排序
					//希尔间隔参数里面的每一次插入排序
					for(int i=x+k;i<a.length;i+=x){
						temp = a[i];
						j = i-x;
						while(j>=k && a[j]>=temp){
							a[j+x] = a[j];
							j-=x;
						}
						a[j+x] = temp;
					}
					k++;
				}
				k=0;
			}
			
		}

快速排序，其实是冒泡排序的改进，是一种不稳定排序：

//快速排序
	public static void quick(int[] a,int i,int j){
		if(i<j){
			int q = quickSort(a,i,j);
			 quick(a,i,q-1);
			 quick(a,q+1,j);
		}
		return;
	}
	
	////快速排序i不可能等于数组的最后一个下标,而且最后i一定等于j，并且下标为i的值就是temp
	public static int quickSort(int[] a,int i,int j){
		if(a.length==1){
			return 0;
		}
		int temp  = a[i];
		//前后相互比较，把大于temp的值放在数组的后面，小于temp的值反正前面
		while(i<j){
			//当从后面比较时，大于temp就一直让自减
			while(temp<a[j]){
				j--;
			}
			//如果下降到i==j的时候则不要交换了
			if(i!=j){
				swap(a,i,j);
				i++;
			}
			//同上
			while(temp>a[i]){
				i++;
			}
			if(i!=j){
				swap(a,i,j);
				j--;
			}
		}
		return i;
	}
	
	public static void swap(int[] a,int i,int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

选择排序，不是一个稳定的排序算法：

public static void selectSort(int[] a){
		int min;
		for(int i=0;i<a.length-1;i++){
			min = i;
			for(int j = i+1;j<a.length;j++){
				//通过与临时最小的比较，得到当前的最小
				if(a[j]<a[min]){
					min = j;
				}
			}
			swap(a,i,min);
		}
	}

冒泡排序，稳定排序：

	 public static void bubbleSort(int[] a){
			for(int i=a.length-1;i>0;i--){
				for(int j=0;j<i;j++){
					if(a[j]>a[j+1]){
						swap(a,j,j+1);
					}
				}
			}
		}

归并排序，稳定排序：

public static void mergeSort(int[] a){
		mergeSort(a,0,a.length-1);
	}
	//递归合并
	public static void mergeSort(int[] a,int first,int last){
		int mid = (first+last)/2;
		if(first<last){
			mergeSort(a,first,mid);
			mergeSort(a,mid+1,last);
			merge(a,first,mid,last);
		}
	}
	//其中first，mid，last都是在数组中的索引，last==a.length-1
	public static void merge(int[] a,int first,int mid,int last){
		int[] c = new int[last-first+1];
		int aIndex = first;
		int cIndex =0;//c的索引
		int bIndex = mid+1;
		while(aIndex<mid+1 && bIndex<last+1){
			if(a[aIndex]<a[bIndex]){
				c[cIndex++] = a[aIndex++];
			}else{
				c[cIndex++] = a[bIndex++];
			}
		}
		if(aIndex<=mid){
			while(aIndex<=mid){
				c[cIndex++] = a[aIndex++];
			}
		}
		if(bIndex<=last){
			while(bIndex<=last){
				c[cIndex++] = a[bIndex++];
			}
		}
		//c排序完成之后，把c中的值都赋给a，改变a的值以便循环递归
		for(int i=0;i<c.length;i++){
			a[first+i] = c[i];
		}
		
	}

堆排序，不是稳定的排序，非常适合大数据（如百万级别的），因为快速排序和归并排序都是基于递归的，有可能发生堆栈溢出：

	//堆排序核心算法
	//调用了建堆函数和以i为最大堆的函数
	public static void heapSort(int[] a){
		buildHeap(a);
		int heapSize = a.length;
		for(int i=a.length-1;i>=0;i--){
			 swap(a,0,i);
			 heapSize--;
			 maxHeap(a,0,heapSize);
		}
	}
	
	//建造一个大顶堆,从索引a.length/2-1开始，对每个元素使用maxHeap,即可以建立一个大顶堆
	public static void buildHeap(int[] a){
		int lag = (int)Math.ceil(a.length/2)-1;
		for(int i=lag;i>=0;i--){
			maxHeap(a,i,a.length);
		}
	}
	
	//以i为最大堆,i在输入的时候，让i节点的值比他的左右子女都要大
	public static void maxHeap(int[] a,int i,int heapSize){
		//因为堆是从1开始算的，数组是从0开始算的，所以在外面是以数组的形式i传进来要加1
		int left = 2*(i+1)-1;
		int right = 2*(i+1);
		int large;
		if(left<heapSize&& a[left]>a[i]){
			large = left;
		}else{
			large = i;
		}
		if(right<heapSize && a[right]>a[large]){
			large = right;
		}
		if(large!=i){
			swap(a,i,large);
			maxHeap(a,large,heapSize);
		}
	}

以下从网上摘抄的各种排序的一些比较：

不过其中归并的额外空间应该是O（n）

参考：

博客：http://blog.csdn.net/hkx1n/article/details/3922249