数据结构——排序

发表于 更新于 本文字数： 1.8k 阅读时长 ≈ 7 分钟
时间复杂度 空间复杂度 稳定性
插入排序 O(n2) O(1) 稳定
选择排序 O(n2) O(1) 不稳定
冒泡排序 O(n2) O(1) 稳定
归并排序 O(nLog2n) O(1) 稳定
快速排序 O(nLog2n) O(nLog2n) 不稳定
堆排序 O(nLog2n) (1) 不稳定
希尔排序 O(n1.5) O(1) 不稳定
桶排序 O(n) O(n) 不稳定

插入排序

直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。
因此，从上面的描述中我们可以发现，直接插入排序可以用两个循环完成：

  1. 第一层循环：遍历待比较的所有数组元素
  2. 第二层循环：将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。找到它应该在有序队列的位置之后，将二者交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void insertSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

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

选择排序

选择排序是一直非常直观的选择办法，它每次寻找当前未排序列表中最大（小）的数，放在队列的首（尾），然后从未排序的队列中取出，再找剩下队列的最值。经过n-1次循环排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

    for (int i = 0; i < num.length - 1; i++) {
        int min = i, temp;
        for (int j = num.length - 1; j > i; j--) {
            if (num[j] < num[min]) {
            min = j;
            }
        }
        temp = num[min];
        num[min] = num[i];
        num[i] = temp;
    }
}

冒泡排序

冒泡排序是一种简单的排序算法，他依次的检查要排序的数列，每次比较两个数，如果他们顺序有误就把他们调换过来，经过依次走访，有一个最大（最小）的数据就会落座，经过n-1次循环排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void bubbleSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

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

归并排序

归并排序是基于归并操作的一种排序算法，即将两个已经排好序的数组合并成一个序列的操作。
对于使用时，使用了分治方法，即将数组递归分割成两两等分，比较再进行合并。使用时需要注意边界数据处理。
每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。
迭代方法即将步长从1增加至 n.length / 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
public static void mergeSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

    merge(num, 0, num.length - 1, new int[num.length]);
}

private static void merge(int[] num, int start, int end, int[] temp) {
    if (start < end) {
        int mid = (end + start) / 2;
        merge(num, start, mid, temp);
        merge(num, mid + 1, end, temp);
        mergeArray(num, start, mid, end, temp);
    }
}

private static void mergeArray(int[] num, int start, int mid, int end, int[] temp) {
    int i = start, j = mid + 1;
    int k = 0;

    while (i <= mid && j <= end) {
        if (num[i] < num[j])
            temp[k++] = num[i++];
        else if (num[i] == num[j])
            temp[k++] = num[i++];
        else
            temp[k++] = num[j++];
    }

    while (i <= mid)
        temp[k++] = num[i++];

    while (j <= end)
        temp[k++] = num[j++];

    for (i = 0; i < k; i++)
        num[start + i] = temp[i];
}

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

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
public static void quickSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

    _quickSort(num, 0, num.length - 1);
}

private static void _quickSort(int[] num, int start, int end) {
    if (start >= end)
        return;

    int t = num[start]，i = start, j = end;

    while (j != i) {
        while (j > i && num[j] >= t)
            j--;

        while (j > i && num[i] <= t)
            i++;

        if (i < j) {
            int temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    int temp = num[i];
    num[i] = num[start];
    num[start] = temp;

    _quickSort(num, start, i - 1);
    _quickSort(num, i + 1, end);
}

堆排序

堆排序是根据堆的原理——堆是一个完全二叉树，切如大顶堆，每个父节点的值都大于他的子节点，当一个已经构造完成的大顶堆，每次将堆顶的数据与最后一个值调换，再将剩余的数据重新排列成一个大顶堆，重复这个过程，就构排序完成了。则问题变成了构造大顶堆及调换数字再构造的过程。

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
public static void heapSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

    for (int i = num.length / 2 - 1; i >= 0; i--) {
        //构造大顶堆，初始化
        buildMaxHeap(num, i, num.length - 1);
    }

    for (int i = num.length - 1; i > 0; i--) {
        //交换堆顶与最后一位字符的顺序
        num[i] = num[i] + num[0];
        num[0] = num[i] - num[0];
        num[i] = num[i] - num[0];

        //对剩下的数据继续构造大顶堆
        buildMaxHeap(num, 0, i - 1);
    }
}

private static void buildMaxHeap(int[] num, int start, int end) {
    //father 为要构造的分支的父节点，son为父节点的左子树
    int father = start, son = start * 2 + 1;
    //son 为寻找最大数值的指针，从左子树的根节点开始，到末尾为止
    while (son <= end) {
        //如果当前指针不如根节点大，则指向右节点
        if (son + 1 < end && num[son] < num[son + 1]) {
            son++;
        }
        if (num[father] <= num[son]) {
            //若根节点比左右子树都大，直接返回，否则交换根节点与左右子树的值,因为比较时是从最后一个非叶子节点开始的，所以直接比较根节点与左右子树就可以
            num[father] = num[father] + num[son];
            num[son] = num[father] - num[son];
            num[father] = num[father] - num[son];
        }
        return;
    }
}

希尔排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。
步骤为

  • 先按照步长为一遍数组的长度，分组，进行插入排序；
  • 缩小步长为刚才的一半，继续分组排序；
  • 直到步长为1时经过一遍排序完成；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void shellSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

    //步长为初始数组长度的一半，最短为1
    for (int gap = num.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < num.length; i++) {
            int j = i;
            //冒泡排序
            while (j - gap > 0 && num[j] < num[j - gap]) {
                num[j] = num[j] + num[j - gap];
                num[j - gap] = num[j] - num[j - gap];
                num[j] = num[j] - num[j - gap];
                j = j - gap;
            }
        }
    }
}

桶排序

桶排序是一种以空间换时间的排序方法，事先要知道待排序数组的范围，申请一个空间为待排序数组最大值减去最小值的记录数组，然后依次遍历数组，出现某个数则标记相应位置+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
public static void bucketSort(int[] num) {
    if (num == null || num.length < 2) {
        return;
    }

    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    for (int i : num) {
        max = Math.max(max, i);
        min = Math.min(min, i);
    }

    int[] bucket = new int[max - min + 1];

    for (int i : num) {
        bucket[i - min]++;
    }

    int index = 0;
    for (int i = 0; i < bucket.length; i++) {
        while (bucket[i]-- > 0) {
            num[index++] = i + 1;
        }
    }
}