萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

手撕快速排序-Java代码

发表于 2021-03-25 | 分类于 算法学习日记 | 0 | 阅读次数 266

手撕快排

复杂度和稳定性

时间复杂度:

  1. 最好:O(nlog2n)
  2. 最坏:O(n^2)
  3. 平均:O(nlog2n)

空间复杂度:O(log2n)

稳定性:不稳定

Java代码

public class QuickSort {

	int[] sortByRecursion(int[] array, int l, int r) {
		if(l == r) {  // 如果当前数组只有一个值,直接返回
			return array;
		}
		
		int left = l, right = r;  // 定义左右指针
		
		int temp = array[l];  // 备份分治点
		boolean flag = false;  // false:左指针不动,右指针动左移,←right              true:右指针不动,左指针右移,left→
		
		while (left != right) {
			if (flag) {  // 右指针不动
				if (array[left] > temp) {  // 如果左侧数字大于右侧数字
					array[right] = array[left];  // 右侧数字赋值为左侧数字
					flag = false;  // 指针换动
				} else {  // 如果左侧数字不大于右侧数字
					left++;  // 左指针右移
				}
			} else {  // 左指针不动
				if (array[right] < temp) {  // 如果右侧数字小于左侧数字
					array[left] = array[right];  // 左侧数字赋值为右侧数字
					flag = true;  // 指针换动
				} else {  // 如果如果右侧数字不小于左侧数字
					right--;  // 右指针左移
				}
			}
		}
		array[left] = temp;  // 把分治点赋值
		
		if (l < left - 1) {  // 递归,将分治点左侧的数组一次快排
			array = sortByRecursion(array, l, left - 1);			
		}
		if (right + 1 < r) {  // 递归,将分治点右侧的数组一次快排
			array = sortByRecursion(array, right + 1, r);
		}
		
		return array;
	}
	
	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		
		int[] arr = {5,6,89,7,48,15,65,32,8,15,84,9,33,4,
					 3,14,74,15,84,96,1,62,84,2,36,15,47,82,41,64,0,61};
		
		arr = qs.sortByRecursion(arr, 0, arr.length - 1);
		
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}
# 算法 # 手撕 # 快排
MySQL-InnoDB引擎的事务
手撕二路归并排序-Java代码
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持