排序算法

 

影响算法性能的关键因素有三个，一是时间，二是空间，三是算法本身的复杂度

 

时间：对于排序算法来说，时间开销是衡量它好坏的重要因素。一般排序都涉及到比较和移动两种操作。比较就是比较两个数的大小，移动就是把两个数的位置进行交换。高效率的算法应该具有较少的比较次数和较少的移动次数。

空间：这里的空间指的是辅助空间。也就是除了装需要排序的数之外所需要的空间。这些空间一般在排序的过程中可以用到，有的时候，可以用空间来减少时间的消耗。它们之间可以相互转换，所以空间也是衡量算法好坏的一个重要因素。

算法本身的复杂性：这里也就是从算法本身出发来说的，看你这个算法设计的合不合理，思路复不复杂。

 

=====================================================

 

排序的列表是{5，7，9，2，6，3，1，4，8}。

 

第一种冒泡排序：

思路：

第一步，把第一个数和其他的每一个数进行比较，如果后面的某一个数比第一个数还要小，那么就把后面的那个数与第一个数进行交换，然后继续进行比较。如下面的左图所示，第一个数为5，把5与后面的每个数进行比较，注意当比较到每4步的时候，由于2比5小，所以这个时候5与2要交换位置，那么2就变成了第一个数了，然后就拿2与后面的数据来比较。要明白我们是拿第一个数与剩下的数比较，也就是拿数组a[0]与后面的数进行比较，a[0]的值随时在变化。

第二步，把第二个数（也就是a[1]的值）与后面的数进行比较，如果后面有数比它小，那么也交换位置。经过第一次比较过后，第二个数就是7。那么就拿7与后面的进行比较，在第三次比较的时候，7会与5交换位置，交换后就拿5进行比较。与上面一样，这次是拿a[1]的值进行比较，a[1]的值可能在变。

第三步，第四步,……第N步，同理。

示例图：


 程序实现：

	public static Integer[] buble1(Integer[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;

				}
			}
		}
		return arr;
	}

 
 第二种冒泡排序：

上一种冒泡算法，是从数组的第一个位置开始，把每个位置的数与其他剩下的数进行比较，如果后面的数有比它小的（或者大的，下面都以小的为例）就进行交换。通过分析这个过程，可以知道，这种算法，每次冒泡的结果都是把所有数里面最小的那一个提到了最前面，而其他的数的顺序都是杂乱无章的。第二次就把第二小的数提取到最前面。每次排序后，对后面的排序都没有帮助。我们就会想，有没有一种排序的算法在把最小的提到前面去的过程中，也能把第二小或者第三小的顺序往前面挪一点呢？这样的话，我们在第二次排序的时候，交换的次数就会减少。下面的冒泡排序就是这样的一种方法。它前一次排序的结果可以给后一次排序带来一定的帮助。

思路：

1.从第一个数开始，从左到右，把相邻的两个数进行比较，如果如果后面的一个数比前面的一个数小，那么就交换它们的位置，否则的话，就不用交换。第一次循环完成后，我们会发现，最大的数9已经排在最后面了，而第二在的数8已经排在倒数第二位了。（如果用前面的排序方法就得不到这样的结果）；
2.还是从第一个数开始，从左到右，把相邻的两个数进行比较，如果后面的数比前面的数小，那么就交换位置。但注意第二次比较，只用比较到数组的倒数第二个位置就可以了。因为通过第一次比较，已经把数组里面最大的数放在了数组的最后一位，所以在第二次比较的时候，就不用跟最后一位进行比较了。

3.同理，还是从第一个数开始进行比较，比较到倒数第三个数为止。……一直到最后，只需要比较第一个数和第二个数了。

示例图：

程序实现：

	public static Integer[] buble2(Integer[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		return arr;
	}

 如果把一个有序的序列用这种方法去进行排序，它比较的次数并没有减少。其实经过第一次比较，如果没有一次数据的交换，我们就可以断定这个序列是有序的，后面就根本不需要再进行比较了。明白了这点后，我们就可以设置一个标记，它初始化为False，如果有某一次比较，没有一次数据进行交换的话，那么就可以断定这个序列目前是有序的，这时候把这个标记设置为True，后面就不需要再再进行比较，循环中止。

	public static Integer[] buble22(Integer[] arr) {
		for (int i = 0; i < arr.length; i++) {
			boolean hasOrder = true;
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					hasOrder = false;
				}
			}
			if (hasOrder)
				break;
		}
		return arr;
	}

 

选择排序：

冒泡排序它的原理就是依次把每一个数与除这个数之外的其他数进行比较，然后进行交换。很显然，这个方法有一个弊病，那就是如果另外有一个数比这个数 小，它们立刻交换位置，比如，如果a1与a2进行比较，发现a2比a1小，它们就进行交换，其时，这个时候根本不需要交换，因为我们是需要找到最小的数， 放到最前面，而此时a2只是比a1小，我们并不能确定它就是最小的数，它还没有跟后面的a3,a4等等比较呢。应该是找到最小的数的时候，我们再进行交 换。选择排序就是这样的一个原理，它和第一种冒泡排序一样，把每一个数与除这个数之外的其他数进行比较，不同的地方是，如果有比它小的，此时并不进行交 换，而是把这个比它小的数的下标记到一个min字段中去，然后用这个比较小的数，去与其他的数进行比较，每一次都把比较中最小的数放到min字段中去，最 后min字段中的值，就是数组中最小元素的下标了。

程序实现：

	public static Integer[] choose(Integer[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[minIndex] > arr[j])
					minIndex = j;
			}
			if (minIndex != i) {
				int temp = arr[i];
				arr[i] = arr[minIndex];
				arr[minIndex] = temp;
			}
		}
		return arr;
	}