![cover](https://img-blog.csdnimg.cn/direct/4ff2f4b198574c3486d69ef2be928300.jpeg)
快速排序算法
通过选择一个基准值,将数组分割成两部分,并对这两部分分别进行递归排序,最终完成整个数组的排序。
·
💖The Begin💖点点关注,收藏不迷路💖
|
1、实现思想
通过选择一个基准值,将数组分割成两部分,并对这两部分分别进行递归排序,最终完成整个数组的排序。
快速排序是一种高效的排序算法,其平均时间复杂度为 O(nlogn),最坏情况下的时间复杂度为 O(n^2)。
2、代码实现
package csdn;
import java.util.Scanner; // 导入Scanner类,用于接收用户输入
public class QuickSort { // 定义名为QuickSort的类
public static void main(String[] args) { // 主方法
Scanner scanner = new Scanner(System.in); // 创建Scanner对象,用于接收用户输入
// 询问用户输入数组的长度
System.out.print("请输入数组的长度:");
int length = scanner.nextInt(); // 从用户输入中读取数组长度
// 创建数组
int[] array = new int[length]; // 创建指定长度的整数数组
// 询问用户输入数组元素
System.out.println("请输入数组元素:");
for (int i = 0; i < length; i++) { // 循环读取数组元素
System.out.print("第 " + (i + 1) + " 个元素:");
array[i] = scanner.nextInt(); // 从用户输入中读取数组元素
}
// 输出原始数组
System.out.println("原始数组:");
printArray(array); // 调用printArray方法打印数组
// 调用排序方法
sort(array); // 调用sort方法对数组进行排序
// 输出排序后的数组
System.out.println("排序后的数组:");
printArray(array); // 调用printArray方法打印排序后的数组
scanner.close(); // 关闭Scanner对象,释放资源
}
// 打印数组元素的方法
public static void printArray(int[] array) { // 定义打印数组元素的方法
for (int num : array) { // 遍历数组
System.out.print(num + " "); // 打印数组元素
}
System.out.println(); // 换行
}
// 快速排序方法
public static void sort(int[] a) { // 定义快速排序方法
sort(a, 0, a.length - 1); // 调用快速排序的辅助方法
}
// 快速排序的辅助方法(主要排序思路)
public static void sort(int[] a, int low, int high) { // 定义快速排序的辅助方法
if (low >= high) return; // 递归结束条件
int i = low; // 定义指针i
int j = high; // 定义指针j
int pivot = a[i]; // 选取基准值
while (i < j) { // 循环直到i >= j
while (i < j && a[j] >= pivot) { // 从右向左找到第一个小于基准值的元素
j--;
}
while (i < j && a[i] <= pivot) { // 从左向右找到第一个大于基准值的元素
i++;
}
if (i < j) { // 若i < j,则交换a[i]和a[j]
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[low] = a[i]; // 将基准值放到正确的位置
a[i] = pivot;
sort(a, low, i - 1); // 对基准值左边的子数组进行递归排序
sort(a, i + 1, high); // 对基准值右边的子数组进行递归排序
}
}
- 选择基准值: 从数组中选择一个基准值(pivot),通常选择第一个元素。
- 分区操作: 将数组分割成两个子数组,使得左子数组中的元素都小于基准值,右子数组中的元素都大于基准值。这个过程称为分区操作。
- 递归排序: 对左子数组和右子数组分别进行快速排序,直到数组长度为1或0,表示子数组已经有序。
- 合并结果: 最后,将所有的子数组合并起来,整个数组就变成有序的了。
💖The End💖点点关注,收藏不迷路💖
|
更多推荐
所有评论(0)