Java实现快速排序及其动图演示
2023-12-15 04:45:22
????????快速排序(Quicksort)是一种基于分治思想的排序算法。它通过选择一个基准元素,将数组分为两个子数组,其中一个子数组的所有元素都小于基准元素,另一个子数组的所有元素都大于基准元素,然后递归地对这两个子数组进行排序。
具体步骤如下:
- 选择一个基准元素,通常选择数组中的第一个元素。
- 将数组分为两个子数组,一个是小于基准元素的子数组,一个是大于基准元素的子数组。可以使用两个指针分别从数组的两端开始,然后向中间遍历,当两个指针相遇时停止,并交换相遇位置的元素。
- 递归地对两个子数组进行步骤1和步骤2的操作,直到子数组的长度为1或者为空。
- 合并排序好的子数组,此时整个数组已经有序。
????????快速排序的时间复杂度为O(nlogn),其中n是数组的长度。最坏情况下的时间复杂度为O(n^2),但是通过合理地选择基准元素,可以避免最坏情况的发生。快速排序是一种原地排序算法,不需要额外的空间。
下面是用Java实现快速排序的代码示例:
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 1, 6, 3, 9, 4, 7};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序结果:");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
}
????????代码的思路是采用了分治法的思想。首先选择一个基准元素,通常是数组的第一个元素。然后将数组分为两部分,一部分是小于等于基准元素的元素,一部分是大于基准元素的元素。接着对这两部分分别进行快速排序,直到每个部分只剩下一个元素或者没有元素。
????????在quickSort
方法中,首先判断low
是否小于high
,如果是的话,调用partition
方法划分数组,并在基准元素的位置将数组分为两部分,然后再分别对这两部分进行快速排序。
??partition
方法使用两个指针low
和high
,分别从数组两端开始向中间移动。在移动过程中,如果遇到比基准元素小的元素,则将其放到左边,否则将其放到右边。最后将基准元素放到合适的位置,并返回该位置的索引。
????????以上代码可以按照快速排序的思想对给定的数组进行排序。
输出结果为:1 2 3 4 5 6 7 8 9。
文章来源:https://blog.csdn.net/m0_37649480/article/details/134989918
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!