5秒用Java写一个快速排序算法?这个我可以

原创
2023/10/18 17:47
阅读数 41

快速排序是一种非常高效的排序算法,由英国计算机科学家霍尔在1960年提出。它的基本思想是选择一个基准元素将待排序数组分成两部分,其中一部分的所有元素都比基准元素小,另一部分的所有元素都比基准元素大,然后对这两部分再分别进行快速排序,整个排序过程可以递归进行。

这种算法的主要步骤是:

  1. 选择一个元素作为基准(pivot)。
  2. 把数组分为两部分:一部分包含所有小于基准的元素,另一部分包含所有大于或等于基准的元素。这个过程称为分区(partition)操作。
  3. 对这两个子数组进行递归排序

下面是一个由FuncGPT(慧函数)生成的用Java实现快速排序的基本示例:

// 类名:QuickSort
// 函数名:quickSort
// 函数功能:使用快速排序算法对数组进行排序
// POM依赖包:无

public class QuickSort {

    /**
     * 使用快速排序算法对数组进行排序
     * @param arr 待排序的数组
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序的递归实现
     * @param arr 待排序的数组
     * @param low 左边界
     * @param high 右边界
     */
    private static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high); // 获取基准值的索引
            sort(arr, low, pivot - 1); // 对基准值左侧的子数组进行排序
            sort(arr, pivot + 1, high); // 对基准值右侧的子数组进行排序
        }
    }

    /**
     * 快速排序的分区实现
     * @param arr 待排序的数组
     * @param low 左边界
     * @param high 右边界
     * @return 选择的基准值的索引
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选择第一个元素作为基准值
        int i = low + 1;
        int j = high;

        while (i <= j) {
            while (i <= j && arr[i] <= pivot) {
                i++;
            }

            while (i <= j && arr[j] > pivot) {
                j--;
            }

            if (i < j) {
                swap(arr, i, j);
            }
        }

        swap(arr, low, j); // 将基准值放到正确的位置上

        return j;
    }

    /**
     * 交换数组中两个位置的元素
     * @param arr 数组
     * @param i 位置1
     * @param j 位置2
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 5, 1, 8, 3, 7, 4, 2, 6};
        quickSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
```

// 函数示例
// 使用快速排序算法对数组进行排序示例
// 入参:arr,待排序的数组
// 出参:无,直接对输入的数组进行排序
// 调用示例:
// int[] arr = new int[]{9, 5, 1, 8, 3, 7, 4, 2, 6};
// QuickSort.quickSort(arr);
// 输出结果:例如,对数组[9, 5, 1, 8, 3, 7, 4, 2, 6]进行排序
// 排序后的数组为[1, 2, 3, 4, 5, 6, 7, 8, 9]
// 则输出结果为:1 2 3 4 5 6 7 8 9
```
// 温馨提示:以上代码由 FuncGPT 生成,编译打包请使用 QuickSort.java 文件。

这段代码中的主要函数包括:

  1. quickSort(int[ ] arr): 这是快速排序的入口函数,它接受一个整数数组作为参数,并对它进行排序。如果输入的数组为空或者只包含一个元素,这个函数就会直接返回。
  2. sort(int[ ] arr, int low, int high): 这是一个递归函数,用于对数组的子区间进行排序。如果左边界 low 小于右边界 high,它会选择一个基准元素,然后对基准元素左侧和右侧的子数组分别进行递归排序。
  3. partition(int[ ] arr, int low, int high): 这个函数用于实现快速排序中的分区操作。它选择数组中的一个基准元素,然后把数组中的其他元素移动到基准元素的左侧或右侧。在这个过程中,小于基准元素的元素会被移动到基准元素的左侧,大于基准元素的元素会被移动到基准元素的右侧。这个函数返回的是基准元素在排序后数组中的位置。
  4. swap(int[ ] arr, int i, int j): 这个函数用于交换数组中两个位置的元素。在main函数中,创建了一个待排序的数组,然后调用quickSort函数对其进行排序,最后打印排序后的数组。如果想知道排序后的结果是什么,你可以运行这段代码并查看控制台输出。这个例子中,输入的数组是 [9, 5, 1, 8, 3, 7, 4, 2, 6],经过快速排序后,输出的结果是 [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

以上就是通过FuncGPT(慧函数)用Java写的一个快速排序算法的基本流程。当然,实际使用中,我们还需要考虑一些其他的因素,比如如何选择一个好的基准元素(这通常会影响排序的效率),以及在内存有限的情况下如何处理大型数组(这通常会影响程序的稳定性)。而这些,采用代码编写最佳实践及大规模机器联合训练的方式诞生的FuncGPT(慧函数)都已经帮你实现。我们将以上代码放到可以媲美ChatGPT—4的文心一言中,得到的评价是:这个Java代码实现了一个结构清晰、易于理解和使用的快速排序算法(详情见截图)。

 

作为全栈式全自动软件开发工具飞算SoFlu软件机器人的一个重要组成部分,FuncGPT(慧函数)支持所有类型函数创建。通过自然语言描述Java函数需求,实时生成高质量、高可读性的Java函数代码。生成代码可直接复制到IDEA,或一键导入Java全自动开发工具函数库。目前开发免费使用,下载链接:https://suo.im/76V9w

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部