java实现十大排序算法

文章目录

冒泡排序

冒泡排序（Bubble Sort）是一种简单的比较排序算法，它的基本思想是重复地交换相邻的两个元素，直到整个数组都是有序的。冒泡排序是一种稳定排序算法，因为它不会改变相等元素的相对顺序。

冒泡排序的基本步骤如下：

  1. 比较相邻元素： 从数组的第一个元素开始，依次比较相邻的两个元素。
  2. 交换元素： 如果两个相邻元素的顺序不正确（例如，前一个元素大于后一个元素），则交换它们的位置。
  3. 重复： 继续重复步骤1和步骤2，直到没有需要交换的元素为止。每一轮都会将最大的元素冒泡到数组的末尾。
  4. 减少范围： 在每一轮排序后，最大的元素都会冒泡到最后的位置，因此可以减少下一轮的比较范围，不再考虑已排序的部分。
  5. 完成排序： 当没有需要交换的元素时，数组已经排序完成。

虽然冒泡排序是一种简单的排序算法，但它的时间复杂度较高，为O(n^2)，其中n是待排序元素的数量。因此，它对于大规模数据集不太高效。冒泡排序通常用于小规模数据排序。

public class BubbleSort {
    public static void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean swapped = false;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int t = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = t;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

选择排序

选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是将数组分成已排序和未排序两部分，每次从未排序部分选择最小（或最大）的元素，然后将其放到已排序部分的末尾。选择排序不像冒泡排序那样每次都交换元素，而是只在最后确定了最小元素的位置后进行交换。选择排序也是一种不稳定的排序算法，因为它可能改变相等元素的相对顺序。

以下是选择排序的基本步骤：

  1. 初始化： 将整个数组视为两部分，已排序部分和未排序部分。一开始，已排序部分为空，而未排序部分包括整个数组。
  2. 查找最小元素： 从未排序部分中查找最小的元素，并记住其索引。
  3. 交换元素： 将最小元素与未排序部分的第一个元素交换位置，将最小元素移到已排序部分的末尾。
  4. 缩小范围： 缩小未排序部分的范围，将已排序部分扩展一个元素，继续重复步骤2和步骤3，直到未排序部分为空。
  5. 完成排序： 当未排序部分为空时，排序完成。

尽管选择排序在最坏情况下和平均情况下的时间复杂度都是O(n^2)，但它不需要额外的存储空间，因此在某些情况下可能是一个有用的排序算法，特别是当内存有限时。

public class SelectionSort {
    public static void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[minIndex] > nums[j]) minIndex = j;
            }
            int t = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = t;
        }
    }
}

插入排序

插入排序（Insertion Sort）是一种简单而有效的排序算法。它的基本思想是将数组分成已排序和未排序两部分，从未排序部分选择一个元素，插入到已排序部分的合适位置，重复这个过程，直到整个数组都有序。插入排序是一种稳定排序算法，因为它不会改变相等元素的相对顺序。

以下是插入排序的基本步骤：

  1. 初始化： 将整个数组视为两部分，已排序部分和未排序部分。一开始，已排序部分只包含数组的第一个元素，而未排序部分包括其余部分。
  2. 选择未排序部分的元素： 从未排序部分选择一个元素，通常从未排序部分的开头选取。
  3. 插入元素： 将选取的元素与已排序部分的元素进行比较，找到合适的位置插入选取的元素，以确保已排序部分仍然有序。
  4. 重复： 继续从未排序部分选择元素，并插入已排序部分，直到未排序部分为空。
  5. 完成排序： 当未排序部分为空时，排序完成。

插入排序在平均和最坏情况下的时间复杂度都是O(n^2)，其中n是待排序元素的数量。然而，在某些情况下，插入排序可能比其他排序算法更加高效，尤其是当待排序的数据集已经基本有序时。

public class InsertionSort {
    public static void sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int t = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > t) {
                nums[j + 1] = nums[j--];
            }
            nums[j + 1] = t;
        }
    }
}

希尔排序

