Java语言面试中八大常见排序算法 _算法

概述
排序分为内部排序和外部排序，内部排序是待排序的元素全部放在内存，并在内存中调整它们的顺序。外部排序是部分元素放到内存中，在内外存间调整元素的顺序。我们通常说的八大排序直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序都是内部排序，下面来具体介绍这八种排序的如何用JAVA实现，以及它们所需的时间复杂度和空间复杂度。

直接插入排序基本思想：将一个待排序的元素插入到已经排好序的序列中，如果待排序的元素与有序序列的中的某个元素相等，则把待排序元素插到该元素后面。
算法实现：

文章插图

时间复杂度：
直接插入排序是稳定的排序，其时间复杂度是O(n^2) 。
说明：稳定的排序是指相等的元素经过排序后，其相对位置没有发生改变。
说明：如果待排序的元素是正序（从小到大排列），每插入一个元素只需比较一次，这样时间复杂度就是O(n) 。反之，如果待排序的元素是逆序（从大到小排列），当插入第i个元素时，需要比较i次，这样时间复杂度是O(n^2) 。

希尔排序基本思想：
希尔排序实质上是一种分组插入排序，其先将整个待排元素序列分割成若干个子序列（由距离为d的元素组成）分别进行直接插入排序，然后依次减少距离d再进行排序，当距离为1时，再对全体元素进行一次直接插入排序。
算法实现：

文章插图

时间复杂度：
希尔排序中相同的元素可能在各自组的插入排序中移动，最后其稳定性会被打乱，所以希尔排序是不稳定的，其时间复杂度是O(nlogn) 。

简单选择排序基本思想：
在n个待排序的元素中找取最小的元素与第一个元素交换位置，然后在n-1个元素中找取最小的元素与第二元素交换位置，直到n=1为止。
算法实现:

文章插图

时间复杂度:
简单选择排序是不稳定的排序，其时间复杂度是O(n^2) 。
不稳定说明：
假设待排元素序列是：6 ， 4 ， 6 ， 7 ， 2 ， 9 ，第一次排序后，序列变成了2 ， 4 ， 6 ， 7 ， 6 ， 9 ，我们可以发现，经过一次排序后，位置一的6调整到位置三的6的后面，所以简单选择排序是不稳定的排序。

冒泡排序基本思想：
从待排序元素的倒数第一位开始向前遍历，如果当前元素比前面元素小，则交换位置。这样一次遍历下来，最小的元素冒泡到第一个位置了，然后，从倒数第二位、第三位...开始向前遍历，重复上面的过程，直到元素有序。
算法实现:

文章插图

时间复杂度:
冒泡排序是稳定的排序，时间复杂度是O(n^2)

快速排序基本思想:
选择一个基准元素（通常选择第一个元素或者最后一个元素），通过一次排序将待排序列分为两部分，一部分都比基准元素小，另一部分都比基准元素大，然后再按此方法对这两组数据分别进行快速排序，直到待排序列有序。
算法实现:

文章插图

时间复杂度:
快速排序是不稳定排序，时间复杂度是O(nlogn)

堆排序基本思想:
堆的概念：
n个元素的序列{k1 ， k2 ， …,kn}当且仅当满足下列关系之一时，称之为堆。
情形1：ki <= k2i 且ki <= k2i+1 （最小堆）
情形2：ki >= k2i 且ki >= k2i+1 （最大堆）
其中i=1,2,…,n/2向下取整;
堆排序：
把待排序的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个最大堆，这时堆的根节点数最大。然后，将根节点与堆的最后一个节点交换，并对前面n-1个数重新调整使之成为堆，依此类推，最后得到有n个节点的有序序列。