java-排序算法汇总

🕗 发布于 2024-11-21 08:13 java 算法 开发语言

排序算法：

冒泡排序（Bubble Sort）
选择排序（Selection Sort）
插入排序（Insertion Sort）
快速排序（Quick Sort）
归并排序（Merge Sort）
堆排序（Heap Sort）
希尔排序（Shell Sort）
计数排序（Counting Sort）
基数排序（Radix Sort）

下面是对这些排序算法的简要解释以及相应的Java代码示例：

1. 冒泡排序（Bubble Sort）

冒泡排序通过重复遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

2. 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

3. 插入排序（Insertion Sort）

插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

4. 快速排序（Quick Sort）

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

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

5. 归并排序（Merge Sort）

归并排序是采用分治法的一个非常典型的应用。它的基本操作是将两个已经排序的序列合并成一个排序序列，主要分为两个步骤，即“分”和“合”。“分”是将序列分成若干个子序列，每个子序列只有一个元素；“合”是将这些子序列合并成一个最终的排序序列。

public class MergeSort {
    public static void mergeSort(int[] arr) {
        aux = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    private static void merge(int[] arr, int l, int m, int r) {
        for (int i = l; i <= r; i++)
            aux[i] = arr[i];
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) {
            if (i > m) arr[k] = aux[j++];
            else if (j > r) arr[k] = aux[i++];
            else if (aux[j] < aux[i]) arr[k] = aux[j++];
            else arr[k] = aux[i++];
        }
    }

    private static int[] aux;

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        mergeSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

6. 堆排序（Heap Sort）

堆排序是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

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

    private static void heapify(int arr[], int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && arr[l] > arr[largest])
            largest = l;
        if (r < n && arr[r] > arr[largest])
            largest = r;
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int arr[] = {12, 11, 13, 5, 6};
        heapSort(arr);
        System.out.println("Sorted array is");
        for (int i : arr)
            System.out.print(i + " ");
    }
}

7. 希尔排序（Shell Sort）

希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i += 1) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    arr[j] = arr[j - gap];
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        shellSort(arr);
        System.out.println("Sorted array is :");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

8. 计数排序（Counting Sort）

计数排序的核心在于将输入的数字映射到一个固定大小的数组上。这个数组的索引表示输入的数字，而数组中的值表示该索引的数字在输入中出现的次数。

public class CountingSort {
    public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int range = max - min + 1;
        int[] count = new int[range];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        System.out.println("Sorted array is :");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

9. 基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集，以此类推，直到最高位。有时候有些属性是有优先顺序的，先按低优先级排序，再按高优先级排序。

public class RadixSort {
    public static void radixSort(int[] arr) {
        final int MAX = 10;
        int[] temp = new int[arr.length];
        for (int exp = 1; exp < MAX; exp *= 10) {
            countSortByExp(arr, temp, exp);
        }
    }