希尔排序（Shell Sort）是一种改进的插入排序算法，也称为缩小增量排序。它的基本思想是将整个数组分成多个子序列，对每个子序列进行插入排序，然后逐渐减小子序列的长度，最终使整个数组有序。希尔排序的关键在于选择合适的间隔序列，称为增量序列，以确定子序列的长度。

希尔排序的主要步骤如下：

  1. 选择增量序列： 首先，选择一个增量序列，这个序列的最后一个元素必须为1，通常以一种特定的方式生成，例如使用 Knuth 序列或者 Sedgewick 序列。
  2. 按增量分组： 将数组按照增量分成多个子序列。每个子序列包含相距为增量的元素。
  3. 对每个子序列进行插入排序： 对每个子序列进行插入排序，即将子序列中的元素按照插入排序的方式排序。
  4. 减小增量： 缩小增量，通常是将增量除以一个固定的因子，继续重复步骤2和步骤3。
  5. 最后一次排序： 最后一次排序时，增量通常为1，即将整个数组作为一个子序列进行插入排序。
  6. 完成排序： 当增量减小到1时，继续进行插入排序，最终整个数组将被排序。

希尔排序的关键在于增量序列的选择，不同的增量序列可能导致不同的性能。希尔排序的时间复杂度取决于增量序列的选择，但通常在O(n2)和O(n1.25)之间。希尔排序的优点是可以在不使用额外内存的情况下进行排序，因此适用于对内存限制的情况。

public class ShellSort {

    public static void sort(int[] nums) {
        shellSort(nums);
    }

    public static void shellSort(int[] nums) {
        int gap = nums.length / 2;
        while (gap > 0) {
            for (int i = gap; i < nums.length; i++) {
                int t = nums[i];
                int j = i - gap;
                while (j >= 0 && nums[j] > t) {
                    nums[j + gap] = nums[j];
                    j -= gap;
                }
                nums[j + gap] = t;
            }
            gap >>= 1;
        }
    }
}

归并排序

归并排序（Merge Sort）是一种经典的分治算法，它的核心思想是将一个大的问题分解成多个小的子问题，解决每个子问题，然后将它们合并起来以得到最终的解决方案。归并排序的主要步骤包括分解、解决和合并。

以下是归并排序的详细步骤：

  1. 分解（Divide）： 将待排序的数组分解为两个子数组，通常是平均分割。这个过程持续递归，直到每个子数组的大小为1或0，即无法再分解为更小的子问题。
  2. 解决（Conquer）： 对每个子数组进行排序，可以使用递归或迭代的方式，这个过程通常采用归并排序本身。
  3. 合并（Merge）： 将已排序的子数组合并成一个有序的数组。合并过程是归并排序的关键步骤，需要合并两个有序的子数组为一个有序的数组。
  4. 重复合并（Repeat Merge）： 重复执行步骤2和步骤3，直到所有的子数组都合并成一个有序的数组为止。
  5. 得到排序结果（Result）： 当所有的子数组都合并完成，得到的就是排序好的数组。

归并排序是一种稳定的排序算法，它的时间复杂度为O(n log n)，其中n是数组的大小。这使得归并排序在大多数情况下都比较高效，特别是对于大型数据集。

public class MergeSort {

    public static void sort(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
    }

    public static void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int middle = left + (right - left) / 2;
            mergeSort(nums, left, middle);
            mergeSort(nums, middle + 1, right);
            merge(nums, left, middle, right);
        }
    }

    public static void merge(int[] nums, int left, int middle, int right) {
        int[] leftNums = new int[middle - left + 1];
        int[] rightNums = new int[right - middle];
        int l = 0;
        int r = 0;
        for (int i = left; i <= right; i++) {
            if (i <= middle) leftNums[l++] = nums[i];
            else rightNums[r++] = nums[i];
        }
        l = 0;
        r = 0;
        int p = left;
        while (l < leftNums.length || r < rightNums.length) {
            if (l == leftNums.length) nums[p++] = rightNums[r++];
            else if (r == rightNums.length) nums[p++] = leftNums[l++];
            else if (leftNums[l] <= rightNums[r]) nums[p++] = leftNums[l++];
            else nums[p++] = rightNums[r++];
        }
    }
}

