快速排序【示例】

冒泡排序可以说是我们学习的第一个真正的排序算法,并且解决了桶排序浪费
空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了 O(N^2)。假如我
们的计算机每秒钟可以运行 10 亿次,那么对 1 亿个数进行排序,桶排序只需要 0.1 秒,而冒
泡排序则需要 1 千万秒,达到 115 天之久,是不是很吓人?那有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!

public class QuickSort {

    public static void main(String[] args) {
        int[] array = {34, 7, 23, 32, 5, 62, 32, 2, 78, 1};
        System.out.println("原始数组:");
        printArray(array);

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

        System.out.println("排序后的数组:");
        printArray(array);
    }

    // 快速排序的主函数
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // pi是分区索引,array[pi]已经排好序
            int pi = partition(array, low, high);

            // 递归地对分区前后的元素进行排序
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 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++;

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

        // 交换array[i + 1]和array[high] (即枢轴)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

    // 打印数组的辅助函数
    public static void printArray(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; ++i) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

快速排序之所以比较快,是因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候
设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全
部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进
行交换,交换的距离就大得多了。因此总的比较和交换次数就少了,速度自然就提高了。当
然在最坏的情况下,仍可能是相邻的两个数进行了交换。

因此快速排序的最差时间复杂度和冒泡排序是一样的,都是 O(N^2),

它的平均时间复杂度为 O (NlogN)。

其实快速排序是基于一种叫做“二分”的思想。

相关推荐

  1. Go 语言实现快速排序算法的简单示例

    2024-07-20 14:34:06       67 阅读
  2. 快速排序

    2024-07-20 14:34:06       51 阅读
  3. 排序算法——快速排序

    2024-07-20 14:34:06       60 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 14:34:06       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 14:34:06       106 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 14:34:06       87 阅读
  4. Python语言-面向对象

    2024-07-20 14:34:06       97 阅读

热门阅读

  1. #陕西大桥垮塌仍有20车30余人失联#

    2024-07-20 14:34:06       26 阅读
  2. Cookies和session区别

    2024-07-20 14:34:06       25 阅读
  3. BM20 数组中的逆序对

    2024-07-20 14:34:06       26 阅读
  4. SpringBoot使用Jasypt加密

    2024-07-20 14:34:06       23 阅读
  5. Linux 之 awk命令详解

    2024-07-20 14:34:06       25 阅读
  6. 电机线电流与转差率曲线理论推导

    2024-07-20 14:34:06       22 阅读
  7. 【HTTP 与 HTTPS 介绍与区别】

    2024-07-20 14:34:06       24 阅读
  8. (81)组合环路--->(05)避免组合环路

    2024-07-20 14:34:06       26 阅读
  9. 3.Implementing Controllers

    2024-07-20 14:34:06       20 阅读
  10. axios(ajax请求库)

    2024-07-20 14:34:06       24 阅读
  11. C++题目_中缀表达式转后缀表达式(常考)

    2024-07-20 14:34:06       24 阅读
  12. 差分进化(Differential Evolution)算法

    2024-07-20 14:34:06       29 阅读