java中排序

常见排序算法

image-20240522122241218

概览比较

排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
冒泡排序 O(n^2) O(n^2) O(n) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序 O(n^2) O(n^2) O(n) O(1) 稳定
希尔排序 O(n log n) O(n^2) O(n) O(1) 不稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定
快速排序 O(n log n) O(n^2) O(n log n) O(log n) 不稳定
堆排序 O(n log n) O(n log n) O(n log n) O(1) 不稳定
基数排序 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
public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            // 如果当前元素比下一个元素大，交换它们的位置
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 选择排序算法
public static void selectionSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            // 寻找未排序部分中的最小元素的索引
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小元素与当前位置的元素交换
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 插入排序算法
public static void insertionSort(int[] array) {
    int n = array.length;
    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;
        // 将大于key的元素向右移动，为key腾出插入位置
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 希尔排序算法
public static void shellSort(int[] array) {
    int n = array.length;
    // 使用希尔增量序列
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个增量进行插入排序
        for (int i = gap; i < n; i++) {
            int key = array[i];
            int j = i;
            // 将大于key的元素向后移动
            while (j >= gap && array[j - gap] > key) {
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = key;
        }
    }
}

归并排序（递归）

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
// 使用归并排序算法对数组进行排序
mergeSort(array, 0, array.length - 1);

// 归并排序算法
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 分割数组为两个子数组
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        // 合并两个子数组
        merge(array, left, mid, right);
    }
}

// 合并两个子数组
public static void merge(int[] array, int left, int mid, int right) {
    // 计算两个子数组的长度
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];

    // 将数据复制到临时数组
    for (int i = 0; i < n1; i++) {
        leftArray[i] = array[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArray[j] = array[mid + 1 + j];
    }

    // 合并临时数组并将结果存回原始数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            array[k] = leftArray[i];
            i++;
        } else {
            array[k] = rightArray[j];
            j++;
        }
        k++;
    }

    // 复制剩余的元素（如果有）
    while (i < n1) {
        array[k] = leftArray[i];
        i++;
        k++;
    }
    while (j < n2) {
        array[k] = rightArray[j];
        j++;
        k++;
    }
}

快速排序（递归）

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
// 快速排序算法
public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        // 将数组划分为两部分，并获取划分点的索引
        int partitionIndex = partition(array, low, high);

        // 递归地对划分的两部分进行排序
        quickSort(array, low, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, high);
    }
}

// 将数组划分为两部分，并返回划分点的索引
public static int partition(int[] array, int low, int high) {
    // 选择最右边的元素作为划分点（也可以选择其他元素作为划分点）
    int pivot = array[high];

    // 定义划分点的索引
    int i = low - 1;

    // 遍历数组，将小于划分点的元素放在左侧，大于划分点的元素放在右侧
    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            swap(array, i, j);
        }
    }

    // 将划分点放在正确的位置上
    swap(array, i + 1, high);

    return i + 1;
}

// 辅助方法：交换数组中两个元素的位置
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

堆排序

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
// 堆排序算法
public static void heapSort(int[] array) {
    int n = array.length;

    // 构建最大堆
    buildMaxHeap(array, n);

    // 从最后一个非叶子节点开始，依次将根节点与最后一个节点交换，并调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}

// 构建最大堆
public static void buildMaxHeap(int[] array, int n) {
    // 从最后一个非叶子节点开始，依次进行堆化操作
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
}

// 堆化操作
public static void heapify(int[] array, int n, int i) {
    int largest = i; // 初始化最大元素的索引为根节点
    int left = 2 * i + 1; // 左子节点的索引
    int right = 2 * i + 2; // 右子节点的索引

    // 如果左子节点大于根节点，则更新最大元素的索引
    if (left < n && array[left] > array[largest]) {
        largest = left;
    }

    // 如果右子节点大于最大元素，则更新最大元素的索引
    if (right < n && array[right] > array[largest]) {
        largest = right;
    }

    // 如果最大元素不是根节点，则交换根节点和最大元素，并继续调整堆
    if (largest != i) {
        swap(array, i, largest);
        heapify(array, n, largest);
    }
}

// 辅助方法：交换数组中两个元素的位置
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

基数排序

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
public static void radixSort(int[] arr) {
    // 找出最大值确定位数
    int max = Arrays.stream(arr).max().getAsInt();
    int numDigits = (int) Math.log10(max) + 1;

    // 创建桶
    int[][] buckets = new int[10][arr.length];
    int[] bucketSizes = new int[10];

    // 根据位数进行排序
    for (int digit = 0; digit < numDigits; digit++) {
        // 分配元素到桶中
        for (int num : arr) {
            int digitValue = (num / (int) Math.pow(10, digit)) % 10;
            buckets[digitValue][bucketSizes[digitValue]] = num;
            bucketSizes[digitValue]++;
        }

        // 收集桶中的元素
        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < bucketSizes[i]; j++) {
                arr[index] = buckets[i][j];
                index++;
            }
            bucketSizes[i] = 0;
        }
    }
}

Java已集成好的排序

列表

