10.1 排序算法

  所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减地排列起来的操作。排序的算法有很多，各种算法对空间的要求及时间效率也各有差别。其中插入排序和冒泡排序又被称作简单排序，它们对空间的要求不高，但时间效率不稳定。而其他一些排序相对于简单排序来说对空间的要求稍高一点，但时间效率却能稳定在很高的水平。关于空间要求和时间效率的问题，有兴趣的可以找其他参考资料研究一下。

10.1.1 冒泡排序

  冒泡排序就是依次比较相邻的两个数，将小数放在前面，大数放在后面。

  第一轮：首先比较第1个和第2个数，将小数放前，大数放后；然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后；至此第一轮结束，将最大的数放到了最后。

  第二轮：仍从第一对数开始比较，将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的数），第二轮结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。

  按此规律操作，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，类似于小的气泡往上升，所以称作冒泡排序。

  通过上面的分析可以看出，假设需要排序的序列的个数是n，则需要经过n-1轮，最终完成排序。在第一轮中，比较的次数是n-1次，之后每轮减少1次。

  用Java语言实现冒泡排序，可以用双重for循环实现，其核心代码如下。

static void bubbleSort(int[] a) {                                  //引用传递
    int temp;
    //数组的长度可以通过“数组名.length”获得
    for (int i = 0; i < a.length-1; i++) {                   //需要比较n-1轮
        for (int j = 0; j < a.length-i-1 ; j++) {      //根据a.length-i-1，每轮需要比较的次数逐轮减少1次
            if (a[j] > a[j+1]) {                           //相邻数进行比较，符合条件进行替换
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

10.1.2 插入排序

  插入排序包括直接插入排序、二分插入排序、链表插入排序和希尔排序。接下来介绍最简单的直接插入排序。

  直接插入排序存在两个表，一个是有序表，另一个是无序表。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

  第一轮：比较无序表中前两个数，然后按顺序插入到有序表中，剩下的数仍在无序表中。

  第二轮：把无序表中剩下的第一个数与有序表的两个数进行比较，然后把这个数插入到合适位置。

  按此规律操作，直至无序表中的数全部插入到有序表，完成排序。

  用Java语言实现直接插入排序的核心代码如下。

static void insertSort(int[] a) {                          //引用传递
    for(int i = 1;i < a.length; i++){
        int j = -1;
        while(j <= i && a[i] > a[++j]){     //找到a[i]应该摆放的位置
            if(j < i){
                //将j之后的数据移动一位，然后把a[i]移动到j处
                int temp = a[i];
                for(int k = i-1;k >= j;k--){
                a[k+1] = a[k];
            }
            a[j] = temp;
        }
    }
}

  直接插入排序没有充分地利用“已插入的数据已经排序”这个事实，因此有很多针对直接插入排序改进的算法，例如二分插入排序等，这里不再赘述。