算法
算法，排序

排序算法

十种常见的排序算法可分为比较类排序和非比较类排序。比较类排序通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序；非比较类排序不通过比较来决定元素间的相对次序，可以突破基于比较排序的时间下界，也称为线性时间非比较类排序。

排序算法分类

算法类比

排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
冒泡排序 O(n^2) O(n^2) O(n) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
快速排序 O(nlog2^n) O(n^2) O(nlog2^n) O(nlog2^n) 不稳定
插入排序 O(n^2) O(n^2) O(n) O(1) 稳定
希尔排序 O(n^1.3) O(n^2) O(n) O(1) 不稳定
堆排序 O(nlog2^n) O(nlog2^n) O(nlog2^n) O(1) 不稳定
归并排序 O(nlog2^n) O(nlog2^n) O(nlog2^n) O(n) 稳定
计数排序 O(n + k) O(n + k) O(n + k) O(n + k) 稳定
桶排序 O(n + k) O(n^2) O(n) O(n + k) 稳定
基数排序 O(n * k) O(n * k) O(n * k) O(n + k) 稳定

冒泡排序

比较两个相邻的元素，将值大或者小的的元素交换到一边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void bubblerSort(Integer[] arr) {
    boolean flag = true;
    for (int i = 0; i < arr.length && flag; i++) {
        flag = false;
        for (int j = arr.length - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = true;
            }
        }
    }
}

选择排序

在待排序的一组数据中，选出最小（最大）的一个数与第一个位置的数交换，然后在剩下的数中，再找最小（最大）的数与第二个位置的数交换位置，依次类推，直到第N-1个元素与第N个元素交换位置，选择排序结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void selectSort(Integer[] arr) {
    int index;
    for (int i = 0; i < arr.length; i++) {
        index = i;
        for (int k = i + 1; k < arr.length; k++) {
            if (arr[index] > arr[k]) {
                index = k;
            }
        }
        if (i != index) {
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

快速排序

随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，比基准小的交换到左边，比基准大的交换到右边，交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void quickSort(Integer[] arr, int left, int right) {
    if (left < right) {
        int dl = left, dr = right, pivot = arr[left];
        while (dl < dr) {
            while (dl < dr && arr[dr] > pivot)
                dr--;
            if (dl < dr)
                arr[dl++] = arr[dr];
            while (dl < dr && arr[dl] < pivot)
                dl++;
            if (dl < dr)
                arr[dr--] = arr[dl];
        }
        arr[dl] = pivot;
        quickSort(arr, left, dl - 1);
        quickSort(arr, dl + 1, right);
    }
}

插入排序

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-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
public void insertSort(Integer[] arr) {
    int j, k;
    for (int i = 1; i < arr.length; i++) {
        for (j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                break;
            }
        }
        if (j != i - 1) {
            int temp = arr[i];
            for (k = i - 1; k > j; k--) {
                arr[k + 1] = arr[k];
            }
            arr[k + 1] = temp;
        }
    }
}

// 简化版
public void insertSort(Integer[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int value = nums[i];
        for (int j = i -1; j >= 0; j--) {
            if (value < nums[j]) {
                nums[j + 1] = nums[j];
            } else {
                break;
            }
            nums[j] = value;
        }
    }
}

希尔排序

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序。实质上是一种分组插入方法。

对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void shellSort(Integer[] arr) {
    int i, j, gap;
    for (gap = arr.length / 2; gap > 0; gap /= 2) {
        for (i = 0; i < gap; i++) {
            for (j = i + gap; j < arr.length; j += gap) {
                if (arr[j] < arr[j - gap]) {
                    int temp = arr[j];
                    int k = j - gap;
                    while (k >= 0 && arr[k] > temp) {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    }
                    arr[k + gap] = temp;
                }
            }
        }
    }
}

堆排序

堆排序是利用完全二叉树的特性，堆树又分为大顶堆和小顶堆。数组是完全二叉树最佳存储结构，因为完全二叉树有特殊的属性，可直接利用数组下标表示左右节点，数组下标为K的元素对应的完全二叉树中左右子节点在数组中的位置分别为2*K + 1、2*K+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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class HeapSort {
    public void heapSortAsc(Integer[] arr) {
        int len = arr.length;
        // len / 2 - 1表示的是从完全二叉数中最后一个元素的父节点开始堆化
        for (int start = len / 2 - 1; start >= 0; start--) {
            maxHeapDown(arr, start, len);  // 将树中最大的元素排到堆顶
        }
        // 上面的循环只是将最大的元素排到了堆顶，但是整棵树即数组中的元素不是有序的
        // 每一次将对顶的元素即最大的元素，和未排序的最后一个元素交换，再进行一次堆化，这样就将数据从小到大排序了
        for (int index = len - 1; index > 0; index--) {
            int temp = arr[0];
            arr[0] = arr[index];
            arr[index] = temp;
            maxHeapDown(arr, 0, index); // len~i已经排好序了
        }
    }
    /**
     * 将完全二叉树中最大的元素放到堆顶，end表示最多建到的点
     */
    public void maxHeapDown(Integer[] arr, int start, int end) {
        int parent = start;
        int left = parent * 2 + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int max = left; // max表示左右节点大的那一个在数组中的位置
            if (left + 1 < end && arr[left] < arr[left + 1]) { // 比较左右节点和父节点的大小
                max = left + 1; // 若右节点比左节点大，则将父节点和右节点交换
            }
            // 若左节点比右节点大，则将父节点和左节点交换
            if (arr[parent] > arr[max]) { // 若父节点大于子节点中最大的那一个，则退出
                return;
            } else { // 若父节点小于子节点中最大的那一个，则交换
                int tmp = arr[parent];
                arr[parent] = arr[max];
                arr[max] = tmp;
                parent = max;   // 还原指针，交换数据后，max指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
                left = parent * 2 + 1;  // 找到之前左右节点大的节点的左子节点在数组中的索引位置
            }
        }
    }
    public void heapSortDesc(Integer[] arr) {
        int len = arr.length;
        for (int start = len / 2 - 1; start >= 0; start--) {
            minHeapDown(arr, start, len);
        }

        for (int index = len - 1; index > 0; index--) {
            int tmp = arr[0];
            arr[0] = arr[index];
            arr[index] = tmp;
            minHeapDown(arr, 0, index);
        }
    }
   /**
     * 将完全二叉树中最小的元素放到堆顶，end表示最多建到的点
     */
    public void minHeapDown(Integer[] arr, int start, int end) {
        int parent = start;
        int left = 2 * start + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int min = left; // min表示左右节点小的那一个在数组中的位置
            if (left + 1 < end && arr[left] > arr[left + 1]) {
                min = left + 1;
            }
            if (arr[min] > arr[parent]) {  // 比较左右节点中小的那一个和父节点的大小
                break;  // 若小的那个节点都比父节点大，说明不需要再遍历了
            }
            int tmp = arr[min];
            arr[min] = arr[parent];
            arr[parent] = tmp;
            parent = min;   // 还原指针，交换数据后，min指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
            left = 2 * parent + 1;  // 找到之前左右节点小的节点的左子节点在数组中的索引位置
        }
    }
    @Test
    public void InsertSortTest() {
        {
            Integer[] arr = new Integer[]{8, 6, 4, 9, 74, 25, 1, 3, 5, 28, 35, 0, 22, 2, 7, 10, 26, 29};
            heapSortAsc(arr);
            System.err.println(" after:" + Arrays.asList(arr));
        }
        {
            Integer[] arr = new Integer[]{8, 6, 4, 9, 74, 25, 1, 3, 5, 28, 35, 0, 22, 2, 7, 10, 26, 29};
            heapSortDesc(arr);
            System.err.println(" after:" + Arrays.asList(arr));
        }
    }
}

