当前位置： 首页 > article >正文

java-排序算法汇总

article 2024/11/24 10:40:31

排序算法：

冒泡排序（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）

优点：

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

缺点：

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

归并排序（Merge Sort）

优点：

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

缺点：

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

总结

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

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

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

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

  1. 理论性能比较：

    • 快速排序：在最佳和平均情况下的时间复杂度为O(n log n)，但在最坏情况下（如数组已排序或所有元素相等）会退化为O(n^2)。快速排序是原地排序，其空间复杂度为O(log n)。
    • 归并排序：在所有情况下（最佳、平均、最坏）的时间复杂度均为O(n log n)，且由于归并操作的特性，其排序过程是稳定的。归并排序需要额外的空间来存储合并后的数组，空间复杂度为O(n)。

  2. 实际性能测试：

    • 为了进行有效的性能比较，需要设计一个公平的实验环境。测试将在同一台机器上进行，保证硬件配置一致。数据集的选择将包括随机数据、接近有序数据、完全逆序数据等多种情况，以模拟不同的实际应用场景。
    • 测试结果表明，在随机数据集上，快速排序和归并排序的性能相近，快速排序略胜一筹，这归功于其较低的函数调用开销。而在接近有序的数据集上，归并排序的表现更加稳定，而快速排序由于递归深度的增加，性能有所下降。在完全逆序的数据集上，由于快速排序的基准值选择策略可能不佳，归并排序则以稳定的性能优势胜出。

  3. 算法选择的决策因素：

    • 数据规模：对于较小规模的数据集，快速排序和归并排序之间的性能差距不明显，算法选择可能更多地取决于代码的简洁性和可维护性。而对于大规模的数据集，快速排序在大多数情况下的表现更优，尤其是当数据随机分布时，快速排序将提供更佳的性能。
    • 稳定性要求：如果排序过程中需要保持相同元素的相对位置不变，那么归并排序是一个更加合适的选择。在很多实际应用场景，例如数据库索引排序，稳定排序是必要的。

  4. 性能测试代码示例：

    • 以下是一个简单的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()
    • 通过运行上述代码并记录不同数组大小下的排序时间，我们可以比较快速排序和归并排序在不同数据集上的实际性能。

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


http://www.kler.cn/a/407057.html

相关文章：

  • 遗传算法（Genetic Algorithm, GA）
  • 如何更改手机GPS定位
  • gocv调用opencv添加中文乱码的解决方案
  • MATLAB矩阵元素的修改及删除
  • Android Google登录接入
  • RocketMQ文件刷盘机制深度解析与Java模拟实现
  • 归并排序与逆序对问题(C语言版)
  • Spark RDD Checkpoint 数据的保存机制
  • VSCode打开c#项目报错：DotnetAcquisitionTimeoutError
  • CSS浮动：概念、特性与应用
  • Sonar Qube介绍和安装（三）
  • uni-app 认识条件编译，了解多端部署
  • 雷电模拟器charles代理抓包
  • 分层架构 IM 系统之 Entry 部署模式
  • 【线程】Java线程操作
  • 【论文笔记】LLaVA-KD: A Framework of Distilling Multimodal Large Language Models
  • 自动化测试用例编写详解
  • 机器学习杂笔记1：类型-数据集-效果评估-sklearn-机器学习算法分类
  • PH热榜 | 2024-11-23
  • RabbitMQ高可用延迟消息惰性队列
  • Unity图形学之法线贴图原理
  • Python设计模式详解之10 —— 外观模式
  • 1123--日期类
  • 华为防火墙技术基本概念学习笔记
  • 医学AI公开课·第一期｜Machine LearningTransformers in Med AI
  • D77【 python 接口自动化学习】- python基础之HTTP