1
2
3
4
5
Arrays.sort(); 	// 使用快速排序（Quicksort）或归并排序（Mergesort）算法对数组进行排序。
Arrays.parallelSort();	// 并行版本的Arrays.sort()，利用多核处理器的并行能力提高排序性能。
Collections.sort();		// 使用TimSort算法对集合进行排序，结合了归并排序和插入排序的思想。
Arrays.sort(T[] a, Comparator<? super T> c);	// 根据自定义的Comparator规则对数组进行排序。
Collections.sort(List<T> list, Comparator<? super T> c);	// 根据自定义的Comparator规则对集合进行排序。

集合

TreeSet和TreeMap默认按照红黑树（数据结构）算法排序（通过红黑树来存储元素，并根据元素的自然顺序或者自定义的比较器来进行排序）

自定义比较器

涉及到 对象数组的比较的情况，两种方法处理：

  1. 继承comparable接口，并实现int compareTo(T o);方法
  2. 定义一个单独的对象比较器，继承自Comparator接口，实现 int compare(T o1, T o2);方法

Comparable

  1. Comparable是java.lang包中的一个排序接口。

  2. 只要一个类实现了这个接口就可以意味着这个类支持排序。

  3. 实现了这个类的接口的列表或者数组可以可以使用Collections.sort或Arrays.sort进行排序。

    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
    class Person implements Comparable<Person>{
        String name;
        int age;
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
        /**
         * 重新的compareTo方法。
         * @param person 用于指定的比较的对象。
         * @returns 相等则返回0，大于则返回正数（1），小于则返回负数（-1）。
         */
        @Override
        public int compareTo(Person person) {
            return this.age - person.age;
        }
        
        /* 测试 */
        public static void main(String[] args) {
            // 创建一个Person数组。
            Person[] persons = new Person[]{new Person("tom", 20), new Person("jack", 12)};
            // 排序之前
            for (Person p : persons) {
                System.out.print("name:" + p.name + ", age:" + p.age + " ");
            }
            Arrays.sort(persons);		// 测试中借助Arrays按照定义的Comparable接口进行排序
            // 排序之后
            for (Person p : persons) {
                System.out.print("name:" + p.name + ", age:" + p.age + " ");
            }
        }
    }
    /**
     * 最终排序结果解释：
     * 根据compareTo结果：
     * 返回 0，即 a-b < 0。说明a小于b，所以两者的顺序是:a, b。
     * 返回 1，即 a-b > 0。说明a大于b，所以两者的顺序是:b, a。
     * 返回-1，即 a-b=0。说明a等于b，所以两个数的顺序是:a, b
     */

Comparator

  1. Comparator是java.util中的一个比较的接口。

  2. 如果我们想要控制某个类的次序，而这个类并没有继承Comparable接口，那么我们就可以使用Comparator接口。

  3. 比较的规则：大致和上面的规则相同，不过也有不同的地方，详情请看下面的代码。

    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
    // 用法一：不重新创建一个类
    public void test(){
        Comparator<Integer> comparator = new Comparator<>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return 0;
            }
            @Override
            public boolean equals(Object obj) {
                return false;
            }
        };
        Integer[] a = {1, 2, 2, 9};
        Arrays.sort(a, comparator);
    }

    // 用法二：重新创建类，实现Comparator类
    class PersonComparator implements Comparator<Person> {
        @Override
        public int compare(Person p1, Person p2) {
            return p1.age - p2.age;
        }
    }
    public class Test {
        public static void main(String[] args) {
            // 创建一个Person数组。
            Person[] persons = new Person[]{new Person("tom", 20), new Person("jack", 12)};
            // 排序之后
            Arrays.sort(persons, new PersonComparator());
        }
    }

  4. 注意：比较器的泛型类型 和 被比较列表 的数据类型保持一致

总结

  1. 两者不在一个包。Comparable在java.lang中，而Comparator在java.util包中。
  2. 实现Comparable的类通常是一个我们要经常使用的类。比如：java中的String类等等。需要修改源代码。而Comparator可以在不同修改源代码的情况下，来完成比较。从了保护了代码。
  3. 两个方法各有优劣。如果你的类需要经常使用比较的操作，那么可以考虑让这个了实现Comparable接口。如果你偶尔使用比较的操作，那么可以考虑使用Comparator。

Title:java中排序

Author:

Created:2024-05-22, 10:57:56

Updated:2024-05-22, 14:32:06

Full URL:http://example.com/2024/05/22/java%E4%B8%AD%E6%8E%92%E5%BA%8F/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.

Contents
  1. 1. 常见排序算法
    1. 1.1. 概览比较
    2. 1.2. 冒泡排序
    3. 1.3. 选择排序
    4. 1.4. 插入排序
    5. 1.5. 希尔排序
    6. 1.6. 归并排序（递归）
    7. 1.7. 快速排序（递归）
    8. 1.8. 堆排序
    9. 1.9. 基数排序
  2. 2. Java已集成好的排序
    1. 2.1. 列表
    2. 2.2. 集合
  3. 3. 自定义比较器
    1. 3.1. Comparable
    2. 3.2. Comparator
    3. 3.3. 总结
|