简单的自我介绍

• 我是一名双非大二学生，目前学习方向为Java后端，快速学习并学到了springboot，并和实验室的朋友做了一个简单的微信小程序，想在寒假找份有关互联网的实习，打算海投，城市和公司暂时没有特别强烈的意向，我会再次牢固的复习一遍Java整套学习知识，并且开始补充算法知识刷算法题，来备战这次寒假实习，并且想报名参加蓝桥杯Java B组的比赛，希望我的一些学习笔记能为你带来一些帮助，这次给大家带来的是快速排序的算法学习。

• 今天状态还行，一直在赶瑞吉外卖的那个项目，今天再努努力，明天就可以结束了1.0版本了，之后要赶紧抓紧算法学习的进度了，蓝桥杯的比赛的报名也迫在眉睫了，有点难受就是如果没被封在宿舍，现在的我应该天天勤勤恳恳在实验室的工位上疯狂赶进度呢，预计这次封应该是要封一学期了。可能是我自己的问题，我感觉大学越上越难受，在高考那年，我是多么憧憬大学生活的，多么想逃离痛苦的高中生活的，到后来才发现原来自己曾经那么想逃离的生活却是令自己朝思暮想的；自己曾经那么憧憬的生活却是令自己痛苦不堪的。当然上了大学的我也没有了高中那般冲劲了，可能是了解到了了社会真实的一面，自己慢慢也在被改变....不能再说这种消极话了，人被封长时间，对精神状态真很摧残，还是要积极，即使环境如此，自己能多做一点就多做一点把，尽管自己能做的事情很小。

什么是快速排序

快速排序是一种高级的排序算法，平均时间复杂度可以达到O(nl o g 2 n log_2nlog
2
​
n)，它的主要思想是找一个基准点大于基准点的放在基准点的一端 小于基准点的放在基准点一端 每一端重复这个过程 用递归实现。

总思想：每趟的基准点不变 最后交换基准点

实现快速排序有两个主流的方法：

1.单边循环法：选取最右端作为基准点，有两个变量i j，i用于维护小于基准点元素的边界，也就是每次交换的目标索引， j负责找到比基准点小的元素，一旦找到与i进行交换，最后i在与基准点进行交换 完成一趟排序。

2.双边循环法：选取最左端作为基准点，有两个变量i j，i负责从左向右找到比基准点大的元素， j负责找到比基准点小的元素，一旦找到j与i进行交换，最后基准点再与i j重合点进行交换 一趟排序完成。

算法原理

对数列{5,3,7,2,9,8,1,4}进行升序快速排序。

单边循环法(最右端为基准点):

i=0与j=1进行交换 i=1与j=3进行交换 i=2与j=6进行交换 i=3与r=7进行交换

3 2 1 4 9 8 7 5

i=0与r=2进行交换

1 2 3 4 9 8 7 5

i=1与j=1进行交换 i=2与r=2进行交换

1 2 3 4 9 8 7 5

i=4与r=7进行交换

1 2 3 4 5 8 7 9

i=5与j=5进行交换 i=6与j=6进行交换 i=7与r=7进行交换

1 2 3 4 5 8 7 9

i=5与r=6进行交换

1 2 3 4 5 7 8 9

双边循环法(最左端为基准点):

基准点下标0 基准点值5

i=2与j=7进行交换 i=4与j=6进行交换 i=4与j=4进行交换 l=0与j=4进行交换

1 3 4 2 5 8 9 7

基准点下标0 基准点值1

i=0与j=0进行交换 l=0与j=0进行交换

1 3 4 2 5 8 9 7

基准点下标1 基准点值3

i=2与j=3进行交换 i=2与j=2进行交换 l=1与j=2进行交换

1 2 3 4 5 8 9 7

基准点下标5 基准点值8

i=6与j=7进行交换 i=6与j=6进行交换 l=5与j=6进行交换

1 2 3 4 5 7 8 9