手撕快速排序
2021/4/30 18:25:36
本文主要是介绍手撕快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
手撕快速排序
- 一. 快速排序动态图
- 二. 快速排序流程
- 三. Java代码实现
一. 快速排序动态图
时间复杂度为 O(NlogN) 不稳定
二. 快速排序流程
主要思想就是分治
- 确定分界点,去左边界 pivot=arr[left]。
- 调整区间 使小于等于pivot的值在左边,使大于等于pivot的值在右边。
- 当i==j两个指针相遇的时候,说明arr数组已经分为左右两个区间了。
- 再递归处理左右两个区间,重复上面三个步骤
- 递归出来的条件是区间只剩下一个元素
三. Java代码实现
注释给的非常详细了,自己debug领悟一下
package com.xizi.sort; import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Scanner; public class QuickSort { public static void main(String[] args) { int[] arr=new int[]{5,4,3,2,1}; int n=arr.length; quickSort(arr,0,n-1); for(int a:arr) { System.out.print(a+" "); } //底层使用双轴快速排序 Arrays.sort(arr); } //时间复杂度 O(NlogN) //1. 选取pivot //2. 划分,根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分 //3. 递归求解小于pivot和大于pivot的部分 public static void quickSort(int[] arr,int left,int right) { //边界判断 区间只剩下一个元素时直接返回 if(left>=right) { return; } //取左边界为分界点 int pivot=arr[left]; //下面使用do while循环 i先减1 j加1 int i=left-1,j=right+1; // 调整区间 使小于pivot的值在左边 大于pivot的值在右边 // 当i==j相遇 arr[]就会被划分为两个区域 while(i<j) { //从前往后找到第一次小于pivot的值 do {i++;}while(arr[i]<pivot); //从后往前找到第一次大于pivot的值 do {j--;}while(arr[j]>pivot); //然后进行交换 if(i<j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } //递归处理 左右区间 quickSort(arr,left,j); quickSort(arr,j+1,right); } }
这篇关于手撕快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南