提供邯郸企业建网站/磁力天堂最新版地址

背景

排序是算法的入门知识，也是面试中经常会问到的问题。本文从JDK工具类 Collections的sort方法入手，动手编写代码，解析面试中经常会问到的排序算法。

准备

1. 生成一个从1-1000的整数集合，并随机打乱顺序；
2. 将乱序的集合保存到文件中，便于各种排序算法调用；
3. 定义一个读取文件中的乱序集合的静态方法；
4. 定义一个遍历打印集合的静态方法。

/*** 待排序数据源** @author zhuhuix* @date 2020-05-28*/
public class OriginalData {//将1000个随机打乱的整数到文件中，便于统一使用public static void main(String[] args) throws IOException, ClassNotFoundException {ObjectOutputStream stream = new ObjectOutputStream(new FileOutputStream("c:\\data.dat"));List<Integer> list = new ArrayList<>();for (int i = 1; i <= 1000; i++) {list.add(i);}// 随机打乱listCollections.shuffle(list);// 写入文件并保存stream.writeObject(list);// 遍历并打印乱序集合printList(getData());}// 读出文件中的随机打乱的待排序数据public static List<Integer> getData() throws IOException, ClassNotFoundException {ObjectInputStream stream = new ObjectInputStream(new FileInputStream("c:\\data.dat"));if (stream != null) {return (List<Integer>) stream.readObject();} else {return null;}}// 遍历打印输出集合public static void printList(List<Integer> list) {Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + ",");}System.out.println();}
}

输出如下：

Collections的sort方法

利用集合工具类Collections的sort方法对集合进行排序：

/**1. Collections.sort排序2.  3. @author zhuhuix3. @date 2020-05-28*/
public class ArraySort {public static void main(String[] args) throws IOException, ClassNotFoundException {List<Integer> list=OriginalData.getData();System.out.println("排序前：");OriginalData.printList(list);SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");Long start = System.currentTimeMillis();System.out.println("排序开始时间：" + sdf.format(start));Collections.sort(list);Long end = System.currentTimeMillis();System.out.println("排序结束时间：" + sdf.format(end));System.out.println("排序耗用了" + (end - start) + "毫秒");System.out.println("排序后：");OriginalData.printList(list);}
}

输出如下：

归并排序

为了解Collection.sort的实际排序算法，我们跟踪一下JDK底层

实际上该排序方法是一种优化的归并排序算法，具体可参见以下资料：

 4. This implementation was adapted from Tim Peters's list sort for5. Python, which is described in detail here:6.  8.   http://svn.python.org/projects/python/trunk/Objects/listsort.txt7.  10. Tim's C code may be found here:8.  12.   http://svn.python.org/projects/python/trunk/Objects/listobject.c

归并排序的算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

常规排序算法

冒泡排序

算法步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

/*** 冒沟排序优化** @author zhuhuix* @date 2020-05-28*/
public class BubbleSortOptimize {public static void main(String[] args) throws IOException, ClassNotFoundException {List<Integer> list=OriginalData.getData();System.out.println("排序前：");OriginalData.printList(list);SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");Long start = System.currentTimeMillis();System.out.println("排序开始时间：" + sdf.format(start));// 设置结束标志Boolean finished = true;for (int i = 0; i < list.size() - 1; i++) {for (int j = i + 1; j < list.size(); j++) {if (list.get(i) > list.get(j)) {int temp = list.get(i);list.set(i, list.get(j));list.set(j, temp);// 如果在此轮排序中发生中元素交换，则排序未结示finished = false;}}if (finished) {break;}}Long end = System.currentTimeMillis();System.out.println("排序结束时间：" + sdf.format(end));System.out.println("排序耗用了" + (end - start) + "毫秒");System.out.println("排序后：");OriginalData.printList(list);}}

输出如下：

选择排序

算法步骤：

1. 首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

/*** 选择排序** @author zhuhuix* @date 2020-05-28*/
public class SelectSort {public static void main(String[] args) throws IOException, ClassNotFoundException {List<Integer> list=OriginalData.getData();System.out.println("排序前：");OriginalData.printList(list);SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");Long start = System.currentTimeMillis();System.out.println("排序开始时间：" + sdf.format(start));// 选择排序过程for (int i = 0; i < list.size() - 1; i++) {int min = i;for (int j = i + 1; j < list.size(); j++) {if (list.get(min) > list.get(j)) {// 记录该轮比较的最小值元素的位置min = j;}}// 将最小值元素位置与当前值进行交换if (i != min) {int temp = list.get(i);list.set(i, list.get(min));list.set(min, temp);}}Long end = System.currentTimeMillis();System.out.println("排序结束时间：" + sdf.format(end));System.out.println("排序耗用了" + (end - start) + "毫秒");System.out.println("排序后：");OriginalData.printList(list);}}

输出如下：

快速排序

算法步骤

1. 从数列中挑出一个元素，称为 “基准值”;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；

/*** 快速排序** @author zhuhuix* @date 2020-05-28*/
public class QuickSort {public static void main(String[] args) throws IOException, ClassNotFoundException {List<Integer> list=OriginalData.getData();System.out.println("排序前：");OriginalData.printList(list);SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");Long start = System.currentTimeMillis();System.out.println("排序开始时间：" + sdf.format(start));Long end = System.currentTimeMillis();System.out.println("排序结束时间：" + sdf.format(end));List<Integer> sortList=quickSort(list,0,list.size()-1);System.out.println("排序耗用了" + (end - start) + "毫秒");System.out.println("排序后：");OriginalData.printList(sortList);}private static  List<Integer> quickSort(List<Integer> list, int left, int right) {if (left < right) {int partitionIndex = partition(list, left, right);quickSort(list, left, partitionIndex - 1);quickSort(list, partitionIndex + 1, right);}return list;}private static int partition(List<Integer> list, int left, int right) {int pivot = left;int index = pivot + 1;for (int i = index; i <= right; i++) {if (list.get(i) < list.get(pivot)) {swap(list, i, index);index++;}}swap(list, pivot, index - 1);return index - 1;}private static void swap(List<Integer> list, int i, int j) {int temp = list.get(i);list.set(i, list.get(j));list.set(j, temp);}}

输出如下：

结语

从以上例子对文件中生成的固定的乱序集合，分别进行归并、冒泡、选择、快速排序的结果来看，
1、快速排序性能最好，归并排序性能也不差，冒泡排序耗时最长；
2、归并排序空间复杂度最高，快速排序次之，冒泡和选择排序几乎不需要开辟新的空间；
3、归并、冒泡是稳定的排序算法；选择、快速是不稳定的排序算法（稳定性是指如果集合序列中存在相同值的元素，排序算法会破坏原有相同值元素的先后顺序）。