浅谈常见排序算法实现原理及性能优化

◆

(河南省郑州市第十一中学)

1行业背景

随着计算机技术和网络技术的高速发展，如今越来越多行业都希望借助计算机的能力进行发展，这也就衍生出了互联网行业和软件行业的急速扩张。目前市场上需要大量的计算机人才，并且薪资待遇都很可观。除了计算机相关专业人才，其他专业的人才同样大量地投入IT市场。为了适应目前膨胀的IT环境，计算机编程语言也从最初的指令语言，汇编语言发展到目前各种各样的高级语言。

高级语言的出现使得人们经过短时间的培训就能够进行简单的软件开发，所以现在大家戏称普通程序员为“码农”。举个简单的例子，在Java语言中，简单的Arrays.sort()方法，就可以对一个数组进行排序。但是这句代码的背后隐藏着什么，它是如何实现的，它的性能如何，对于使用它的人来说可能未必清楚。

本文将通过Java语言对常见的排序算法的实现原理进行剖析，介绍不同的排序算法的适用场景和性能高低。

2 Java语言介绍

Java语言是一种开源的高级编程语言，封装性很强。Java代码最终会编译成class文件，在Java虚拟机上执行的，所以Java是不受操作系统的限制的，具有跨平台特性，是目前业界非常流行的一门语言。

由于Java是一门高级程序语言，所以使用Java的程序员可以调用很多Java基础包中或是其他人编写的工具类中很简单的方法完成较为复杂的功能。比如在上一节提到的对数组排序的方法。Java语言令软件开发的门槛降低了很多，使更多的人可以快速成为Java开发者。

3常用排序算法简介

3.1冒泡排序

冒泡排序是一个相当经典的排序算法，因为它更接近于人类直观的排序方式。它的排序思想如同它的名字，通过两两交换，将数字像水中的泡泡一样，有序地冒出来。它的最佳时间复杂度是O(n^2)。

3.2快速排序

快速排序虽然名为“快速”，但它未必是最快的排序算法，因为在不同的场景下，排序算法的性能是会受到影响的。但总体上来讲，快速排序的性能还是不错的。它采用了分而治之和递归的思想，使数组不会被多次循环嵌套遍历，在多数场景下，会大大提升排序的效率和性能。它的最佳时间复杂度为O(nlgn)。

3.3插入排序

插入排序不能说是一个非常好的排序方法，因为它的思想较为古板，但却非常好理解。他将数组中的数字分为有序部分和无序部分，不断从无序部分将数据插入有序部分中，并且插入后依然有序，这就需要每次都找到数据要插入的位置。如果数组本来就是有序的，那么此时的复杂度为O(n)；如果数组本来是倒序的，那么插入排序的时间复杂度就为O(n^2)。插入排序较适应于元素少的数组进行排序。

3.4选择排序

选择排序应该是最为简单直观的排序方法了，它每次都遍历数组，从中选择出最大(最小)的元素，放在数组的第一位，直到所有元素全部排序完成。选择排序在不同的场景下都会执行相同次数的遍历，所以性能不是很高。它的时间复杂度是O(n^2)。

4排序算法原理剖析

以上排序方法中，插入排序和选择排序的原理都较为直观，本文不对其进行过多的介绍。下面主要对冒泡排序和快速排序算法进行深度地剖析。

4.1快速排序原理研究

快速排序由于时间复杂度为O(nlgn)，排序效率较高，因此经常被采用，再加上快速排序的思想——分治法也非常实用，因此很多知名软件公司，如腾讯、微软都会在笔试或面试中对“快速排序”进行提问。

快速排序的基本思想是：

1.先从数列中取出一个数作为基准数。

2.将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步，直到各区间只有一个数。

以下是快速排序的算法模拟过程，待排序数组如下：

首先定义变量：i，j，X，其中i是指向数组起始位置的游标值，j是指向数组末尾的游标值。X为基准数。

(1)初始状态下：i=0;j=9;X=72。

(2)从数组末尾开始找比基准数小的数，找到游标位置在8的时候，值47小于基准值72。此时将0位置的数置为47，i加1。此时数组的8位置被空了下来，就要从左边开始找比基准数大的数字去填充8位置。此时找到位置3的值86大于基准值72。这时就将8位置的值置为86，j减1。

(3)此时的i=3，j=7，X=72。

(4)位置3被空下来，就要从j的位置开始找比基准值小的数，找到位置5的值40比基准值小，此时将位置3的值置为40，i加1。

(5)此时i=4，j=5，X=72。

(6)继续从i开始找比基准值大的数，当i加1等于j时，此次排序结束。数组为：

可以看出位置5前的数都比72小，后面的数都比72大。因此再对位置0到4和位置6到9这二个子区间重复上述步骤就可以将数组排序了。

4.2冒泡排序原理研究

冒泡排序非常容易理解，设数组长度为n。

(1)从第一个数开始比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

(2)这样对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第n-1个位置。

(3)n=n-1，如果n不为0就重复前面二步，否则排序完成。这样就可以将一个无序的数组排序。

5冒泡排序算法性能优化

5.1第一次优化

在第四节中，本文已经用Java代码实现了冒泡排序的排序功能。但是可以看出原数组a中的后半部分已经是排序状态，其实不必要循环20次，可能在某次排序后数组已经是有序状态了。所以就要考虑进行性能优化。

我们可以试想，如果某次排序中没有交换元素位置的事件发生，那么就可以认为是该数组已经排序成功了，就不需要在进行排序。我们对冒泡排序进行了如下优化：

可以看出效果很明显，在循环了5次后，就已经是有序数组了，程序便停止排序工作。

5.2第二次优化

在5.1节中对冒牌排序做了部分优化，使得排序的循环次数从20次减少到了5次。可以说减少了3/4的工作量，性能提升非常大。但是同时我们发现了另一个问题，虽然5.1节中的程序使循环次数减少了，但是每次的内部循环次数依然没有变化，每次循环还是要对比到最后一个数为止。

我们试想，如果数组的后半部分已经是有序的数组了，那么我们只要记录上一次循环的最后一次交换的位置，在本次循环时，只要将元素“冒”到该位置，就可以避免每次循环中都要对比到最后一个数。我们对冒泡排序进行了第二次优化：

可以看出，与上次优化一样，程序只循环了5次就结束了排序工作，但是相比于第一次循环，后几次循环的内部循环数骤减，又一次提升了排序的性能。

6总结

本文通过介绍了几种常见的排序算法的思想和时间复杂度，反映出在计算机世界中，任何一个细小的地方都是可以用心去研究其内涵的。通过介绍了冒泡排序的性能优化方案，能够看出，即使是同一种思想的算法，只要掌握了算法的核心原理，就可以设法提高其性能。

对于一些简单的程序来讲，选择哪一种算法来排序数据可能对程序的执行时间和结果都不会有太大的影响，甚至有时可以忽略不计。但是对于计算量巨大的程序来讲，不合适或者性能较低的算法可能就会严重影响程序的整体性能了。所以在我们学习计算机技术的过程中，要知其然，更要知其所以然，这样才能更好地了解计算机知识。

参考文献：

[1]唐红杰.Java语言程序设计之Java基本语法的教学研究[J].软件，2014，(06) ：23-24.

[2]刘建科，冯媛媛.快速排序算法的教学要点与方法探讨[J].电脑知识与技术，2016，(6X) ：117-118.

[3]程妮.C语言中冒泡排序算法的教学设计与分析[J].现代计算机，2016，(10) ：59-63.

[4]黄福员，聂瑞华.冒泡排序算法的改进[J].计算机技术与发展，2003，(11) ：26-27.