数据结构-快速排序
看动画了解
【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-CSDN博客
一 介绍
快速排序法介绍:
快速排序(Quicksort)是对冒泡排序的一种改进。
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
二 思路
1 选定一个基准值，最好选定最左边或者最右边，选中间会给自己找麻烦。
2 确定两个指针left 和right 分别从左边和右边向中间遍历数组。
3 如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。
4 然后右边的指针再走，遇到小于基准值的数就停下来。
5 交换left和right指针对应位置的值。
6 重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。
三 代码实现
public class QuickSort {
// 主函数示例，用于测试快速排序算法
public static void main(String[] args) {
int[] array = {3, 6, 8, 10, 1, 2, 1}; // 初始化一个整型数组
quickSort(array, 0, array.length - 1); // 对数组进行快速排序
// 输出排序结果
for (int num : array) {
System.out.print(num + " ");
}
}
// 快速排序的主要方法，递归地对数组进行排序
public static void quickSort(int arr[], int left, int right) {
if (left >= right) {
return; // 如果左边界大于等于右边界，说明数组已经有序，直接返回
}
int baseIndex = quickSort1(arr, left, right); // 获取基准元素的索引
quickSort(arr, left, baseIndex - 1); // 对基准元素左边的子数组进行快速排序
quickSort(arr, baseIndex + 1, right); // 对基准元素右边的子数组进行快速排序
}
// 快速排序的分区方法，用于找到基准元素的正确位置
private static int quickSort1(int[] arr, int left, int right) {
int baseIndex = right; // 将基准元素设为最右侧元素
while (left < right) {
while (left < right && arr[left] <= arr[baseIndex]) {
left++; // 移动左指针，直到找到一个大于基准元素的元素
}
while (left < right && arr[right] >= arr[baseIndex]) {
right--; // 移动右指针，直到找到一个小于基准元素的元素
}
sort(arr, left, right); // 交换两个元素的位置
}
sort(arr, left, baseIndex); // 将基准元素放到最终位置
return left; // 返回基准元素的索引
}
// 交换数组中两个元素的位置
public static void sort(int arr[], int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}四 总结
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
原文地址：https://blog.csdn.net/2302_80490510/article/details/143483941
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！