龙源期刊网 http://www.qikan.com.cn

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

作者：张子瀚

来源：《中国校外教育(下旬)》2018年第02期

【摘要】随着计算机技术的快速发展，企业和用户对软件的要求不再是仅仅停留在满足基本需求。在此基础之上，企业和用户希望软件能够具有更好地健壮性和更高的性能。目前，计算机程序语言不断更新换代，程序员在编写代码时，透明度越来越高，可能表面上，但是却不了解底层的实现。通过使用Java编程语言，研究基础的几个排序算法的实现原理，并且讨论如何提高排序算法的性能。

【关键词】排序算法 高性能 Java 1行业背景

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

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

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

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

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

龙源期刊网 http://www.qikan.com.cn

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.先从数列中取出一个数作为基准数。

龙源期刊网 http://www.qikan.com.cn

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冒泡排序算法性能优化