Java实现6种常见排序

1.冒泡排序(Bubble Sort)

import java.util.Arrays;
//冒泡排序
public class BubbleSort {
	public static void main(String[] args) {
		int a[]=new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9};
		//i=0,第一轮比较
		for (int i = 0; i < a.length-1; i++) {
			//第一轮，两两比较
			for (int j = 0; j < a.length-1-i; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
			}
		}
		System.out.println(Arrays.toString(a));
	}
}

优化

import java.util.Arrays;
public class BubbleSort2 {
	public static void main(String[] args) {
		int a[]=new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9};
		for (int i = 0; i < a.length-1; i++) {
			boolean flag=true;
			for (int j = 0; j < a.length-1-i; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					flag=false;
				}
			}
            //省略6、7轮的比较，减少时间
			if (flag) {
				break;
			}
		}
	}
}

2.选择排序(Select Sort)

import java.util.Arrays;
//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。
public class SelectSort {
	public static void main(String[] args) {
		int a[]=new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9};
		for (int i = 0; i < a.length-1; i++) {
			int index=i;//标记第一个为待比较的数
			for (int j = i+1; j < a.length; j++) { //然后从后面遍历与第一个数比较
				if (a[j]<a[index]) {  //如果小,就交换最小值
					index=j;//保存最小元素的下标
				}
			}
			//找到最小值后，将最小的值放到第一的位置，进行下一遍循环
			int temp=a[index];
			a[index]=a[i];
			a[i]=temp;
		}
	}
}

3.插入排序(Insert Sort)

import java.util.Arrays;
//插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。
public class InsertSort{
	public static void main(String[] args) {
		int a[]=new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9};
		for (int i = 1; i < a.length; i++) {  //长度不减1，是因为要留多一个位置方便插入数
			//定义待插入的数
			int insertValue=a[i];
			//找到待插入数的前一个数的下标
			int insertIndex=i-1;
			while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较
				a[insertIndex+1]=a[insertIndex];
				insertIndex--;
			}
			a[insertIndex+1]=insertValue;
		}
	}
}

4.希尔排序(Shell Sort)

对于这样一个数组：

如果我们要插入一个元素2 ，在直接插入排序中是依次对比，比2大的元素挨个向后移动。直接插入排序的问题就在此：如果在后面来了一个特别小的元素，需要全部移动，那么排序的效率特别低。

接下来我们介绍一种更加高效率的插入排序方法：希尔排序。

对于这样一个数列：

一共有八个元素，我们用元素的数目除以二，得到步长四，把数组分为两个部分。

这一步体现了希尔排序的一个重要思想：划分部分。

但是对于奇数个元素呢？比如九个元素，我们知道，取整除法9/2=4，

在这两个部分中，取步长为四，则7和4和0比较，5和3，9和6，8和2在这四个部分中，每个部分都进行一次直接插入排序。

这每个小组进行完插入排序之后变成：

在比较第二轮时，我们把步长除以二，此时步长变成了2，数组变成了两组：①0，6，4，9，7 ②3，2，5，8

在每一组中继续进行直接插入排序
结果如下：

再将步长除以2，此时步长为1，也是最后一次排序

希尔排序最重要的就是步长，让步长不断地除以二，直到步长为1，优点是如果在数组最后加入一个小元素，他会被很快移到最前面。