快速排序

快速排序（Quick Sort）是一种常用的排序算法，它也是一种分治算法。它的核心思想是选择一个基准元素（通常是数组的第一个元素），将数组分成两个子数组，其中一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大，然后对这两个子数组递归地进行快速排序。

以下是快速排序的主要步骤：

  1. 选择基准元素（Pivot）： 从数组中选择一个元素作为基准元素。通常选择第一个元素，但也可以选择其他位置的元素。
  2. 分区（Partitioning）： 将数组中的元素分成两个子数组，一个子数组包含比基准元素小的元素，另一个子数组包含比基准元素大的元素。基准元素的位置在分区后将是最终排好序的位置。
  3. 递归排序子数组： 对分区后的两个子数组递归地应用快速排序算法，直到子数组的大小为1或0，即无法再分区。
  4. 合并结果： 将排序好的子数组合并起来，得到最终的有序数组。

快速排序是一种高效的排序算法，平均情况下的时间复杂度为O(n log n)，最坏情况下为O(n^2)，但最坏情况很少发生。它通常比其他O(n log n)复杂度的排序算法快，因为它在内部排序中是原地排序（不需要额外的内存），而且适用于大型数据集。

public class QuickSort {

    public static void sort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (start >= end) return;
        int pivot = nums[start];
        int left = start + 1;
        int right = end;
        while (true) {
            while (left <= right && nums[left] <= pivot) left++;
            while (left <= right && nums[right] >= pivot) right--;
            if (left <= right) swap(nums, left, right);
            else break;
        }
        swap(nums, start, right);
        quickSort(nums, start, right - 1);
        quickSort(nums, right + 1, end);
    }

    public static void swap(int[] nums, int x, int y) {
        int t = nums[x];
        nums[x] = nums[y];
        nums[y] = t;
    }
}

堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它利用了堆的性质来进行排序，其中堆可以分为最大堆和最小堆。堆排序通常使用最大堆来进行升序排序。

堆排序的主要思想是将待排序的数组构建成一个二叉堆（最大堆），然后不断将堆顶元素（最大元素）与堆的最后一个元素交换，然后将堆的大小减一，再对剩余的元素进行堆的调整，使其满足最大堆的性质，重复这个过程直到整个数组排序完成。

以下是堆排序的主要步骤：

  1. 构建最大堆（Heapify）： 从输入数组构建一个最大堆。这可以通过从最后一个非叶子节点开始，逐步向前进行堆化来实现。堆化的过程是将当前节点与其子节点进行比较，并确保最大堆性质被维护。
  2. 交换与重建堆： 将堆顶元素（最大元素）与堆的最后一个元素交换，然后减小堆的大小。接着对堆顶元素进行下沉操作，重新调整堆以满足最大堆性质。
  3. 重复步骤 2 直到堆为空： 重复上述交换和重建堆的过程，直到堆中只剩下一个元素，此时整个数组就已经排序完成。

堆排序的时间复杂度为 O(n log n)，并且是一种原地排序算法，因为它不需要额外的存储空间。

public class HeapSort {

    public static void sort(int[] nums) {
        heapSort(nums);
    }

    public static void heapSort(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            heapify(nums, nums.length, i);
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            int t = nums[0];
            nums[0] = nums[i];
            nums[i] = t;
            heapify(nums, i, 0);
        }
    }

    public static void heapify(int[] nums, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && nums[left] > nums[largest]) largest = left;
        if (right < n && nums[right] > nums[largest]) largest = right;
        if (largest != i) {
            int t = nums[i];
            nums[i] = nums[largest];
            nums[largest] = t;
            heapify(nums, n, largest);
        }
    }
}

桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它通过将待排序元素分散到多个桶中，然后分别对每个桶中的元素进行排序，最后将所有桶中的元素合并成有序序列。桶排序适用于输入数据均匀分布在某个范围内的情况，例如浮点数排序。

