猫史档案馆

有的时候需要数据排序，但是排序有很多种方法，应该选哪种呢？

 

其实很简单：用内置函数

array.sort()

 

欸发错了。。

 

//before main()
import java.util.Arrays;

//.......

//in main()

Arrays.sort(arr);

 

 

但是，你们知道快速排序吗？（知道的大佬可以出门右转）

快速排序的基本流程见下图

 

白色：待排序

红色：枢纽元素

绿色：（虚拟的）空位

黄色：需要交换

蓝色：已排序（到达正确位置）

箭头i和j：快慢指针（元素与枢纽元素比较）

 

看完流程，我们来写代码。

 

首先看结构

 

 

然后是基本的程序入口

 

可以看到，有一个qui_sort，没错，打少了"ck"。因为qui_sort是程序本体。

 

现在，我们把数组最后一个元素作为枢纽元素（如图）

 

但是按照上面的图，我们不仅要排序，还要把枢纽元素位置返回，并进行递归操作。

如下图，假设有一个函数getmid这个函数执行了图中快慢指针查找并交换，然后返回i的位置。

因为程序设计，i需大于j则停下。枢纽元素前的部分的结尾应为i的位置-1，枢纽元素后的部分开头为i的位置。

 

接下来就是getmid部分。

函数签名int getmid(int[] array,int start,int end)

 

i，j指针和pivot枢纽：

 

首先我们需要一个while循环，判断条件i<=j。当i>j时停止。

 

图中搜索规则为：当i找到大于pivot的元素时停止，当j找到小于pivot的元素时停止

（即找到不该在此的元素，并与对面交换）

没有初始化，也没有循环体，要的只是将i，j迭代。

 

当找好目标或搜索完毕时，进行处理

 

（另外说一句，t m p这个变量是提前定义好的，作临时变量使用）

 

最后：返回枢纽元素位置

 

 

随便来测试一下：

 

结果：

 

别问为啥发py专区