import java.util.Arrays;
/**
 * 希尔排序：大的数组划分为多个小的部分，每个部分按照插入排序
 * 拆分的原则是：刚开始两部分，步长为总长除以二
 *            之后步长不断除以二
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] arr =new int[]{3,1,4,1,5,9,2,6,5,3,5,8,9};
		shellSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	//希尔排序
	public static void shellSort(int[] arr){
		//挨个遍历步长，缩短步长，直到步长为零
		for(int gap =arr.length/2;d>0;gap=gap/2){
			//遍历所有的元素
			for(int i=gap;i<arr.length;i++){
				//遍历本组中所有的元素,从第一个元素开始
				for(int j=i-gap;j>=0;j=j-gap){//本组前面的那个元素
					//如果当前元素大于加上步长之后的那个元素,（前面的比后面的大了）交换
					if(arr[j]>arr[j+gap]){
						int temp = arr[j];
						arr[j]=arr[j+gap];
						arr[j+gap]=temp;			
					}					
				}
			}			
		}		
	}
}

5.快速排序(Quick Sort)

高快省的排序算法

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（就是一个用来参照的数）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：

3 1 2 5 4 6 9 7 10 8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

排序算法显神威

方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边，让哨兵j指向序列的最右边。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：

6 1 2 5 9 3 4 7 10 8

到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：

3 1 2 5 4 6 9 7 10 8

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧

如果你模拟的没有错，调整完毕之后的序列的顺序应该是：

2 1 3 5 4

OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下

1 2 3 4 5 6 7 8 9 10

到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面用图片来描述下整个算法的处理过程。

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。

(上面的轮数只是为了更好判断，因为有递归，不代表实际轮数)
import java.util.Arrays;
//快速排序：冒泡排序的升华版
public class QuickSort {
	public static void main(String[] args) {
		int a[]={3,1,4,1,5,9,2,6,5,3,5,8,9};
		quicksort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
	private static void quicksort(int[] a, int low, int high) {
		int i,j;
		if (low>high) {
			return;
		}
		i=low;
		j=high;
		int temp=a[low];//基准位,low=length时，会报异常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必须在if判断后面,就跳出方法。
		while(i<j){
			//先从右边开始往左递减，找到比temp小的值才停止
			while ( temp<=a[j] && i<j) {
				j--;
			}
			//再看左边开始往右递增，找到比temp大的值才停止
			while ( temp>=a[i] && i<j) {
				i++;
			}
			//满足 i<j 就交换,继续循环while(i<j)
			if (i<j) {
				int t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
		//最后将基准位跟 a[i]与a[j]相等的位置，进行交换,此时i=j
		a[low]=a[i];
		a[i]=temp;
		//左递归
		quicksort(a, low, j-1);
		//右递归
		quicksort(a, j+1, high);	
	}
}

6.归并排序(Merge Sort)

import java.util.Arrays;
//归并排序
public class MergeSort {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		int temp[]=new int[a.length];
		mergesort(a,0,a.length-1,temp);
		System.out.println(Arrays.toString(a));
	}
	private static void mergesort(int[] a, int left, int right, int[] temp) {
		//分解
		if (left<right) {
			int mid=(left+right)/2;
			//向左递归进行分解
			mergesort(a, left, mid, temp);
			//向右递归进行分解
			mergesort(a, mid+1, right, temp);
			//每分解一次便合并一次
			merge(a,left,right,mid,temp);
		}
	}
	/**
	 *
	 * @param a  待排序的数组
	 * @param left  左边有序序列的初始索引
	 * @param right 右边有序序列的初始索引
	 * @param mid	中间索引
	 * @param temp	做中转的数组
	 */
	private static void merge(int[] a, int left, int right, int mid, int[] temp) {
		int i=left; //初始i，左边有序序列的初始索引
		int j=mid+1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）
		int t=0;//指向temp数组的当前索引，初始为0
		//先把左右两边的数据（已经有序）按规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完成为止
		while (i<=mid && j<=right) {
			//如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中
			if (a[i]<=a[j]) {
				temp[t]=a[i];
				t++;//索引向后移
				i++;//i后移
			}else {
				//反之，将右边有序序列的当前元素填充到temp数组中
				temp[t]=a[j];
				t++;//索引向后移
				j++;//j后移
			}
		}
		//把剩余数据的一边的元素填充到temp中
		while (i<=mid) {
			//此时说明左边序列还有剩余元素
			//全部填充到temp数组
			temp[t]=a[i];
			t++;
			i++;
		}
		while (j<=right) {
			//此时说明左边序列还有剩余元素
			//全部填充到temp数组
			temp[t]=a[j];
			t++;
			j++;
		}
		//将temp数组的元素复制到原数组
		t=0;
		int tempLeft=left;
		while (tempLeft<=right) {
			a[tempLeft]=temp[t];
			t++;
			tempLeft++;
		}
	}	
}