标签：data structure

    最近关注了一下c++，又想到很久没有碰的数据结构又快忘完了。又开始从简单的排序开始温习了。作为排序的最经典也是最简单的方法，冒泡，选择，插入这三种排序方法是最让人能够理解的。当然，三种方法的效率也是差不多的，都是O(n2)时间。以下就3种实现，根据自己的理解，简单的描述一番。以下实现均以由小到大的顺序进行实现。

    冒泡排序：

/**
	 * 演示冒泡排序算法
	 * 实质在于通过每次循环的冒泡将最小的放到第一位，因此从整个未排序的数组中，从后将最小的位往前推
	 */
	private static void maopaoSort(int[] ints) {
		for(int i = 0;i < ints.length;i++) {
			for(int j = ints.length - 1;j > i;j--) {//从后面往前开始冒
				if(ints[j] < ints[j - 1])
					swap(ints, j, j - 1);//将小的往前冒，即做一次转换操作
			}
		}
	}

    由上可知，冒泡就是一个将整个数组当中最小的数字，从最后面慢慢地往前冒的过程。假设最小的数在第N位，那么在冒泡的过程中，就是首先通过N冒泡，将N冒到N-1位上，再冒到N-2上（由N-1与N-2比较），最后一直冒到数组的第0位。这样一次子循环下来，最小的数就冒好了。接下来，就开始冒第二小的数了，那么这个数自然就放到i+1即第1位上了。

    选择排序：

/**
	 * 演示选择排序算法
	 * 选择排序的实质在于每次循环从后面的数中选择一个最小的数，放到数组的最前面
	 * 因此每次的比较在于将当前最小的数与当前数相比较，比较之后将小的放到正确的位置上
	 */
	private static void xuanzeSort(int[] ints) {
		for(int i = 0;i < ints.length;i++) {
			int m = i;//假设当前最小的数的下标即为i
			for(int j = i + 1;j < ints.length;j++) {
				if(ints[m] > ints[j]) {//与最小的数比，即与下标为m的数比
					m = j;//重置最小的数的下标
				}
			}
			swap(ints, i, m);//交换两个数，将最小的数放到当前位置上
		}
	}

    由代码可以看出，选择排序和冒泡排序差不多，区别在于在选择排序当中，不再需要两两对比和交换，而是将最小的数与循环中的数进行比较，而且只需要记录最小的数的下标即可。最后将最小的数的下标和当前正在处理的数下标交换即可。如当前正确排到第3位了，前2位自然是已经排好序的了。假设第5位数是最小的，那么最后，就是交换第3位和第5位，然后又从第4位数进行处理了。

    插入排序：

/**
	 * 演示插入排序
	 * <p/>
	 * 实质在于将当前位置上的数插入到前面已经排好序的数组当中，即在进行排序时，当前位置之前的数组实际上是已
	 * 经排好序了的
	 */
	private static void charuSort(int[] ints) {
		for(int i = 1;i < ints.length;i++) {
			int j = i;//记录当前操作的数的下标，即从当前下票开始
			int temp = ints[j];//记录当前要操作的数
			while(j > 0 && temp < ints[j - 1]) {//只有当操作的数小于前面的数时才往前移位置
				ints[j] = ints[j - 1];//将前面的一个数往后移，即将前一个数的值放到后一个下标当中
				j--;
			}
			//找到最终的一个下标，当前数比下标前一个数小，下标后面的数在比较过程中均往后移了一位
			ints[j] = temp;
		}
	}

    插入排序是和前面两个排序最不相同的排序方法了。前面两种方法即是将已经处理且不会再进行二次处理的的数放到一边，再处理剩余的数。而插入是假设前面的数是排好序的，并不关心没有排序的数是否就一定要比排好序的数小。它所做的即是将当前正在处理的数放到前面处理好排好序的数的中间。即原来处理好的数的长度为5,当增加当前处理数之后，长度就变为6了。且数根据一定的规则放到6位长度的数中的其中一个位置上。
    插入核心的地方就是处理将数往前面的数组里面插入的过程，在这里，当然可以使用swap，将当前处理的数和前面比较的数进行调换位置，但考虑到效率上的原因。这里直接将前面比较的数往后放，等到找到一个可以放当前处理数的一标时，再将此数放到正确的位置上即可。

    总结：

    在实现中，前面三个算法在实现的过程当中，肯定有很多的陷阱。如何更好地实现一个排序，并考虑到效率和理解程序上。一个简单的程序也可以写得很长。但简单的算法肯定要考虑到很多种情况，并且要在大多数的场景下都可以很好地工作。重在理解，理解好了，程序就好写了。