Java实现快速排序算法

简介

快速排序（Quick Sort）是由东尼·霍尔所发展的一种排序算法，在平均状况下，排序 n 个项目要 Ο(n log n) 次比较。在最坏状况下则需要 Ο(n^2) 次比较，但这种状况并不常见。快速排序使用分治法（Divide and Conquer）策略来把一个序列分为两个子序列，从而实现排序。本文将详细介绍如何使用Java实现快速排序算法，包括基础概念、使用方法、常见实践以及最佳实践。

快速排序基础概念

快速排序的基本步骤如下：

选择基准值（pivot）：从数组中选择一个元素作为基准值。这个值将用于划分数组。
分区操作（partition）：通过比较和交换元素，将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。
递归排序：对左右两个子数组分别递归地进行上述步骤，直到整个数组有序。

Java实现快速排序算法

代码示例

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++;

                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换 arr[i+1] 和 arr[high]（基准值）
        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};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        quickSort(arr, 0, arr.length - 1);

        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解析

quickSort方法：这是快速排序的主方法，接受一个整数数组 arr，以及要排序的子数组的起始索引 low 和结束索引 high。如果 low 小于 high，说明子数组至少有两个元素，需要进行排序。
partition方法：该方法负责进行分区操作。选择数组的最后一个元素作为基准值 pivot，然后通过遍历数组，将小于等于基准值的元素交换到左边，大于基准值的元素留在右边。最后，将基准值与 i + 1 位置的元素交换，返回 i + 1 作为基准值的最终位置。
main方法：用于测试快速排序算法。创建一个示例数组，打印排序前的数组，调用 quickSort 方法进行排序，然后打印排序后的数组。

常见实践

数组排序

上述代码已经展示了如何对整数数组进行快速排序。对于其他类型的数组，只需要修改 partition 方法中的比较逻辑即可。例如，对于字符串数组：

public class StringQuickSort {

    public static void quickSort(String[] 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(String[] arr, int low, int high) {
        String pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j].compareTo(pivot) <= 0) {
                i++;

                String temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        String temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        String[] arr = {"banana", "apple", "cherry", "date"};
        System.out.println("排序前数组:");
        for (String str : arr) {
            System.out.print(str + " ");
        }

        quickSort(arr, 0, arr.length - 1);

        System.out.println("\n排序后数组:");
        for (String str : arr) {
            System.out.print(str + " ");
        }
    }
}

列表排序

如果要对 List 进行排序，可以先将 List 转换为数组，然后进行排序，最后再将结果转换回 List。或者，也可以直接在 List 上进行操作：

import java.util.ArrayList;
import java.util.List;

public class ListQuickSort {

    public static void quickSort(List<Integer> list, int low, int high) {
        if (low < high) {
            int pi = partition(list, low, high);

            quickSort(list, low, pi - 1);
            quickSort(list, pi + 1, high);
        }
    }

    private static int partition(List<Integer> list, int low, int high) {
        int pivot = list.get(high);
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (list.get(j) <= pivot) {
                i++;

                int temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }

        int temp = list.get(i + 1);
        list.set(i + 1, list.get(high));
        list.set(high, temp);

        return i + 1;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(10);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(1);
        list.add(5);

        System.out.println("排序前列表:");
        System.out.println(list);

        quickSort(list, 0, list.size() - 1);

        System.out.println("排序后列表:");
        System.out.println(list);
    }
}

最佳实践

优化选择基准值

选择合适的基准值可以显著提高快速排序的性能。常见的优化方法有：

随机选择基准值：每次随机选择一个元素作为基准值，避免最坏情况的发生。

