概述
排序分为内部排序和外部排序,内部排序是待排序的元素全部放在内存,并在内存中调整它们的顺序。外部排序是部分元素放到内存中,在内外存间调整元素的顺序。我们通常说的八大排序直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序都是内部排序,下面来具体介绍这八种排序的如何用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个节点的有序序列。
从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆结果。
说明:若想得到升序序列,则建立最大堆,若想得到降序序列,则建立最小堆。
算法实现:
时间复杂度:
堆排序是不稳定的排序,其时间复杂度是O(nlogn)。
基本思想:
是把待排序序列分为若干个子序列,每个子序列是有序的,然后再把有序子序列合并为整体有序序列。
算法实现:
时间复杂度:
归并排序是稳定的排序,其时间复杂度为O(nlogn)。
基本思想:
将所有待排序列(正整数)统一为同样的数位长度,数位较短的数前面补零。然后 ,从最低位开始,依次进行一次排序。这样,从最低位一直到最高位排序完成以后, 数列就变成一个有序序列。
算法实现:
时间复杂度:
基数排序是稳定的排序,其时间复杂度为O(d(n+r)),d为位数,r为基数范围。