排序算法毋庸置疑，是最重要最重要的基础算法，真正的实际应用中，往往是几种排序算法的组合，因为没有完美的算法，只有适合的算法。学好算法的第一步应该是熟练手写出基本的排序算法，本文应该被放在一篇文章，但是命运的巧合，我还是选择了递归。因为排序算法就摆在那，思想比较清晰，理解上没有难度，但是递归也摆在那，好像简单但是又无从下手。本文先从复杂度比较高但是比较简单的几种排序算法入手。这几种都是O(n^2)的时间复杂度。

1. 冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法的基本步骤：

  • 比较相邻的元素。如果第一个比第二个大(注意相等不要交换，所谓冒泡是稳定的排序)，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 重复步骤1~3，直到排序完成。

动态图：

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 冒泡排序
 */
public class BubbleSort {

    private static void bubble_sort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        /**
         * 冒泡排序整体思路：每一趟的比较，都会将最大的一个数排到最后面
         * 0。。。。。。。n-1   第一趟一直比较到最后一个，把最大的放到对后面
         * 0。。。。。n-2   第二趟比较的数组长度会减少一个，因为最大的已经确定了
         * 0。。。。n-3    第三趟比较的就再少两个，因为两个最大的已经确定了
         */
        for(int i=arr.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                //两两比较交换
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

2. 选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：不断地在未排序序列中找到最小元素，交换到数组的最前面。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 选择排序
 */
public class SelectSort {

    private static void select_sort(int[] arr){
        /**
         * 基本思想是：每一趟都将最小值的索引确定好，然后放到前
         * 所以每一趟结束之后，前面是已经排好序的
         */
        for(int i=0;i<arr.length;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            swap(arr,min,i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

3. 插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr= {3,1,54,32,23,3,6};
        insert_sort(arr);
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i] + " ");
        }
    }

    private static void insert_sort(int[] arr){
        /**
         * 插入排序主要思想是：每一趟都保证当前索引前的所有元素都小于当前索引
         * 比如【5,4,3,2,1】，那么第一趟是【4,5,3,2,1】，第二趟是【3,4,5,2,1】
         * 第三趟是【2,3,4,5,1】，第四趟是【1,2,3,4,5】
         *
         *
         * 其实这是优化后的方法，简单的插入排序是这样子的：
         *    for(int i=1;i<arr.length;i++){
         *        for(int j=i; j>0 && array[j-1]>array[j]; j--){
         *           swap(array, j, j-1);
         *        }
         *    }
         * 这里的优化是考虑到原始方法要不断地进行交换，其实是没有必要的，直接赋值就好了
         */
        for(int i=1;i<arr.length;i++){
            int tmp = arr[i];
            int j;
            for(j=i;j>0 && arr[j-1] > tmp ;j--){
                arr[j] = arr[j-1];
            }
            arr[j] = tmp;
        }
    }
}