七种基本的排序

       排序很多种，其中，七种排序是比较基本的排序方式，这七种排序分别是选择，冒泡，归并，快速，基数，插入，希尔排序。其他排序还有堆排序，桶排序，二叉树排序，图书馆排序，鸡尾酒排序等等，有兴趣的可以去研究。

      一：冒泡排序

      在所有的排序中，冒泡排序是最简单的，每一趟扫描都将最大值或者最小值扫描到队首/队尾，经过n趟扫描，这就可以了。这种排序的时间复杂度是O(n*n)，最最理想的情况，可以达到O(1)

程序员都应该去看代码：

private static void bubbleSort(int[] a, int length) {
		boolean flag = true;
		for (int i = 0; i < length && flag; i++) {
			flag = false;
			for (int j = 0; j < length - i - 1; j++) {
				if (a[j] < a[j + 1]) {
					change(a, j + 1, j);
					flag = true;
				}
			}
		}
	}

 代码中，change是改变数组a中两个参数的位置。这个算法需要注意的是定义一个flag标量，当已经排好序但是扫描没有完成的时候，可以提前完成，只有这样，可以将时间复杂度降低到n(1)。

二：选择排序

这中算法的思想也很简单，每一次扫描都选出将未排序的部分的最大or最小值，与预定位置相比较，其时间复杂度也为O(n*n)

代码：

private static void selectionSort(int[] a, int length) {
		for (int i = 0; i < length; i++) {
			int num = a[i];
			int loc = i;
			for (int j = i + 1; j < length; j++) {
				if (a[j] > num) {
					num = a[j];
					loc = j;
				}
			}
			change(a, i, loc);
		}
	}

 与冒泡排序相同，也可以加入一个flag标量，这里就不详细说了。

三and四：归并排序 快速排序

归并排序与快速排序其实上是逆过程，他们都可以采用分治策略来实现。归并排序是将一个数组分为两部分，两部分分别排序好之后，然后将两个已经排序好的数组进行合并；快速排序是先将数组分为两个数组A,B，其中A中的每一个元素的数值都小于B中的元素，然后对A，B两个数组再分别进行排序，就可以了。

代码：

// 快速排序
	private static void quickSort(int[] a, int i, int j) {
		if (i >= j) {
			return;
		}
		if (i + 1 == j) {
			if (a[i] < a[j]) {
				change(a, i, j);
			}
			return;
		}

		int[] first = new int[j - i + 1];
		int[] last = new int[j - i + 1];
		int firstNum = 0;
		int lastNum = 0;
		int sentinel = a[i];
		// System.out.println(i+" "+sentinel);
		for (int n = i + 1; n <= j; n++) {
			if (a[n] > sentinel) {
				first[firstNum++] = a[n];
			} else {
				last[lastNum++] = a[n];
			}
		}
		for (int n = 0; n < firstNum; n++) {
			a[n + i] = first[n];
		}

		a[firstNum + i] = sentinel;
		for (int n = 0; n < lastNum; n++) {
			a[n + firstNum + 1 + i] = last[n];
		}
		quickSort(a, i, firstNum - 1 + i);
		quickSort(a, firstNum + 1 + i, j);

	}

	// 归并排序
	private static void mergeSort(int[] a, int i, int j) {
		if (i >= j) {
			return;
		}
		if (i + 1 == j) {
			if (a[i] < a[j]) {
				change(a, i, j);
			}
			return;
		}
		int middle = (i + j) / 2;
		mergeSort(a, i, middle);
		mergeSort(a, middle + 1, j);
		int[] b = new int[j - i + 1];
		int beforeMiddle = i;
		int afterMiddle = middle + 1;
		int bNum = 0;
		while (beforeMiddle <= middle && afterMiddle <= j) {
			if (a[beforeMiddle] > a[afterMiddle]) {
				b[bNum] = a[beforeMiddle];
				beforeMiddle++;
				bNum++;
			} else {
				b[bNum] = a[afterMiddle];
				afterMiddle++;
				bNum++;
			}
		}
		while (beforeMiddle <= middle) {
			b[bNum] = a[beforeMiddle];
			bNum++;
			beforeMiddle++;
		}
		while (afterMiddle <= j) {
			b[bNum] = a[afterMiddle];
			bNum++;
			afterMiddle++;
		}
		// print(b,0,b.length-1);
		for (int n = i; n <= j; n++) {
			a[n] = b[n - i];
		}
	}

 两种算法的时间复杂度都为O(n*log(n))

五 基数排序

基数排序是一种很有趣的排序方式，它首先将数组中元素的个位数进行排序，然后以此从十位数，百位数进行排序。这种算法很巧妙，其时间复杂度为O(k*n)，非常理想是吧？

// 基数排序
	private static void baseSort(int[] array, int redix, int distance) {
		int[] temp = new int[array.length];
		int[] count = new int[redix];
		int divide = 1;
		for (int i = 0; i < distance; i++) {
			System.arraycopy(array, 0, temp, 0, array.length);
			Arrays.fill(count, 0);

			for (int j = 0; j < array.length; j++) {
				int key = (temp[j] / divide) % redix;
				count[key]++;
			}
			for (int j = 1; j < redix; j++) {
				count[j] += count[j - 1];
			}
			for (int j = array.length - 1; j >= 0; j--) {
				int key = (temp[j] / divide) % redix;
				count[key]--;
				array[count[key]] = temp[j];
			}
			divide *= redix;
		}
	}

 该方法中，redix是基数，distance是最大的位数，例如数组{66,77,9834,7812,67,8,673445}，redix可以设定为10，distance为6。

六or七：插入排序和希尔排序

希尔排序是插入排序的升级版，所以先讲插入排序。有一个未排序的数组A,则新建一个数组B，B可以认定为有序的，将A中的元素依次插入到B中，那么就可以达到排序的目的。

代码：

private static void insertSort(int[] a, int length) {
		for(int i=1;i<a.length;i++){
			int temp=a[i];
			int j=i-1;
			while(j>=0&&a[j]>temp){
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=temp;
		}
	}

 希尔排序比这个要复杂一点，希尔排序是先设定一个步长，然后再。。。呃。。我讲不清楚，维基百科上讲的不错，我直接复制过来吧。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。

代码如下：

//希尔排序
	private static void shellSort(int[] a){
		int gap=0;
		while(gap<a.length){
			gap=gap*3+1;
		}
		while(gap>0){
			for(int i=gap;i<a.length;i++){
				int j=i-gap;
				int temp=a[i];
				while(j>=0&&a[j]>temp){
					a[j+gap]=a[j];
					j-=gap;
				}
				a[j+gap]=temp;
			}
			gap=(gap-1)/3;
		}
	}

 原文地址：http://uwind.iteye.com/blog/1944204