下面是桶排序的基本思想和步骤：

  1. 确定桶的数量： 首先确定要使用的桶的数量，桶的数量可以根据输入数据的范围和分布情况来决定。
  2. 将元素分配到桶中： 遍历待排序的元素，将每个元素放入相应的桶中。这可以通过一个映射函数来实现，映射函数将元素映射到桶的索引。
  3. 对每个桶进行排序： 对每个非空桶中的元素进行排序。可以使用其他排序算法，如插入排序或快速排序，来对每个桶中的元素进行排序。
  4. 合并桶中的元素： 将排序后的桶依次合并，得到最终的有序序列。
public class BucketSort {
    public static void sort(int[] nums) {
        bucketSort(nums, nums.length);
    }

    public static void bucketSort(int[] nums, int numBuckets) {
        if (nums == null || nums.length <= 1) return;
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int bucketSize = (max - min + 1) / numBuckets + 1;
        List<Integer>[] buckets = new ArrayList[numBuckets];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (int num : nums) {
            buckets[(num - min) / bucketSize].add(num);
        }
        int p = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (Integer value : bucket) {
                nums[p++] = value;
            }
        }
    }
}

基数排序

基数排序（Radix Sort）是一种非比较性的整数排序算法，它通过将待排序的整数按照位数进行排序。基数排序的核心思想是从最低位（个位数）开始，按照位数的顺序依次进行排序，直到最高位（最高位数）。每次排序都是稳定的计数排序或桶排序，保持了元素的相对顺序。这样，多次排序后，最终得到的结果就是整体有序的。

下面是基数排序的基本步骤：

  1. 确定排序的位数： 首先确定要排序的整数的最高位数，通常是通过找到最大的整数来确定的。
  2. 按位数排序： 从最低位（个位数）开始，对整数进行稳定的排序（通常使用计数排序或桶排序）。按照当前位数的值，将整数分配到对应的桶中。
  3. 依次处理高位数： 继续对下一位数进行排序，直到处理完最高位数。这个过程是递归的，每次排序都是以前一轮排序的结果为基础。
  4. 合并结果： 经过多轮排序后，最终得到的结果就是整体有序的。
public class RadixSort {

    public static void sort(int[] nums) {
        radixSort(nums);
    }

    public static void radixSort(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int exp = 1;

        int[] bucket = new int[nums.length];

        while (max / exp > 0) {
            int[] count = new int[10];

            for (int num : nums) {
                count[(num / exp) % 10]++;
            }
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }
            for (int i = nums.length - 1; i >= 0; i--) {
                bucket[--count[(nums[i] / exp) % 10]] = nums[i];
            }
            System.arraycopy(bucket, 0, nums, 0, nums.length);
            exp *= 10;
        }
    }
}

计数排序

计数排序（Counting Sort）是一种非比较性的整数排序算法，它通过统计待排序整数中每个整数出现的次数，然后按照整数的值顺序输出排好序的结果。计数排序适用于整数排序，特别是当待排序的整数范围相对较小时（不过这个范围不能太大，否则需要大量的内存来存储计数数组）。

以下是计数排序的基本思想和步骤：

  1. 找出待排序的整数范围： 首先确定待排序整数的最小值（min）和最大值（max），以便确定计数数组的大小。
  2. 创建计数数组： 创建一个大小为max - min + 1的计数数组，用于存储每个整数出现的次数。数组的索引对应于整数的值，数组的值表示该整数出现的次数。
  3. 统计整数出现次数： 遍历待排序的整数数组，对每个整数进行统计，增加相应值的计数器。
  4. 生成排序结果： 遍历计数数组，按照整数的值和出现次数，将整数输出到排序结果数组中。

计数排序的时间复杂度是 O(n+k)，其中 n 是待排序整数的个数，k 是整数范围。在整数范围不大的情况下，计数排序可以非常高效。

public class CountingSort {

    public static void sort(int[] nums) {
        countingSort(nums);
    }