private static int partition(int[] arr, int low, int high) {
    // 随机选择一个元素作为基准值
    int randomIndex = low + (int) (Math.random() * (high - low + 1));
    int pivot = arr[randomIndex];

    // 将基准值与最后一个元素交换
    int temp = arr[randomIndex];
    arr[randomIndex] = arr[high];
    arr[high] = temp;

    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;

            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

三数取中：选择数组的第一个、中间和最后一个元素中的中间值作为基准值。

private static int partition(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    int pivot;

    // 选择第一个、中间和最后一个元素中的中间值作为基准值
    if ((arr[low] <= arr[mid] && arr[mid] <= arr[high]) || (arr[high] <= arr[mid] && arr[mid] <= arr[low])) {
        pivot = arr[mid];
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
    } else if ((arr[mid] <= arr[low] && arr[low] <= arr[high]) || (arr[high] <= arr[low] && arr[low] <= arr[mid])) {
        pivot = arr[low];
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    } else {
        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 quickSort(int[] arr, int low, int high) {
    if (low < high) {
        if (high - low + 1 <= 16) {
            // 对于小数组，使用插入排序
            insertionSort(arr, low, high);
        } else {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

private static void insertionSort(int[] arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

小结

快速排序是一种高效的排序算法，通过分治法将数组划分为两个子数组，递归地进行排序。本文介绍了快速排序的基础概念，提供了Java实现的代码示例，并探讨了常见实践和最佳实践。通过优化基准值选择和处理小数组等方法，可以进一步提高快速排序的性能。希望读者通过本文的学习，能够深入理解并灵活运用Java实现快速排序算法。

参考资料

《算法导论》（Introduction to Algorithms）
维基百科 - 快速排序
GeeksforGeeks - Quick Sort

更多学习资料

Java实现AC自动机算法：高效字符串匹配的利器

在字符串处理的领域中，常常会遇到需要在一个长文本中查找多个关键词的问题。传统的逐个匹配方法效率较低，而AC自动机算法（Aho-Corasick自动机算法）则提供了一种高效的解决方案。它能够在一次扫描长文本的过程中，同时查找多个关键词，大大提高了匹配效率。本文将深入探讨AC自动机算法在Java中的实现，包括基础概念、使用方法、常见实践以及最佳实践。

Java 实现数组：从基础到最佳实践

在 Java 编程中，数组是一种重要的数据结构，用于存储固定大小的同类型元素序列。它为开发人员提供了一种方便的方式来组织和管理数据，在各种应用场景中都发挥着关键作用。本文将全面介绍 Java 实现数组的相关知识，包括基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并熟练运用数组解决实际编程问题。

Java 实现 B+ 树算法：从基础到实践

B+ 树是一种自平衡二叉查找树的变种，在数据库索引和文件系统中有着广泛的应用。与普通的二叉树不同，B+ 树所有的叶子节点都在同一层，并且通过链表相连，这使得范围查询变得更加高效。本文将详细介绍如何使用 Java 实现 B+ 树算法，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现B树算法：深入探索与实践

在计算机科学中，B树是一种自平衡二叉查找树的泛化数据结构，它在文件系统和数据库索引等领域有着广泛的应用。B树允许每个节点拥有多于两个子节点，这使得它在处理大量数据时比传统的二叉树更有效率。本文将深入探讨如何使用Java实现B树算法，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现平衡二叉树：从基础到最佳实践

平衡二叉树（AVL树）是一种自平衡二叉查找树，由苏联数学家Georgy Adelson-Velsky和Evgenii Landis在1962年提出。它在数据存储和检索方面具有高效性，能确保在插入、删除和查找操作时，树的高度始终保持在对数级别，从而保证操作的时间复杂度为O(log n)。本文将深入探讨如何使用Java实现平衡二叉树，涵盖基础概念、使用方法、常见实践及最佳实践。

二叉查找树（Binary Search Tree，BST）是一种非常重要的数据结构，在计算机科学和软件开发中有着广泛的应用。它的特点是每个节点的值都大于其左子树中所有节点的值，小于其右子树中所有节点的值。这种特性使得二叉查找树在查找、插入和删除操作上具有较高的效率，平均时间复杂度为 O(log n)，其中 n 是树中节点的数量。本文将详细介绍如何使用 Java 实现二叉查找树算法，包括基础概念、使用方法、常见实践以及最佳实践。

Java 实现二分查找算法

二分查找（Binary Search），也被称为折半查找，是一种在有序数组中查找特定元素的高效算法。与顺序查找（逐个元素比较）相比，二分查找每次都能将搜索区间缩小一半，大大减少了查找所需的时间复杂度。在 Java 中，实现二分查找算法是掌握基本算法和数据结构的重要一步，本文将详细介绍其基础概念、使用方法、常见实践以及最佳实践。

Java 实现二叉树：从基础到实践

二叉树是计算机科学中一种重要的数据结构。它在许多领域都有广泛应用，如搜索算法、数据压缩、表达式求值等。在 Java 中，实现二叉树可以帮助我们更高效地组织和处理数据。本文将深入探讨 Java 实现二叉树的相关知识，包括基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要的数据结构。

Java实现BM字符串匹配算法：高效查找的利器

在字符串处理中，字符串匹配是一个常见且重要的任务。BM（Boyer-Moore）字符串匹配算法是一种高效的字符串搜索算法，由 Robert S. Boyer 和 J Strother Moore 在1977年发明。与传统的暴力匹配算法相比，BM算法通过利用待匹配字符串的字符信息，减少不必要的字符比较，从而显著提高匹配效率。本文将详细介绍如何使用Java实现BM字符串匹配算法，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现冒泡排序算法：基础、实践与最佳实践

冒泡排序（Bubble Sort）是一种简单直观的排序算法，也是学习排序算法的入门经典。它的基本思想是通过多次比较和交换元素，将无序数组逐步转换为有序数组。在Java中实现冒泡排序算法，能够帮助开发者深入理解排序算法的原理和数组操作的基本技巧。本文将详细介绍Java实现冒泡排序算法的基础概念、使用方法、常见实践以及最佳实践。

Java实现桶排序算法

排序算法在计算机科学中是非常重要的基础算法，桶排序（Bucket Sort）是一种分布式排序算法。它的基本思想是将数组分到有限数量的桶子里，每个桶子再分别进行排序，最后将排序好的桶子依次合并起来，从而得到一个有序的数组。与一些传统的排序算法（如冒泡排序、选择排序）相比，桶排序在特定条件下能够显著提高排序效率。本文将详细介绍如何使用Java实现桶排序算法，帮助读者深入理解该算法的原理与应用。

Java实现计数排序算法：深入理解与实践

排序算法在计算机科学中扮演着至关重要的角色，它能够将一组无序的数据转换为有序的数据，以便后续的查找、分析等操作更加高效。计数排序（Counting Sort）是一种非比较排序算法，它通过统计每个元素在序列中出现的次数，再根据统计结果将元素按顺序输出，从而实现排序的目的。计数排序的时间复杂度为 ( O(n + k) )，其中 ( n ) 是待排序元素的个数， ( k ) 是数据范围。相比一些基于比较的排序算法（如冒泡排序、选择排序等），计数排序在特定情况下具有更高的效率。

Java实现双端队列：深入解析与实践

在数据结构的领域中，双端队列（Deque，即Double - ended Queue的缩写）是一种特殊的数据结构，它允许在队列的两端进行插入和删除操作。与普通队列（FIFO，先进先出）和栈（LIFO，后进先出）不同，双端队列提供了更加灵活的数据处理方式。在Java中，有多种方式可以实现双端队列，本文将详细介绍其基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地理解和应用这一强大的数据结构。

Java 实现并查集：概念、使用与最佳实践

并查集（Union-Find Set）是一种非常实用的数据结构，主要用于处理不相交集合的合并与查询问题。在计算机科学领域，它被广泛应用于许多算法中，如 Kruskal 算法求解最小生成树、判断图中是否存在环等。本文将详细介绍如何使用 Java 实现并查集，包括其基础概念、使用方法、常见实践以及最佳实践。

Java 实现双向链表：深入解析与实践

在数据结构的领域中，链表是一种重要且基础的数据结构。而双向链表作为链表的一种特殊类型，它不仅允许沿着一个方向遍历，还能反向遍历，这为许多算法和应用场景提供了更大的灵活性。本文将深入探讨如何使用 Java 实现双向链表，涵盖基础概念、使用方法、常见实践以及最佳实践等方面，帮助读者全面掌握这一重要的数据结构。

Java实现树状数组：原理、使用与最佳实践

在算法和数据结构的领域中，树状数组（Fenwick Tree）是一种高效的数据结构，用于处理数组的前缀和查询以及单点更新操作。相比于传统的数组前缀和计算方式，树状数组能够在对数时间内完成这些操作，大大提高了算法的效率。本文将深入探讨如何使用Java实现树状数组，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现斐波那契查找算法

斐波那契查找（Fibonacci Search）是一种在有序数组中查找某一特定元素的搜索算法。它与二分查找类似，都是分治算法的一种应用，但斐波那契查找利用了斐波那契数列的特性来进行分割查找区间，在某些情况下，其性能表现优于二分查找。

Java实现图的广度优先搜索

图的广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索图数据结构的算法。它从给定的起始顶点开始，一层一层地扩展，先访问离起始顶点最近的顶点，然后逐渐向外扩展，直到访问完所有可达顶点。在Java中，实现图的广度优先搜索可以帮助我们解决许多实际问题，如路径查找、网络分析等。

Java实现图的深度优先搜索

图的深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索图数据结构的算法。在图中，深度优先搜索从起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续，然后回溯到上一个节点，继续探索其他未访问的路径。Java 作为一种广泛使用的编程语言，提供了丰富的工具和数据结构来实现图的深度优先搜索。本文将详细介绍 Java 实现图的深度优先搜索的基础概念、使用方法、常见实践以及最佳实践。

Java实现图：从基础到最佳实践

在计算机科学中，图是一种强大的数据结构，用于表示对象之间的关系。在Java中，实现图结构为解决许多复杂问题提供了有效的手段，如社交网络分析、路径规划、任务调度等。本文将深入探讨Java中图的基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要的数据结构。

Java实现哈希查找算法：从基础到最佳实践

在计算机科学领域，查找算法是处理数据时经常用到的工具。哈希查找算法作为一种高效的查找方式，能够在平均情况下以接近常数的时间复杂度进行数据查找。本文将深入探讨如何在Java中实现哈希查找算法，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要的算法技术。

Java实现哈希表：深入解析与实践

哈希表（Hash Table）是一种非常重要的数据结构，它提供了快速的数据查找和插入操作。在Java中，哈希表的实现基于哈希算法，通过将键（key）映射到一个特定的位置（桶，bucket）来存储和检索值（value）。理解哈希表的原理和使用方法对于优化程序性能、提高数据处理效率至关重要。本文将详细介绍Java实现哈希表的基础概念、使用方法、常见实践以及最佳实践。

Java实现堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，它满足堆特性：父节点的值总是大于或等于（最大堆）其子节点的值，或者总是小于或等于（最小堆）其子节点的值。堆排序的平均时间复杂度为 (O(n log n))，空间复杂度为 (O(1))。在这篇博客中，我们将详细探讨如何用Java实现堆排序算法。

Java实现堆：深入理解与高效应用

在计算机科学中，堆（Heap）是一种特殊的数据结构，它是一种完全二叉树，并且满足堆属性。在Java中，堆在许多算法和数据处理场景中都有广泛应用，例如优先队列的实现、堆排序算法等。本文将详细介绍Java实现堆的基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要的数据结构。

Java实现哈夫曼树：从基础到最佳实践

哈夫曼树（Huffman Tree）是一种在数据压缩等领域有着广泛应用的二叉树结构。它由美国数学家大卫·哈夫曼（David A. Huffman）于1952年提出，通过构造最优二叉树来实现数据的高效编码。在Java中，实现哈夫曼树不仅能帮助我们理解数据结构和算法的应用，还能为解决实际问题提供有力的工具。本文将深入探讨Java实现哈夫曼树的各个方面，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现插入排序算法

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是将数组分为已排序和未排序两部分，初始时已排序部分只有一个元素（即数组的第一个元素）。然后，算法从第二个元素开始，将未排序部分的每个元素插入到已排序部分的正确位置。插入排序对于少量数据的排序效率较高，并且在部分有序的数组上表现出色。本文将详细介绍如何使用Java实现插入排序算法，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现插值查找算法

在计算机科学中，查找算法是用于在一组数据元素中找到特定元素的算法。插值查找（Interpolation Search）是一种针对有序数组的查找算法，它在平均情况下具有比二分查找更快的查找速度，特别适用于数据分布均匀的数组。本文将详细介绍插值查找算法在Java中的实现，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现KMP字符串匹配算法

在字符串处理中，字符串匹配是一个常见的任务。KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它能够在文本字符串中快速查找模式字符串的出现位置。相较于传统的暴力匹配算法，KMP算法通过利用已经匹配的部分信息，避免了不必要的字符比较，从而显著提高了匹配效率。本文将详细介绍KMP算法在Java中的实现，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现线性探测哈希：深入理解与实践

哈希表（Hash Table）是一种在计算机科学中广泛使用的数据结构，它通过哈希函数将键（key）映射到一个特定的位置，从而实现快速的数据查找、插入和删除操作。线性探测哈希（Linear Probing Hash）是解决哈希冲突的一种简单而有效的方法。在本文中，我们将深入探讨如何使用Java实现线性探测哈希，包括基础概念、使用方法、常见实践以及最佳实践。

Java实现线性查找算法：从基础到最佳实践

在计算机科学领域，查找算法是解决数据检索问题的重要工具。线性查找（Linear Search）作为一种基本且直观的查找算法，适用于各种数据结构和场景。本文将深入探讨如何使用Java实现线性查找算法，涵盖其基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要算法。

Java实现链表：从基础到最佳实践

链表是一种重要的数据结构，在计算机科学中应用广泛。与数组不同，链表中的元素在内存中并不连续存储，而是通过节点（Node）之间的引用关系依次连接。在Java中，实现链表可以帮助我们更好地理解数据结构的原理，并且在许多实际场景中发挥作用，比如实现栈、队列等其他数据结构。本文将深入探讨Java实现链表的各个方面，包括基础概念、使用方法、常见实践和最佳实践。

Java实现最长公共子序列算法

在计算机科学中，最长公共子序列（Longest Common Subsequence，LCS）问题是一个经典的动态规划问题。给定两个序列，找出这两个序列中最长的公共子序列的长度。子序列是在不改变元素顺序的情况下，从原始序列中删除一些元素（也可以不删除任何元素）后得到的序列。例如，对于序列 [1, 3, 4, 5, 6, 7, 7, 8] 和 [3, 5, 7, 4, 8, 6, 7, 8, 2]，它们的一个公共子序列是 [3, 5, 7, 8]，而最长公共子序列可能有多个，但长度是固定的。在Java中，我们可以通过动态规划的方法高效地解决这个问题。

Java实现快速排序算法

简介

目录

快速排序基础概念

Java实现快速排序算法

代码示例

代码解析

常见实践

数组排序

列表排序

最佳实践

优化选择基准值

处理小数组

小结

参考资料

更多学习资料