排序算法分类

排序算法分为内排序和外排序。所有数据已经读入内存，排序过程中无需对磁盘进行读写称为内排序。内存中无法保存全部数据，需要用到外存的称为外排序。文章讲的排序都属于内排序，下面以从小到大排序举例进行描述。

内排序算法可以分为以下五类：

  • 插入排序：直接插入排序、二分法插入排序，希尔排序
  • 选择排序：简单选择排序、堆排序
  • 交换排序：冒泡排序、快速排序
  • 归并排序
  • 基数排序

算法理解与实现

插入排序

算法思想：插入排序分为已排好序的部分，待插入排序的当前元素，要解决的问题即是寻找到合适位置进行插入。即每次将一个待排序的记录，按照顺序码大小插入到有序序列的合适位置，直到全部插入排序完成。
关键点：找到已经排好序的序列中合适插入位置。

直接插入排序

算法思想：

代码：

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
38
39
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/3.
 */
public class InsertSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 1.插入排序の直接插入排序
    public static void directInsertSort(int[] numbers) {
        int temp = numbers[0];
        int j = 0;

        for (int i = 0; i < numbers.length; i++) {
            temp = numbers[i];
            for (j = i; j > 0 && temp < numbers[j-1]; j--) {
                numbers[j] = numbers[j-1];
            }
            numbers[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{9, 5, -11, 3, 1, 9};

        directInsertSort(numbers);

        print(numbers);
    }
}

二分法插入排序

算法思想：
同样地，二插入排序也分为已排好序的部分，待插入排序的元素temp，二分的目的是比较减少次数。
如果待插入元素temp大于已排好序的下标为mid的元素，表明应该插入mid右边，则更新left为mid + 1；否则，表明应该插入mid的左边，更新right为mid - 1.

代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/3.
 */
public class InsertSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 2.插入排序の二分插入排序
    public static void binInsertSort(int[] numbers) {
        int temp = numbers[0];
        int left = 0;
        int right = 0;
        int mid = 0;

        for (int i = 0; i < numbers.length; i++) {
            temp = numbers[i];
            left = 0;   // 固定左边
            right = i - 1; // 有序序列的右边界
            // temp是待插入元素，每次插入时，从left到right的数组序列已经有序，循环找到插入位置
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < numbers[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 判断需要移动多少个位置,left 等于 right
            for (int j = i - 1; j >= left; j--) {
                numbers[j + 1] = numbers[j];
            }
            numbers[left] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{9, 5, -11, 3, 1, 9};

        binInsertSort(numbers);

        print(numbers);
    }
}

希尔排序

算法思想：
将待排序的序列分为若干个组分别进行直接插入排序，带整个序列的记录基本有序时，对全体序列进行直接插入排序。
具体来说，划分组依据步长increment；组（列）排序使用插入排序，只是相邻元素下标关系为一个步长increment；步长为1时，即直接插入排序。

代码：

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
38
39
40
41
42
43
44
45
46
47
48
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/3.
 */
public class InsertSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 3.插入排序の希尔排序
    public static void shellSort(int[] numbers) {
        int temp = 0;
        int j = 0;

        // 设置步长,每次为原来的一半
        for (int increment = numbers.length / 2; increment > 0; increment /= 2) {
            // 按步长划分列(组)
            for (int i = increment; i < numbers.length; i++) {
                temp = numbers[i];
                // 对同一列中的元素进行插入排序
                for (j = i; j >= increment; j -= increment) {
                    if (temp < numbers[j - increment]) { // 决定从小到大排序
                        numbers[j] = numbers[j - increment];
                    } else {
                        break;
                    }
                }
                numbers[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{9, 5, -11, 3, 1, 9};

        shellSort(numbers);

        print(numbers);
    }
}

选择排序

算法思想：每趟从待排序记录序列中选择最小的元素放在已排序表的最前面，直至全部排完。
关键点：在待排序序列中找到最小的元素（下标）。

直接选择排序

算法思想：
每次找出未排序部分最小序列最小元素的下标，然后将其与第i个（第i趟）的元素交换。即第一次找出最大的元素下标，与第一个元素做交换；第二次找到剩下未排序的最大元素，与第二个位置的元素做交换，直到排序完成。

代码：

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
38
39
40
41
42
43
44
45
46
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/3.
 */
public class SelectSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 1.选择排序の简单选择排序
    public static void simpleSelectSort(int[] numbers) {
        int temp;

        for (int i = 0; i < numbers.length - 1; i++) {
            int k = i;
            // 有比当前numbers[i]更小的数，那么记录其下标j
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[k] > numbers[j]) {
                    k = j;
                }
            }
            // 当发现k ！= i 即有比当前numbers[i]更小的数，交换； k == i 时，那么自己和自己交换不影响结果,因此if语句可以省去
            //if (k != i) {
                temp = numbers[i];
                numbers[i] = numbers[k];
                numbers[k] = temp;
            //}
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{-13, 5, -11, 11, 4, 9, 3, 1, -90, 12};

        simpleSelectSort(numbers);

        print(numbers);
    }
}

堆排序

算法思想：
堆非官方定义：满足完全二叉树；大顶堆每个节点的都比其左右子节点大。
堆排序把要排序的序列看作一棵顺序存储的二叉树，调整存储顺序，使之成为一个堆。
堆排序分为两步：a.构建堆;b.根元素与最后一个元素作交换，剔除最后一个元素。
其中构建堆是大顶堆还是小顶堆决定升降序排列。

代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/3.
 */
public class SelectSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 2.1选择排序の堆排序
    public static void heapSort(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            buildMaxHeap(numbers, numbers.length - 1 - i);
            swap(numbers, 0, numbers.length - 1 - i);
        }
    }

    //----------------------------------
    // 2.2构建堆
    // 对numbers数组从0到lastIndex建大顶堆
    public static void buildMaxHeap(int[] numbers, int lastIndex) {
        // 从最后一个节点（下标为lastIndex）的父节点开始
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            int fatherIndex = i;    // 保存当前节点
            int biggerIndex = 2 * fatherIndex + 1;  // 求出其左子节点

            // 如果父节点fatherIndex的子节点存在，需使得父节点最大
            while (biggerIndex <= lastIndex) {
                // biggerIndex < lastIndex表示当前节点存在右子节点biggerIndex+1
                if (biggerIndex < lastIndex) {
                    // 记录fatherIndex的子节点中较大数的对应下标
                    if (numbers[biggerIndex] < numbers[biggerIndex + 1]) {
                        biggerIndex++;
                    }
                }
                // 比较父节点与其较大子节点的值
                if (numbers[fatherIndex] < numbers[biggerIndex]) {
                    swap(numbers, fatherIndex, biggerIndex);
                    // 将biggerIndex赋予fatherIndex，while循环保证交换后biggerIndex位置的值大于其左右子节点的值
                    fatherIndex = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }

    //----------------------------------
    // 2.3交换数据
    public static void swap(int[] numbers, int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{-13, 5, -11, 11, 4, 9, 3, 1, -90, 12};

        heapSort(numbers);

        print(numbers);
    }
}

交换排序

算法思想：两两比较，交换元素的排序算法
关键点：何时进行交换。

冒泡排序

算法思想：
对于待排序部分，自上而下的相邻元素两两比较，如果顺序与要求相反，则交换两个元素，则大的元素往下沉，轻的元素往上冒，冒泡就是这么的形象简单。

代码：

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
38
39
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/4.
 */
public class ExchangeSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //----------------------------------
    // 1.交换排序の冒泡排序
    public static void bubbleSort(int[] numbers) {
        int temp;
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{90, 5, -11, 11, 4, 3, 3, 1, -90, 12};

        bubbleSort(numbers);

        print(numbers);
    }
}

快速排序

算法思想：
划分方法partition选择一个基准元素，通过一趟扫描，找到基准元素应该在的位置，将待排序序列分为大于等于基准元素的部分，小于基准元素的部分。接下来分别对两部分进行同样的方式划分，直至排序完成。Hoarse划分和三路划分。

代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/4.
 */
public class ExchangeSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //----------------------------------
    // 2.1交换排序の快速排序
    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(numbers, low, high);
            quickSort(numbers, low, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, high);
        }
    }

    //----------------------------------
    // 2.2三路划分,优化
    public static int partition(int[] numbers, int low, int high, int pivotIndex) {
        int pivotValue = numbers[pivotIndex];
        int storeIndex = low;

        swap(numbers, pivotIndex, high);
        for (int i = low; i < high; i++)
            if (numbers[i] <= pivotValue) {
                swap(numbers, i, storeIndex);
                ++storeIndex;
            }
        swap(numbers, storeIndex, high);
        return storeIndex;
    }

    //----------------------------------
    //Hoarse划分
    public static int partition(int[] numbers, int low, int hight) {
        int pivot = numbers[low];

        while (low < hight) {
            while (low < hight && numbers[hight] >= pivot) {
                hight--;
            }
            numbers[low] = numbers[hight];
            while (low < hight && numbers[low] < pivot) {
                low++;
            }
            numbers[hight] = numbers[low];
        }
        numbers[low] = pivot;
        return low;
    }

    //----------------------------------
    // 2.3交换数据
    public static void swap(int[] numbers, int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    //----------------------------------
    // 2.4调用
    public static void quick(int[] numbers) {
        if (numbers.length > 0) {
            quickSort(numbers, 0, numbers.length - 1);
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{90, 5, -11, 11, 4, 3, 3, 1, -90, 12};

        quick(numbers);

        print(numbers);
    }
}

归并排序

算法思想：
将两个或两个以上的有序表合并成一个新的有序表。先将序列分为若干个子序列，这若干个子序列又是有序的，然后将其合并为一个整体有序序列。
这里划分直接以1/2划分，然后再分别对两部分进行归并排序，最后调用将两个两部分排好序的子序列合并，如此递归至排序完成。

代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/4.
 */
public class MergeSort {
    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 1.归并排序
    public static void mergeSort(int[] numbers, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(numbers, low, mid);
            mergeSort(numbers, mid + 1, high);
            merge(numbers, low, mid, high);
        }
    }

    //-----------------------------------
    // 合并数组
    public static void merge(int[] numbers, int originLow, int middle, int originHigh) {
        int[] tempNumbers = new int[originHigh - originLow + 1];
        int low = originLow;
        int high = originHigh;
        int mid = middle + 1;
        int third = 0;

        // 将小的先放入新数组
        while (low <= middle && mid <= high) {
            if (numbers[low] <= numbers[mid]) {
                tempNumbers[third++] = numbers[low++];
            } else {
                tempNumbers[third++] = numbers[mid++];
            }
        }
        // 左边有剩余，添加到数组中
        while (low <= middle) {
            tempNumbers[third++] = numbers[low++];
        }
        // 右边有剩余，添加到数组中
        while (mid <= high) {
            tempNumbers[third++] = numbers[mid++];
        }

        // 新数组元素复制到原数组对应位置
        for (int i = 0; i < tempNumbers.length; i++) {
            numbers[originLow + i] = tempNumbers[i];
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{-13, 5, -11, 11, 4, 9, 3, 1, -90, 12};

        mergeSort(numbers, 0, numbers.length - 1);

        print(numbers);
    }
}

基数排序

算法思想：
以前比较两个正整数的大小是这样的，如果一个数的位数比另一个多，则这个数就大。如果位数相同，那么按位数递减依次比较大小，哪个数在这一位上更大则停止比较，得到这个数较大的结果。而我们也可以从个位到高位进行比较。

那么怎么保存每次按照数的某一位比较得出的排序结果呢？数的每一位是由0-9中的一个构成的，如果按照某一位进行比较，最多会是，该位数都相等，那么共有n个数的数组会排成1列共n个，故需要用二维数组bucket[10][n]来存放排序结果。
[72 25 18 90 35 25 12 81 97 11] 十个数进行基数排序

按个位排序：

0 1 2 3 4 5 6 7 8 9
90 11 72 25 97 18
81 12 35
25

按照从0到9元素顺序，桶内先进先出顺序，排序得到下列数组
[90 11 81 72 12 25 35 25 97 18]

按十位排序：

0 1 2 3 4 5 6 7 8 9
11 25 35 72 81 90
12 25 97
18

按同样方法，排序得到下面有序序列
[11 12 18 25 25 72 81 90 97]

代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package main.sort;

/**
 * Created by LuoWenqing on 2017/4/4.
 */
public class RadixSort {

    //-----------------------------------
    // 打印函数
    public static void print(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
    }

    //-----------------------------------
    // 基数排序
    public static void radixSort(int[] numbers) {
        int n = 1;
        int k = 0;
        int len = numbers.length;

        int max = numbers[0];
        for (int i = 0; i < len; i++) {
            if (max < numbers[i]) {
                max = numbers[i];
            }
        }

        // 计算出需要比较到位数
        int times = 0;
        while (max != 0) {
            times++;
            max /= 10;
        }

        // 二维数组的行为按0-9形成的桶，len取number.length是保证桶能够放下所有的数字
        int[][] bucket = new int[10][len];
        // 用于保存每个桶里元素的个数
        int[] order = new int[10];
        while (n <= times) {
            for (int num : numbers) {
                int digit = num / (int)Math.pow(10, n - 1) % 10;
                bucket[digit][order[digit]] = num;
                order[digit]++;
            }

            for (int i = 0; i < len; i++) {
                // 如果桶里有数据，从上到下遍该桶历并保存到原数组中
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        numbers[k] = bucket[i][j];
                        k++;
                    }
                }
                order[i] = 0; //将桶里计数器置0，用于下一位排序
            }
            n++;
            k = 0;
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{5, 411, 11, 4, 9, 3, 1, 90, 12};

        radixSort(numbers);

        print(numbers);
    }
}

总结

类别 排序算法 最坏时间复杂度 最好时间复杂度 平均时间复杂度 稳定性
插入 直接插入排序 O(n2) O(n) O(n2) 稳定
插入 二分法插入排序 O(n2) O(log2n) O(n2) 稳定
插入 希尔排序 O(n2) O(n) O(n1.3) 不稳定
选择 简单选择排序 O(n2) O(n2) O(n2) 不稳定
选择 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) 不稳定
交换 冒泡排序 O(n2) O(n2) O(n2) 稳定
交换 快速排序 O(n2) O(nlog2n) O(nlog2n) 不稳定
归并 二路归并排序 O(nlog2n) O(nlog2n) O(nlog2n) 稳定
基数 基数排序 O(d(r+n)) O(d(n+rd)) O(rd+n) 稳定

其中基数排序的r表示关键字基数，d表示长度，n表示关键字个数。

声明：本站所有文章均为原创或翻译，遵循署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议，如需转载请确保您对该协议有足够了解，并附上作者名 (Tsukasa) 及原文地址