归并排序

将两个的有序数列合并成一个有序数列，归并排序包括从上往下和从下往上两种方式。

从下往上：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。

从上往下：它与从下往上在排序上是反方向的，它基本包括3步：

  • 分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2
  • 求解：递归对两个子区间a[low...mid]和a[mid+1...high]归并排序。递归终结条件是子区间长度为1
  • 合并：将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]

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
public void mergeSortUp2Down(Integer[] arr, int start, int end) {
    if (arr == null || start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    mergeSortUp2Down(arr, start, mid);
    mergeSortUp2Down(arr, mid + 1, end);

    merge(arr, start, mid, end);
}

public void mergeSortDown2Up(Integer[] arr, int len) {
    if (arr == null || len < 0) {
        return;
    }
    for (int n = 1; n < len; n *= 2) {
        mergeGroups(arr, len, n);
    }
}

void mergeGroups(Integer[] arr, int len, int gap) {
    int i;
    for (i = 0; i + 2 * gap - 1 < len; i += 2 * gap) {
        merge(arr, i, i + gap - 1, i + 2 * gap - 1);
    }
    if (i + gap - 1 < len - 1) {
        merge(arr, i, i + gap - 1, len - 1);
    }
}

public void merge(Integer[] arr, int start, int mid, int end) {
    int[] temp = new int[end - start + 1];
    int i = start;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= end) {
        temp[k++] = arr[j++];
    }
    for (i = 0; i < k; i++) {
        arr[start + i] = temp[i];
    }
}

桶排序

将数组分到有限数量的桶子里。数组arr数据范围为[0, max)，创建容量为max的桶数组buckets，遍历数组arr将其值作为数组下标，再遍历桶数组得到有序数组。

1
2
3
4
5
6
7
8
9
10
11
public void bucketSort(Integer[] arr, int n, int max) {
    int[] buckets = new int[max];
    for (int index = 0; index < n; index++) {
        buckets[arr[index]]++;
    }
    for (int bucketIndex = 0, arrIndex = 0; bucketIndex < max; bucketIndex++) {
        while (buckets[bucketIndex]-- > 0) {
            arr[arrIndex++] = bucketIndex;
        }
    }
}

基数排序

基数排序是桶排序的扩展，将整数按位数切割成不同的数字，然后按每个位数分别比较。将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

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 void radixSort(Integer[] arr) {
    int max = getMax(arr);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, exp);
    }
}

public void countSort(Integer[] arr, int exp) {
    int[] output = new int[arr.length];
    int[] buckets = new int[10];
    for (int index = 0; index < arr.length; index++) {
        buckets[arr[index] / exp % 10]++;
    }

    for (int index = 1; index < 10; index++) {
        buckets[index] += buckets[index - 1];
    }

    for (int index = arr.length - 1; index >= 0; index--) {
        output[buckets[arr[index] / exp % 10] - 1] = arr[index];
        buckets[arr[index] / exp % 10]--;
    }

    for (int index = 0; index < arr.length; index++) {
        arr[index] = output[index];
    }
}

public int getMax(Integer[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}