排序算法总结

总结

博客中所提到的所有排序算法均以从小到大排序为例。
回顾并实现基本的排序算法。
HTTP-图示

主函数

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
import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {
        int[] arr = new int[20];
        int index = 0;
        for (int i = 20; i > 0; i--)
            arr[index++] = i;
        System.out.println("排序前，数组为");
        System.out.println(Arrays.toString(arr));
        arr = bucketSort(arr);
        System.out.println("排序后，数组为");
        System.out.println(Arrays.toString(arr));
    }

    // 交换数组中元素的位置
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 输出数组
    public static void printArray(int[] arr, int begin, int end) {
        for (int i = 0; i < arr.length; i++) {
            if (i == 0)
                System.out.print("[");
            System.out.print(arr[i] + ",");
            if (i == arr.length - 1)
                System.out.print("]");
        }
        System.out.println();
    }
}

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 1.直接插入排序
public static int[] insertionSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    for (int i = 0; i < arr.length - 1; i++) {
        // 将 i+1 位置的数插入 0 到 i 之间的数组，从后往前遍历
        // cur 指 i+1 的位置元素，pre 指 0 到 i 中依次向前遍历的指针
        int cur = arr[i + 1];
        int pre = i;
        while (pre >= 0 && cur < arr[pre]) {
            arr[pre + 1] = arr[pre];
            pre--;
        }
        // 最后将原来 i+1 位置的元素放入现在 0 到 i+1 之间数组中正确的位置上
        // pre+1 是因为刚才循环结束时又自减了一次
        arr[pre + 1] = cur;
    }
    return arr;
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 2.希尔排序
// 希尔排序最重要的变量就是 gap
public static int[] shellSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    int gap = arr.length / 2, cur;
    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            // 将 pre+gap 位置的数插入 0 到 pre 之间“同组”的数组，从后往前遍历
            // cur 指 pre+gap 的位置元素
            cur = arr[i];
            int pre = i - gap;
            while (pre >= 0 && arr[pre] > cur) {
                arr[pre + gap] = arr[pre];
                pre -= gap;
            }
            arr[pre + gap] = cur;
        }
        gap /= 2;
    }
    return arr;
}

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 // 3.简单选择排序
public static int[] selectionSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    for (int i = 0; i < arr.length - 1; i++) {
        // 每一轮挑出一个最小的元素，依次与不断增长的 i 位置的元素交换
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        if (minIndex != i)
            swap(arr, minIndex, i);
    }
    return arr;
}

堆排序

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
// 4.堆排序
public static int[] heapSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    while (heapSize > 0) {
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);
    }
    return arr;
}

public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

public static void heapify(int[] arr, int index, int size) {
    int left = index * 2 + 1;
    while (left < size) {
        int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 5.冒泡排序
public static int[] bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

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

快速排序

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
// 6.快速排序
public static int[] quickSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    quickSort(arr, 0, arr.length - 1);
    return arr;
}

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int mid = partition(arr, l, r);
        quickSort(arr, l, mid - 1);
        quickSort(arr, mid + 1, r);
    }
}

public static int partition(int[] arr, int l, int r) {
    int i = l, j = r, tmp = arr[l];
    while (i < j) {
        while (i < j && arr[j] >= tmp)
            j--;
        arr[i] = arr[j];

        while (i < j && arr[i] < tmp)
            i++;
        arr[j] = arr[i];
    }
    arr[i] = tmp;

    return 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
// 7.归并排序
public static int[] mergeSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    mergeSort(arr, 0, arr.length - 1);
    return arr;
}

public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

public static void merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    while (p1 <= m && p2 <= r) {
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[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
47
48
49
50
51
52
53
54
55
// 8.基数排序
public static int[] radixSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    radixSort(arr, 0, arr.length - 1, 2);
    return arr;
}

public static int maxbits(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int res = 0;
    while (max != 0) {
        res++;
        max /= 10;
    }
    return res;
}

public static void radixSort(int[] arr, int begin, int end, int digit) {
    final int radix = 10;
    int i = 0, j = 0;
    int[] count = new int[radix];
    int[] bucket = new int[end - begin + 1];

    for (int d = 1; d <= digit; d++) {
        for (i = 0; i < radix; i++)
            count[i] = 0;

        for (i = begin; i <= end; i++) {
            j = getDigit(arr[i], d);
            count[j]++;
        }

        for (i = 1; i < radix; i++)
            count[i] = count[i] + count[i - 1];

        for (i = end; i >= begin; i--) {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }

        for (i = begin, j = 0; i <= end; i++, j++) {
            arr[i] = bucket[j];
        }
    }
}

public static int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 9.计数排序
public static int[] countSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }

    int[] bucket = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }

    int index = 0;
    for (int j = 0; j < bucket.length; j++) {
        while (bucket[j]-- > 0) {
            arr[index++] = j;
        }
    }
    return arr;
}

桶排序

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
// 10.桶排序
public static int[] bucketSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return arr;

    int bucketSize = arr.length;
    int min = arr[0];
    int max = arr[0];
    for (int i = 0; i < bucketSize; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    int bucketCount = bucket(max, min, bucketSize) + 1;
    int[][] buckets = new int[bucketCount][0];

    // 利用映射函数将数据分配到各个桶中
    for (int i = 0; i < arr.length; i++) {
        int index = bucket(arr[i], min, bucketSize);
        buckets[index] = arrAppend(buckets[index], arr[i]);
    }

    int index = 0;
    for (int[] bucket : buckets) {
        if (bucket.length <= 0) {
            continue;
        }
        // 对每个桶进行排序，这里使用了插入排序
        bucket = insertionSort(bucket);
        for (int value : bucket) {
            arr[index++] = value;
        }
    }
    return arr;
}

public static int bucket(long num, long min, long bucketSize) {
    return (int) ((num - min) * bucketSize);
}

public static int[] arrAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}

参考资料

https://twocups.cn/index.php/2020/02/01/17/
https://github.com/hustcc/JS-Sorting-Algorithm

#算法
排序算法总结
https://lcf163.github.io/2020/07/06/排序算法总结/
作者
乘风的小站
发布于
2020年7月6日
许可协议