浅谈排序算法（上）

计算机也许是快的，但它们不是无限快。储存器也许是廉价的，但不是免费的。

——strein《算法导论》

有一句话这么说：程序=数据结构+算法，可见算法在软件研发过程中的重要地位，那么我们今天就来学习一下算法中最基础的几种排序算法：

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 快速排序
6. 归并排序
7. 基数排序
8. 堆排序

冒泡排序

算法思想：

顾名思义，冒泡排序的精髓在于【冒泡】，我们想象一下，水底的气泡从诞生到浮出水面的过程，这个过程为：气泡诞生-气泡上浮-浮出水面破灭，那么我们在计算机语言中，就可以根据气泡的上浮原理：

诞生：确定气泡的位置——选定第一个数的位置；

上浮：将大气泡上浮——数字挨个与后移路径中的每一个数字比较大小并互换位置；

浮出水面破灭：将破灭的气泡放置最后——将比较完后的数字放置最后，暂时抛弃；

诞生2：选择第二个气泡——继续选择第一个数的位置……

……      循环直到池里的气泡都选择完毕。

冒泡排序动画演示

那么我们用Java的代码可以这样表述，另外，针对排序做了进一步的优化：

public static void maopaoSort(int[] arr){
    long start = new Date().getTime();
    boolean isSort = true;//设定一个布尔值用于判断剩下的数字是否有序，默认为True
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                isSort = false;//一旦进入次区间说明剩下的数字是无序的，仍需继续排序。
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        // 如果在某一次冒泡排序中没有交换顺序，说明该数组已经有序
        if (isSort){
            break;
        }
    }
    long end = new Date().getTime();

    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

 优点:比较简单,空间复杂度较低，是稳定的；

 缺点:时间复杂度太高，效率慢；

选择排序

算法思想：
1.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
2.从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
3.以此类推，直到所有元素均排序完毕；

选择排序图示动画

用Java演示代码如下

public static void selectSort(int[] arr){
    long start = new Date().getTime();
    for (int i = 0; i < arr.length - 1; i++) {
        int min = arr[i]; // 默认当前位置的数为最小
        int minindex = i; // 记录当前的位置坐标
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minindex = j;
            }
        }
        if (i != minindex){
            arr[minindex] = arr[i];
            arr[i] = min;
        }
    }
    long end = new Date().getTime();
    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

优点：一轮比较只需要换一次位置；

缺点：效率慢，不稳定。

插入排序

算法思想：

顾名思义，采用插入的方式，对无序数列进行排序。

可将其与抓牌比较，将新抓起的牌放入右手，并在左手按顺序比较，最后在合适的位置插入右手中的牌。

维护一个有序区，将数据一个一个插入到有序区的适当位置，直到整个数组都有序。即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序动画演示

用Java实现插入排序算法

public static void insertSort(int[] arr){
    long start = new Date().getTime();
    for (int i = 1; i < arr.length; i++) {
        int insertIndex = i;
        int insertVal = arr[i];
        while (insertIndex > 0 && insertVal < arr[insertIndex - 1]){
            arr[insertIndex] = arr[insertIndex - 1];
            insertIndex--;
        }
        arr[insertIndex] = insertVal;
    }
    long end = new Date().getTime();
    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

优点：在运行次数少的情况下比较有优势，稳定；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候。