排序(一)
初级排序算法选择排序
思想：首先，找到数组中最小的那个元素。其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
【图例】
图中，x轴方向为数组的索引，y轴方向为待排序元素的值。
选择排序有两个很鲜明的特点：
运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点。（无论数组的初始状态是什么，此算法效率都一样低效）
数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了N次交换——交换次数和数组的大小是线性关系。（我们将研究的其他任何算法都不具备这个特征）
【对于长度为N的数组，选择排序需要大约N2/2次比较和N次交换】
冒泡排序
思想：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。（较大的元素也会慢慢沉到底部。）
冒泡排序算法的运作如下：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
【图例】
图中，x轴方向为数组的索引，y轴方向为待排序元素的值。
由图中可看出，冒泡排序是从后到前，逐步有序的，最大的元素先沉到底部，接着是次大的……
void BubbleSort(Comparable[] a){//exchanged表示是否做过交换处理，一趟冒泡没有做过交换处理，即没有改变任何元素的位置，则停止冒泡。bool exchanged = false ;int N = a.length ;//最多n-1趟冒泡排序(若发现某趟排序没有交换操作,则停止冒泡)for (int i = 1; i < N && !exchanged; i++){exchanged = false ;//从第0个到第N-1-i个 为一趟冒泡，选择出此趟中最大的值，沉到底部。for(j = 0; j < N-i; j++){//若相邻的两关键字逆序 交换if(a[j] > a[j+1]){exch(a[j], a[j+1]) ; //交换a[j]、a[j+1]exchanged = true ; //标记有元素交换位置}}//for(j)}}
特点：
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n2)次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行O(n2)，而插入排序在这个例子只需要O(n)个运算。
因此很多实现中避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。（例如上面代码）
插入排序
思想：将第i个元素与其左边的已经有序的元素一一比较，找到合适的位置，插入其中。为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。
具体算法描述如下：
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后
6、重复步骤2~5
与选择排序一样，当前索引左边的所有元素都是有序的。但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。插入排序不会访问索引右侧的元素，而选择排序不会访问索引左侧的元素。
和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。对一个其中的元素已经有序(或接近有序)的数组进行排序，将会比对随机顺序的数组或是逆序数组进行排序要快得多。
【图例】
使用插入排序为一列数字进行排序的过程。
或许是某座闻名遐迩的文化古城。我们可以沿途用镜头记录彼此的笑脸，