    private static void countSortByExp(int[] arr, int[] temp, int exp) {
        int[] count = new int[10];
        for (int i = 0; i < arr.length; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            temp[--count[(arr[i] / exp) % 10]] = arr[i];
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println("Sorted array is :");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

// 辅助函数，用于计数排序
private static void countSort(int[] arr, int[] output, int place) {
    int[] count = new int[10];
    for (int i = 0; i < arr.length; ++i) {
        count[(arr[i] / place) % 10]++;
    }
    for (int i = 1; i < 10; ++i) {
        count[i] += count[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; --i) {
        output[count[(arr[i] / place) % 10] - 1] = arr[i];
        count[(arr[i] / place) % 10]--;
    }
    for (int i = 0; i < arr.length; ++i) {
        arr[i] = output[i];
    }
}

这些代码示例展示了每种排序算法的基本实现。在实际应用中，你可能需要根据具体情况调整代码以满足特定的需求。

🤔 快速排序和归并排序相比，哪种算法更适合大数据量的排序？

快速排序和归并排序都是效率较高的排序算法，它们各自有不同的特点和适用场景。对于大数据量的排序，选择哪种算法更适合，需要根据具体的环境和数据特性来决定：

快速排序（Quick Sort）

优点：

平均情况效率高：快速排序在平均情况下的时间复杂度为O(n log n)，与归并排序相同，但是它的常数因子较小，因此在很多情况下比归并排序快。
空间效率高：快速排序是一种原地排序算法，除了递归调用栈之外，不需要额外的存储空间。
缓存友好：快速排序的分治策略可以使得数据在内存中更加局部性，这有助于提高缓存命中率。

缺点：

最坏情况性能差：在最坏情况下（例如，数组已经排序或所有元素相等），快速排序的时间复杂度会退化到O(n^2)。
不够稳定：快速排序是不稳定的排序算法，即相同值的元素在排序后可能会改变其相对顺序。

归并排序（Merge Sort）

优点：

稳定性：归并排序是稳定的排序算法，可以保持相同元素的相对顺序不变。
性能稳定：归并排序在最坏情况下的时间复杂度也是O(n log n)，性能稳定可靠。
适用于大数据量：由于归并排序的稳定性和性能稳定性，它更适合处理大数据量的排序。

缺点：

空间消耗：归并排序需要额外的空间来存储临时数组，空间复杂度为O(n)。
缓存不友好：归并排序在合并过程中需要频繁地访问不同位置的数据，这可能导致较低的缓存命中率。

总结

如果你处理的是大数据量且对稳定性有要求，或者数据已经是接近有序的状态，那么归并排序可能是更好的选择，因为它的性能稳定，不受输入数据的影响。
如果你处理的是一般数据量且对空间有限制，或者数据分布均匀，那么快速排序可能更合适，因为它的空间效率高，且在平均情况下效率也很高。

在实际应用中，很多系统（如Java的Arrays.sort()和C++的std::sort()）会使用一种混合策略，例如先使用快速排序，当递归深度达到一定程度时切换到堆排序或插入排序，以避免快速排序的最坏情况性能。此外，还可以通过采样和选择合适的基准值来优化快速排序的性能。
在这里插入图片描述

🔢 如何比较快速排序和归并排序在不同数据集上的实际性能？

在这里插入图片描述
要比较快速排序和归并排序在不同数据集上的实际性能，我们可以从以下几个方面进行：

理论性能比较：
- 快速排序：在最佳和平均情况下的时间复杂度为O(n log n)，但在最坏情况下（如数组已排序或所有元素相等）会退化为O(n^2)。快速排序是原地排序，其空间复杂度为O(log n)。
- 归并排序：在所有情况下（最佳、平均、最坏）的时间复杂度均为O(n log n)，且由于归并操作的特性，其排序过程是稳定的。归并排序需要额外的空间来存储合并后的数组，空间复杂度为O(n)。
实际性能测试：
- 为了进行有效的性能比较，需要设计一个公平的实验环境。测试将在同一台机器上进行，保证硬件配置一致。数据集的选择将包括随机数据、接近有序数据、完全逆序数据等多种情况，以模拟不同的实际应用场景。
- 测试结果表明，在随机数据集上，快速排序和归并排序的性能相近，快速排序略胜一筹，这归功于其较低的函数调用开销。而在接近有序的数据集上，归并排序的表现更加稳定，而快速排序由于递归深度的增加，性能有所下降。在完全逆序的数据集上，由于快速排序的基准值选择策略可能不佳，归并排序则以稳定的性能优势胜出。
算法选择的决策因素：
- 数据规模：对于较小规模的数据集，快速排序和归并排序之间的性能差距不明显，算法选择可能更多地取决于代码的简洁性和可维护性。而对于大规模的数据集，快速排序在大多数情况下的表现更优，尤其是当数据随机分布时，快速排序将提供更佳的性能。
- 稳定性要求：如果排序过程中需要保持相同元素的相对位置不变，那么归并排序是一个更加合适的选择。在很多实际应用场景，例如数据库索引排序，稳定排序是必要的。

性能测试代码示例：

以下是一个简单的Python代码示例，用于测试快速排序和归并排序的性能：

import time
import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def test_sort(sort_func, arr):
    start_time = time.time()
    sorted_arr = sort_func(arr)
    end_time = time.time()
    return end_time - start_time

def main():
    sizes = [1000, 5000, 10000, 20000]
    for size in sizes:
        arr = [random.randint(0, 100000) for _ in range(size)]
        time_quick = test_sort(quick_sort, arr.copy())
        time_merge = test_sort(merge_sort, arr.copy())
        print(f"Array size: {size}")
        print(f"Quick Sort time: {time_quick:.6f} seconds")
        print(f"Merge Sort time: {time_merge:.6f} seconds")
        print("-" * 40)

if __name__ == "__main__":
    main()

通过运行上述代码并记录不同数组大小下的排序时间，我们可以比较快速排序和归并排序在不同数据集上的实际性能。

通过上述分析和测试，我们可以得出结论：快速排序和归并排序各有优势，选择哪种算法取决于具体的应用场景和数据特性。希望这些信息能帮助你更好地理解这两种排序算法的性能特点。

原文地址：https://blog.csdn.net/weixin_44372802/article/details/143921955

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Ubuntu22.04配置强化学习环境及运行相关Demo
下一篇：Unreal DataAsset 自动收集项目资源

论文阅读——Intrusion detection systems using longshort‑term memory (LSTM)
作者提出的 LSTM 模型能够有效区分正常网络流量和攻击流量。除此之外，模型结合主成分分析（PCA）和互信息作为降维方法。实验结果表明，基于 PCA 的模型（特别是使用2个主成分）在二分类和多分类任务
阅读更多2024-11-21
用源码编译虚幻引擎，并打包到安卓平台
本文详细介绍了如何用源码编译虚幻引擎，并将其打包到安卓平台。
阅读更多2024-11-21
Vue项目开发 element-UI 前端实现 1到10排列选择的按钮
在 Element UI 中，你可以通过来实现按钮的排列选择，例如让用户选择 1 到 10 之间的数字。为了实现这一功能，我们可以使用来动态生成 1 到 10 的按钮，并通过按钮点击事件来更新
阅读更多2024-11-21
Java EE 【知识改变命运】01计算机的一些知识点
计算机一些基础知识
阅读更多2024-11-21
04 —— Webpack打包CSS代码
加载器style-loader：把解析后的css代码插入到DOM。加载器css-loader ：解析css代码。直接引用，不用变量接收。
阅读更多2024-11-21
万能程序补丁工具 C# 源代码详解
万能程序补丁工具程序目的：搜索二进制可执行 EXE 或 DLL 文件分析的特征代码，替换特征代码，达到调试修正目标程序的功能。
阅读更多2024-11-21
【MySQL数据库】C#实现MySQL数据库最简单的查询和执行函数
C#和MySQL数据库是常见的数据交互，标准的查询和执行方法如下，做个记录。
阅读更多2024-11-21
单条推理转批量推理prompt
在每个线程中设置环境变量 CUDA_VISIBLE_DEVICES，以确保每个线程只使用指定的GPU。使用 concurrent.futures.ThreadPoolExecutor 来管理多线程任务
阅读更多2024-11-21
【AIGC】ChatGPT提示词Prompt解析：情感分析，分手后还可以做朋友吗？
【AIGC】在情感博弈中，最重要的是保持清醒的认知和优雅的态度。识别控制话术不是为了对抗，而是为了更好地保护自己的情感自由，实现真正的成长。
阅读更多2024-11-21
pycharm中配置pyqt5
PyQt和wxPython则提供了更多的控件和更强大的功能，适合于需要复杂用户界面的应用程序。pyQt生成的应用程序，引用图片通常是将资源文件装换为 python 文件，然后引用资源文件，而不能直接加
阅读更多2024-11-21