Java-排序算法

发表于 更新于 分类于 本文字数： 1.3k 阅读时长 ≈ 5 分钟

冒泡排序

外层循环次数为集合元素数 - 1 (两两比较)[1]

内层循环每次 -1 (每次循环确定最末尾数)

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int idx = 0; idx < arr.length - 1 - i; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                int temp = arr[idx + 1];
                arr[idx + 1] = arr[idx];
                arr[idx] = temp;
            }
        }
    }
}

选择排序

默认首位数为最小，遍历后续元素，确定最小索引，交换数据[2]

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

插入排序

默认从二号元素开始，左侧元素为有序列[3]

遍历时若较左侧小的数，进行移动(类冒泡)，否则直接进入下次外循环 (较左侧最近数大，则较有序列所有数大)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertionSort(int[] a) {
    int cur = 0;
    int len = a.length;
    while (++cur < len) {
        if (a[cur] < a[cur - 1]) {
            int val = a[cur];
            int idx = cur;
            while (--idx >= 0 && val < a[idx]) {
                a[idx + 1] = a[idx];
            }
            a[idx + 1] = val;
        }
    }
}

希尔排序

一种改进的插入排序[4]

最外层循环为步长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort(int[] arr) {
    for (int step = arr.length >>> 1; step > 0; step >>>= 1) {
        for (int j = step; j < arr.length; j++) {
            for (int idx = j; idx > 0 && idx - step >= 0; idx -= step) {
                if (arr[idx] < arr[idx - step]) {
                    int temp = arr[idx - step];
                    arr[idx - step] = arr[idx];
                    arr[idx] = temp;
                } else {
                    break;
                }
            }
        }
    }
}

快速排序

首先确定一个基数，将大于/小于他的数置于其两侧，再对左右两侧集合进行递归[5]

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
public static void quickSort(int[] arr, int start, int end) {
    if (start + 1 > end) {
        return;
    }
    boolean isStartWithEnd = true;
    int left = start;
    int right = end;
    int meanVal = arr[start];
    while (true) {
        if (isStartWithEnd) {
            if (arr[end] >= meanVal) {
                end--;
            } else if (arr[end] < meanVal) {
                arr[start] = arr[end];
                start++;
                isStartWithEnd = false;
            }
        } else /* if (!isStartWithHigh) */ {
            if (arr[start] <= meanVal) {
                start++;
            } else if (arr[start] > meanVal) {
                arr[end] = arr[start];
                end--;
                isStartWithEnd = true;
            }
        }
        if (start == end) {
            arr[start] = meanVal;
            break;
        }
    }
    quickSort(arr, left, start - 1);
    quickSort(arr, start + 1, right);
}

归并排序

先进行递归，将列表进行拆分，首先从最小的切分集合进行排序，之后进行合并排序，最终合并排序为一个有序表[6]

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 mergeSort(int[] arr, int start, int end) {
    if (end <= start) {
        return;
    }
    int mid = (start + end) >>> 1;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    int left = start;
    int right = mid + 1;
    int idx = 0;
    int[] resArr = new int[end - start + 1];
    while (left <= mid && right <= end) {
        if (arr[left] <= arr[right]) {
            resArr[idx] = arr[left];
            left++;
        } else /* arr[left] > arr[right] */ {
            resArr[idx] = arr[right];
            right++;
        }
        idx++;
    }
    while (left <= mid || right <= end) {
        if (left <= mid) {
            resArr[idx] = arr[left];
            left++;
        } else /* right <= end */ {
            resArr[idx] = arr[right];
            right++;
        }
        idx++;
    }
    if (end - start + 1 >= 0) {
        System.arraycopy(resArr, 0, arr, start, end - start + 1);
    }
}

堆排序

构建堆 (此处是升序排序，所以选择大顶堆)[7]

  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
class HeapSort {
    public static void sort(int[] arr) {
        for (int i = arr.length >>> 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int j = arr.length - 1; j > 0; j--) {
            int tmp = arr[0];
            arr[0] = arr[j];
            arr[j] = tmp;
            adjustHeap(arr, 0, j);
        }
    }

    private static void adjustHeap(int[] arr, int cur, int len) {
        int tmp = arr[cur];
        // 若调整根节点，子节点需再调整 (idx = idx * 2 + 1)
        for (int idx = cur * 2 + 1; idx < len; idx = idx * 2 + 1) {
            // 判断 左/右子节点 中的最大子节点
            if (idx + 1 < len && arr[idx + 1] > arr[idx]) {
                idx++;
            }
            if (arr[idx] > tmp) {
                arr[cur] = arr[idx];
                cur = idx;
            } else {
                break;
            }
        }
        arr[cur] = tmp;
    }
}

基数排序

此处是最低位优先 (Least Significant Digit first，LSD) 法，从个位开始，对数组进行排序[8]

  1. 将对应位元素出现的次数存储在 buckets 中

  2. buckets[i] += buckets[i - 1] 将 bucket 的值变为对应最后一个元素的索引 (此时buckets 为一个有序索引桶)，每确定一个索引的元素将对应 bucket 的值 -1，将 bucket 存储的索引移动到对应的下一个索引

    (实际上是索引 + 1，因为默认没有元素的 bucket 的值为 0，之后从 bucket 中取得索引需要 -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 radixSort(int[] arr) {
    int max = arr[0];
    int exp;
    for (int num : arr) {
        if (num > max) {
            max = num;
        }
    }
    for (exp = 1; max / exp > 0; exp *= 10) {
        int[] tmpArr = new int[arr.length];
        int[] buckets = new int[10]; // 0 ~ 9
        for (int value : arr) {
            buckets[(value / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            buckets[i] += buckets[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            tmpArr[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
            buckets[(arr[i] / exp) % 10]--;
        }
        System.arraycopy(tmpArr, 0, arr, 0, arr.length);
    }
}

  1. Robert Sedgewick and Kevin Wayne, Algorithms, 4th Edition, Bubble.java, describes bubble sort as a stable sort using constant extra memory. ↩︎

  2. Sedgewick and Wayne, Algorithms, 4th Edition, §2.1 Elementary Sorts, covers selection sort as an elementary method that repeatedly selects the next item for the sorted prefix. ↩︎

  3. Sedgewick and Wayne, Algorithms, 4th Edition, §2.1 Elementary Sorts, presents insertion sort as maintaining a sorted prefix and inserting the next element into it. ↩︎

  4. Sedgewick and Wayne, Algorithms, 4th Edition, §2.1 Elementary Sorts, describes Shellsort as a variation of insertion sort over decreasing gap subsequences. ↩︎

  5. Introduction to Algorithms, 4th Edition presents quicksort as partitioning around a pivot and recursively sorting subarrays; its average behavior is good, while bad pivot choices can produce quadratic worst-case time. ↩︎

  6. Introduction to Algorithms, 4th Edition presents merge sort as recursively dividing input and merging sorted subarrays; array merge sort typically uses linear extra space and can be stable. ↩︎

  7. Introduction to Algorithms, 4th Edition presents heapsort as building a heap and repeatedly moving the maximum element to the end; it has O(n log n) worst-case time and constant auxiliary space in the usual array implementation. ↩︎

  8. Introduction to Algorithms, 4th Edition presents radix sort as a non-comparison sort that processes digit positions with a stable intermediate sort; its cost depends on digit count and bucket/radix size. ↩︎