假设让棒球队队员在运动场上排列成一队。九个正式的队员加一个替补已经站好，准备练习。现在需要按身高从低到高为队员们排队（最矮的站在左边），给他们照一张集体照。应该怎样排序呢？
在排序这件事上，人与计算机程序相比有以下优势：我们可以同时看到所有的队员，并且可以立刻找出最高的一个，而不用费力地测量和比较每个人的身高。而且，队员们不一定要固守特定的空间，他们可以相互推推搡搡就腾出了位置，还能互相前后站立。经过一些具体的调整，就可以毫不费力地给队员们拍好队。
计算机程序却不能像人这样通览所有的数据。它只能根据计算机的“比较”操作原理，在同一时间内对两个队员进行比较。算法的这种“管视”将是一个反复出现的问题。在人类看来很简单的事情，计算机的算法缺不能看到全景，因此它只能一步一步地解决具体问题和遵循一些简单的规则。
一、冒泡排序（Bubble Sort）
1.冒泡排序描述
比较相邻两个数据项的关键字值，如果反序，则交换。若按升序排序，每一趟将被扫描的数据序列中的最大数据项交换到最后位置，就像气泡从水里冒出一样。
2.冒泡排序的Java代码
BubbleArray.java
package com.leverage.array;
public class BubbleArray {
private long[] arr; // refer to array arr
private int nElems; // number of data items
// --------------------------------------------------------------
public BubbleArray(int max) { // constructor
arr = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) { // put element into array
arr[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() { // displays array contents
for (int j = 0; j < nElems; j++) { // for each element
System.out.print(arr[j] + " "); // display it
}
System.out.println("");
}
// --------------------------------------------------------------
public void bubbleSort() {
int out, in;
for (out = nElems - 1; out > 1; out--) { // outer loop (backward)
for (in = 0; in < out; in++) { // inner loop (forward)
if (arr[in] > arr[in + 1]) { // out of order?
swap(in, in + 1); // swap them
}
}
}
}
// --------------------------------------------------------------
private void swap(int one, int two) {
long temp = arr[one];
arr[one] = arr[two];
arr[two] = temp;
}
}
BubbleSortApp.java
package com.leverage.array;
public class BubbleSortApp {
public static void main(String[] args) {
int maxSize = 100; // array size
BubbleArray arr; // reference to array
arr = new BubbleArray(maxSize); // create the array
arr.insert(66); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(11);
arr.insert(00);
arr.insert(33);
arr.insert(88);
arr.insert(22);
arr.insert(77);
arr.display(); // display items
arr.bubbleSort(); // bubble sort them
arr.display(); // display items again
}
}
在BubbleSortApp类的main()方法中，往数组中随机插入10个数据项，显示数组，然后调用BubbleArray类的bubbleSort()来对其排序，接着再一次显示数组。下面是输出结果：
冒泡排序之前的数组：66 99 44 55 11 0 33 88 22 77
冒泡排序之后的数组：0 11 22 33 44 55 66 77 88 99
3.冒泡排序不变性
在许多算法中，有些条件在算法执行时是不变的。这些条件被称为不变性。认识不变性对理解算法是有用的。在一定的情况下它们对调试也有用；可以反复地检查不变性是否为真，如果不是的话就标记出错。
在BubbleArray.java中，不变性是指out右边的所有数据项为有序。在算法的整个运行过程中这个条件始终为真。（在第一趟排序开始前，尚未排序，因为out开始时在数据项的最右边，没有数据项在out的右边。）
4.冒泡排序的效率
通过考察BubbleArray类的bubbleSort()方法，inner looper在第一趟排序中进行了9次比较，第二趟排序进行了8次比较，如此类推，直到最后一趟进行了一次比较。对于10个数据项，就是
9+8+7+6+5+4+3+2+1=45
一般来说，数组中有N个数据项，则第一趟排序中有N-1次比较，第二趟中有N-2次，如此类推。这种序列的求和公式如下：
(N-1)+(N-2)+(N-3)+...+3+2+1=N*(N-1)/2
当N为10时，N*(N-1)/2等于45
这样，算法作了约N^2/2次比较（忽略减1，不会有很大差别，特别是当N很大时）。
因为两个数据项只有在需要时才交换，所以交换的次数少于比较的次数。如果数据是随机的，那么大概有一半数据需要交换，则交换的次数为N^2/4。（不过在最坏的情况下，即初始数据逆序时，每次比较都需要交换。）
交换和比较操作次数都和N^2成正比。由于常数不算在大O表示法中，可以忽略2和4，并且认为冒泡排序运行需要O(N^2)时间级。
PS：无论何时，只要看到一个循环嵌套在另一个循环里，就可以怀疑这个算法的运行时间为O(N^2)时间级。外层循环执行N次，内层循环对于每一次外层循环都执行N次（或者几分之N次）。这就意味着将大约需要执行N*N或者N^2次某个基本操作。
二、选择排序（Select Sort）
1.选择排序描述
第一趟从N个数据项的数据序列中选出关键字最小（或最大）的数据项并放到最前（或最后）位置，下一趟在从N-1个数据项中选出最小（大）的数据项并放到次前（后）的位置，以此类推，经过N-1趟完成排序。
2.选择排序的Java代码
SelectArray.java
package com.leverage.array;
public class SelectArray {
private long[] arr; // refer to array arr
private int nElems; // number of data items
// -----------------------------------------------------------------
public SelectArray(int max) { // constructor
arr = new long[max]; // create the array
nElems = 0; // no items yet
}
// -----------------------------------------------------------------
public void insert(long value) { // put element into array
arr[nElems] = value; // insert it
nElems++; // increment size
}
// -----------------------------------------------------------------
public void display() { // displays array contents
for (int j = 0; j < nElems; j++) { // for each element
System.out.print(arr[j] + " "); // display it
}
System.out.println("");
}
// -----------------------------------------------------------------
public void selectSort() {
int out, in, min;
for (out = 0; out < nElems - 1; out++) { // outer loop
min = out; // minimum
for (in = out + 1; in < nElems; in++) { // inner loop
if (arr[in] < arr[min]) { // if min greater
min = in; // we have a new min
}
}
swap(out, min); // swap them
}
}
private void swap(int one, int two) {
long temp = arr[one];
arr[one] = arr[two];
arr[two] = temp;
}
}
SelectSortApp.java
package com.leverage.array;
public class SelectSortApp {
public static void main(String[] args) {
int maxSize = 100; // array size
SelectArray arr; // reference to array
arr = new SelectArray(maxSize); // create the array
arr.insert(66); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(11);
arr.insert(00);
arr.insert(33);
arr.insert(88);
arr.insert(22);
arr.insert(77);
arr.display(); // display items
arr.selectSort(); // bubble sort them
arr.display(); // display items again
}
}
在SelectSortApp类的main()方法中，往数组中随机插入10个数据项，显示数组，然后调用SelectArray类的selectSort()来对其排序，接着再一次显示数组。下面是输出结果：
选择排序之前的数组：66 99 44 55 11 0 33 88 22 77
选择排序之前的数组：0 11 22 33 44 55 66 77 88 99
3.选择排不变性
在SelectArray.java中，小标小于或等于out的位置的数据项总是有序的。
4.选择排序的效率
选择排序和冒泡排序执行了相同次数的比较：N*(N-1)/2。对于10个数据项，需要45次比较，10个数据项只需要小于10次交换。对于100个数据项，需要4950次比较，但只进行了不到100次的交换。N值很大时，比较的次数是主要的，所有结论是选择排序和冒泡排序一样运行了O(N^2)时间级。但是，选择排序无疑更快，因为它进行的交换少得多。当N值较小时，特别是如果交换的时间级比比较的时间级大得多时，选择排序实际上是相当快的。
三、插入排序（Insertion Sort）
1.插入排序描述
每趟将一个数据项，按其关键字大小，插入到它前面有序的子序列中，使得插入后的子序列仍是有序的，依次重复直到全部数据项插入完毕。
2.插入排序的Java代码
InsertArray.java
package com.leverage.array;
public class InsertArray {
private long[] arr; // refer to array arr
private int nElems; // number of data items
// -------------------------------------------------------------
public InsertArray(int max) { // constructor
arr = new long[max]; // create the array
nElems = 0; // no items yet
}
// -------------------------------------------------------------
public void insert(long value) { // put element into array
arr[nElems] = value; // insert it
nElems++; // increment size
}
// -------------------------------------------------------------
public void display() { // displays array contents
for (int j = 0; j < nElems; j++) { // for each element
System.out.print(arr[j] + " ");
}
System.out.println(""); // display it
}
// -------------------------------------------------------------
public void insertSort() {
int in, out;
for (out = 0; out < nElems; out++) { // out is dividing line
long temp = arr[out]; // remove marked item
in = out; // start shifts at out
while (in > 0 && arr[in - 1] >= temp) { // until one is smaller
arr[in] = arr[in - 1]; // shift item to right
--in; // go left one position
}
arr[in] = temp; // insert marked item
}
}
}
InsertSortApp.java
package com.leverage.array;
public class InsertSortApp {
public static void main(String[] args) {
int maxSize = 100; // array size
InsertArray arr; // reference to array
arr = new InsertArray(maxSize); // create the array
arr.insert(66); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(11);
arr.insert(00);
arr.insert(33);
arr.insert(88);
arr.insert(22);
arr.insert(77);
arr.display(); // display items
arr.insertSort(); // bubble sort them
arr.display(); // display items again
}
}
在InsertSortApp类的main()方法中，往数组中随机插入10个数据项，显示数组，然后调用InsertArray类的insertSort()来对其排序，接着再一次显示数组。下面是输出结果：
插入排序之前的数组：66 99 44 55 11 0 33 88 22 77
插入排序之后的数据：0 11 22 33 44 55 66 77 88 99
3.插入排序不变性
在每趟结束时，在将temp位置的项插入后，比outer变量下标小的数据项都是局部有序的。
4.插入排序的效率
这个算法需要多少次比较和复制呢？在第一趟排序中，它最多比较一次，第二趟最多比较两次，依次类推。最后一趟最多比较N-1次。因此有
1+2+3+...+N-3+N-2+N-1=N*(N-1)/2
然而，因为在每一趟排序发现插入点之前，平均只有全体数据项的一半真的进行了比较，我们除以2得到
N*(N-1)/4
复制的次数大致等于比较的次数。然而，一次复制与一次交换的时间花费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。
在任意情况下，对于随机顺序的数据进行插入排序需要O(N^2)时间级。
对于已经有序或基本有序的数据来说，插入排序要好得多。当数据有序时，while循环的条件总是假，所有它变成了外层循环中的一个简单语句，执行N-1次。在这种情况下，算法运行只需要O(N)时间级。如果数据基本有序，插入排序几乎只需要O(N)时间级，这对把一个基本有序的文件进行排序是一个简单而有效的方法。
然而，对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。
四、几种简单排序比较
除非手边没有算法书可参考，一般情况几乎不太使用冒泡排序算法。它过于简单了，以至于可以毫不费力地写出来。然而当数据量很小的时候它会有些应用的价值。
选择排序虽然把交换次数降到了最低，但比较的次数仍然很大。当数据量很小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择。对于更大数据量的排序来说，快速排序通常是最快的方法。