黑马程序员技术交流社区

标题: 简述Arrays.sort()排序原理 [打印本页]

---

作者: 123bayern    时间: 2018-12-13 16:26
标题: 简述Arrays.sort()排序原理
我们知道排序主要有：插入排序、冒泡排序、归并排序、快速排序、堆排序、桶排序及外部排序等。
而通过调用工具类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。
这里简述其原理过程，具体实现由于篇幅所限，暂不赘述，感兴趣的同学可以参考书籍《大话数据结构》。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2