A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 123bayern 初级黑马   /  2018-12-13 16:26  /  686 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

我们知道排序主要有:插入排序、冒泡排序、归并排序、快速排序、堆排序、桶排序及外部排序等。
而通过调用工具类Arrays的类方法sort()可以实现排序。通过查看Arrays.sort()源代码,可以发现其排序是通过快速排序算法实现的,那么快速排序的原理是什么呢?这里简述其原理,感兴趣的同学可以更深入地分析快速排序实现的代码。
快速排序的原理如下:
在数组中选择一个称为主元(pivot)的元素,将数组分为两部分,第一部分的所有元素小于或等于主元,第二部分的所有元素都大于主元,然后分别对这第一部分和第二部分应用快速排序算法。如图:


伪代码为:
public static void quickSort(int [] list){
           if(list.length>1){
                select a pivot;
                partition list into list1 and list2 such that
                     all elements in list1 <= pivot;
                     all elements in list2 > pivot;
                quickSort(list1);
                quickSort(list2);
           }
    }
从伪代码看,快速排序算法主要体现了分治的思想以及递归调用的过程。
自然,主元的选择影响了该算法的实现过程。理想情况下,选择能将两部分平均划分的数据作为主元,但是这往往不太现实,这里把数组中第一个数作为主元(当然,也可以取数组中第一个数,中间数,最后一个数三者的中间值作为主元。)
下面演示本快速排序算法的过程:
5 2 9 3 8 4 0 1 6 7  选择5为主元,快速排序为:
4 2 1 3 0 5 8 9 6 7  现对第一部分4 2 1 3 0进行快速排序,4为主元,第二部分同理,这里不详述。快速排序为:
0 2 1 3 4 这里主元4只有第一部分0 2 1 3,现在对这个数组的第一部分0 2 1 3 进行快速排序,其中0为主元,排序为:
0 2 1 3 这里主元0只有第二部分2 1 3,现在对这个数组的第二部分2 1 3进行快速排序,2为主元,排序为:
1 2 3,这里2是主元,1为第一部分,3为第二部分,这两个数组只有一个数据,排序结束。结果为0 1 2 3 4,即4 2 1 3 0 5 8 9 6 7(5为主元)的第一部分已排好序,同理,第二部分也可以应用快速排序排序,结果为6 7 8 9,最后整个数组通过快速排序,排好序为:
0 1 2 3 4 5 6 7 8 9。
这里简述其原理过程,具体实现由于篇幅所限,暂不赘述,感兴趣的同学可以参考书籍《大话数据结构》。

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马