java快排

最近想把大学学的东西捡些起来,所以从快排开始,网上找了些快排的资料,结果让我比较失望,没有写的比较靠谱的,很多人甚至自己都不测试就把代码往上贴,现在写一篇自己的,希望能给大家一些帮助

可以在oschina找到本文的源代码。

概念

快速排序是冒泡的优化,目前而言最快的排序算法,当然了,还有一些快排的优化,可以根据不同的排序对象给不同的排序算法。

Array.sort()工具方法

java.util.Array类下有些niubility的排序算法,我看了下int数组的排序代码,大概是这么回事:

如果数组比较小的话,直接快排。

这里的快排和本文说的二分法的快排还不一样,jdk中的快排是用多个基准数的快排,比较复杂。

如果数组比较大,就开始评估数组的是不是比较有序的还是根本就无序状态的,如果是根本无序状态,就用快排,如果是比较有序的,用归并排序。

自己实现快排

快速认知

我们用语言来形容一下快排算法的大概,首先我们需要知道,我们只要以一个数为基准数(这里就用第一个数),将数组中比这个数小的数放到基准数左边,大于等于的放基准数右边。之后,我们把基准数左边的若干个数看成一个初始数组,右边的若干个数看成另一个初始数组执行相同的步骤。

没错,就是递归。

划分数组

现在问题来了,我们怎么把数组中与基准数相比小的数放左边,大的放右边。

所以有一个方法叫“填坑”,这个方法其实蛮形象的。大概是这样:

首先我们有一个int类型数组

int[] array = new int[] { 5, 1, 7, 9, 2, 6, 3, 10 };

有一个指针lo指向第一个数,有一个指针hi指向最后一个数

  • 先拿到数组中第一个数作为基准数(pivot),也就是 5 ,拿出来放一边

这时候我们可以把lo指向的位置看成坑,里面是空的。

  • 然后hi指针从右开始往左遍历,直到找到一个比基准数小的数字停下来,这边是3,把这个数字放到刚才的坑里,也就是lo的位置,也就是第一个位置。

这时候hi指向position是6,lo的position是0,数组是这个状态:

3, 1, 7, 9, 2, 6, 3, 10

  • 右边hi已经好了,接下来是lo从左往右遍历,相反的,直到找个一个数比基准数大停下来,这里是7,position为2,把这个数字放在坑里,其实就是hi,position是6。

看下现在的各个变量状态:

hi的position是6,lo的position是2,数组是这样:

3, 1, 7, 9, 2, 6, 7, 10

  • 继续hi右向左,找到了2,继续填坑,坑在哪儿呢,就是position为2。

hi的position为4,lo的position为2,数组是这样:

3, 1, 2, 9, 2, 6, 7, 10

  • 继续lo左向右,比较幸运,第一个就是,9。填坑。

这时候hi的position为4,lo的position为3,数组是这样:

3, 1, 2, 9, 9, 6, 7, 10

  • 然后我们再继续,移动hi,我们发现,这时候lo等于hi了,这怎么办?
    我们认为这时候我们的一次遍历就结束了,但是,还需要一些收尾工作,我们把lo指向的数字(其实hi也可以,因为一样的),也就是position为3的坑填上我们的基准数,5。

那么数组现在就是这样的:

3, 1, 2, 5, 9, 6, 7, 10

我们神奇地发现,基准数5左边全是小于5的数,右边全是大于5的数!Perfect。

迭代排序

有了划分数组这块基石,我们只需要在这个基础上抽象出迭代的模型即可。

对于一个数组,我们只需要每次都以第一个数为基准划分好,一直划分到左边和右边的指针相等就可以了。这部分概念还是比较好理解的。

代码实现

划分数组的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* 给定一个数组,地位指针和高位指针<br>
* 以第一个数为基准分割为两部分 <功能简述>
*
* @param array
* @param l
* @param h
* @return 返回基准的位置
*/
public static int partition(int[] array, int l, int h) {
//拿到低位的数作为基准
int pivot = array[l];

while (l < h) {//l如果小于h就要一直循环下去

while (l < h && array[h] >= pivot) {//确保l<h而且当前指向数大于等于基准数
h--;
}
//直到减到有一个数小于基准数
//就让这个数填到左边的数这里
array[l] = array[h];

//然后开始从左往右遍历
while (l < h && array[l] < pivot) {////确保l<h,当前指向数小于基准数
l++;
}
//直到找到比基准数大的一个数
//就让这个数填到右边刚才已经填掉的数这里
array[h] = array[l];
}
//到这里l必然等于h
//基准数填到中间去
array[l] = pivot;
return l;
}

迭代的实现

1
2
3
4
5
6
7
8
public static void quickSort(int[] array, int l, int h) {
if (l >= h) {
return;
}
int mid = partition(array, l, h);
quickSort(array, l, mid - 1);
quickSort(array, mid + 1, h);
}

下一层次的的划分是以上一层次的中心点开始的

最后要说一句,快排这种算法jdk都帮我们实现了,而且实现地要比我们自己写的好,所以工作中直接调用封装好的方法就可以了,但是这种算法的思想我们是要牢牢记住的,所以了解这些算法并非完全没用。

写完收工~