    public static void countingSort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int k = max - min + 1;
        int[] countArr = new int[k];
        for (int num : nums) {
            countArr[num - min]++;
        }
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i - 1];
        }
        int[] temp = new int[k];
        for (int i = nums.length - 1; i >= 0; i--) {
            temp[--countArr[nums[i] - min]] = nums[i];
        }
        System.arraycopy(temp, 0, nums, 0, nums.length);
    }
}

验证

上面排序算法可以使用下面代码进行验证

public class SortTest {
    public static void test(Class aclass, Method method, String name) {
        int count = 1000;
        while (count-- > 0) {
            int[] nums1 = new int[1000];
            for (int i = 0; i < nums1.length; i++) {
                nums1[i] = (int) (Math.random() * 10000);
            }
            int[] nums2 = Arrays.copyOf(nums1, nums1.length);
            Arrays.sort(nums1);
            try {
                method.invoke(aclass, nums2);
            } catch (IllegalAccessException | InvocationTargetException e) {
                throw new RuntimeException(e);
            }
            boolean flag = Arrays.equals(nums1, nums2);
            if (!flag) {
                System.out.println("=========================================");
                System.out.println(name + "排序错误");
                System.out.println(Arrays.toString(nums1));
                System.out.println(Arrays.toString(nums2));
                System.out.println("=========================================");
                return;
            }
        }
        System.out.println(name + "OK");
    }

    public static void main(String[] args) throws NoSuchMethodException {
        test(QuickSort.class, QuickSort.class.getMethod("sort", int[].class), "快速排序");
        test(SelectionSort.class, SelectionSort.class.getMethod("sort", int[].class), "选择排序");
        test(BubbleSort.class, BubbleSort.class.getMethod("sort", int[].class), "冒泡排序");
        test(InsertionSort.class, InsertionSort.class.getMethod("sort", int[].class), "插入排序");
        test(MergeSort.class, MergeSort.class.getMethod("sort", int[].class), "归并排序");
        test(ShellSort.class, ShellSort.class.getMethod("sort", int[].class), "希尔排序");
        test(HeapSort.class, HeapSort.class.getMethod("sort", int[].class), "堆排序");
        test(BucketSort.class, BucketSort.class.getMethod("sort", int[].class), "桶排序");
        test(CountingSort.class, CountingSort.class.getMethod("sort", int[].class), "计数排序");
        test(RadixSort.class, RadixSort.class.getMethod("sort", int[].class), "基数排序");
    }
}

上面代码会随机生成1000个[0,9999]的数，然后进行排序，重复1000次来验证代码的正确性，上面代码输入如下

image-20230919204330808

各个排序的时间复杂度和空间复杂度

以下是十大常见排序算法的平均时间复杂度、最坏时间复杂度、最好时间复杂度、空间复杂度以及是否稳定的表格展示：

排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 是否稳定排序
冒泡排序 (Bubble Sort) O(n^2) O(n^2) O(n) O(1) 是
选择排序 (Selection Sort) O(n^2) O(n^2) O(n^2) O(1) 否
插入排序 (Insertion Sort) O(n^2) O(n^2) O(n) O(1) 是
希尔排序 (Shell Sort) O(n1.3-2) O(n^2) O(n log n) O(1) 否
归并排序 (Merge Sort) O(n log n) O(n log n) O(n log n) O(n) 是
快速排序 (Quick Sort) O(n log n) O(n^2) O(n log n) O(log n) 否
堆排序 (Heap Sort) O(n log n) O(n log n) O(n log n) O(1) 否
计数排序 (Counting Sort) O(n + k) O(n + k) O(n + k) O(k) 是
桶排序 (Bucket Sort) O(n + k) O(n^2) O(n) O(n + k) 是
基数排序 (Radix Sort) O(n * k) O(n * k) O(n * k) O(n + k) 是

说明：

  • “n” 表示输入数据的规模。
  • “k” 表示输入数据中的最大值和最小值之差（数字的范围），基数排序中k可以理解为最大值的位数，但更准确地说，它表示每个数字的进制。