算法（三）初等排序后篇[选择和希尔排序]
相关文章
算法（一）时间复杂度
算法（二）初等排序前篇[插入和冒泡排序]
1.选择排序
根据上一篇文章讲到的插入排序和冒泡排序，我们把选择排序的数组也分为已排序部分和未排序部分。
图解选择排序
在用图来讲解选择排序之前，我们要先了解选择排序的规则。
选择排序的规则
就是重复执行以下的处理：
1.找出未排序部分最小值的位置min。
2.将min位置的元素与未排序部分的起始元素做对比，如果顺序错误则将它们进行就交换。
以数组a={5,4,8,7,9,3,1}为例，我们对其进行从小到大排序，排序过程如下图所示。
首先我们找到未排序部分最小的值a[6]=1和未排序的起始元素a[0]=5相比较，发现a[6]的值更小，则将两个数进行交换，以此类推。
最终得到的结果为a={1,3,4,5,7,8,9}
实现选择排序
接下来要实现插入排序，针对下图来定义变量。
如上图所示，i为循环变量，代表未排序部分的开头元素； j为循环变量，用来遍历未排序部分找出最小值min。
接下来我们用代码来实现选择排序，如下所示。
public class SelectionSort {
public static void main(String[] args) {
int a[] = {5, 4, 8, 7, 9, 3, 1};
ArrayUtils.printArray(a);
int b[] = selection(a);
ArrayUtils.printArray(b);
}
public static int[] selection(int[] a) {
int i, j, min, v;
int n = a.length;
for (i = 0; i < n; i++) {
//每次将未排序部分的首元素下标赋值给下标min
min = i;
//得到未排序部分的最小值的下标并赋值给min
for (j = i+1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
v = a[i];
a[i] = a[min];
a[min] = v;
}
return a;
}
}
其中负责打印数组的ArrayUtils类如下所示。
public class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("{");
int len=array.length;
for (int i = 0; i < len; i++) {
System.out.print(array[i]);
if (i < len - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
}
输出结果为：
{5, 4, 8, 7, 9, 3, 1}
{1, 3, 4, 5, 7, 8, 9}
选择排序复杂度
假设数据总数为n，则为了搜索未排序部分最小的的值需要(n-1)+(n-2)+(n-3)+……+1次比较，也就是n²/2+n/2次比较，因此时间复杂度为O(n²)。同样的，此前讲过的插入排序和冒泡排序的时间复杂度也是O(n²)。它们的区别就是：不含flag的冒泡算法和选择排序并不依赖于比较运算的次数，不受输入数据的影响，而插入算法却依赖于比较运算的次数，处理某些数据时会具有很高的效率。
2.希尔排序
在算法（二）初等排序前篇[插入和冒泡排序]这篇文章中，我们讲到了插入排序，对于大规模的乱序数组，插入排序会很慢，因为它只会交换相邻的元素，元素只能一点一点的从数组的一端移动到另一端。如果最小的元素在数组的末尾，则要将它移动到数组的开头则需要进行n-1次移动。
希尔排序原理
希尔排序改进了插入排序这一问题，它交换不相邻的元素对数组进行局部排序，并最终用插入排序将局部有序的数组进行排序。
希尔排序的思想就是使得数组中任意间隔h的元素都是有序的，这样的数组可以成为h有序数组。这里拿数组a={4,8,9,1,10,6,2,5}为例，当h为4时，会将这个数组分为h个子数组。
从上图可以看到，我们根据h=4，将数组分为了四个子数组，分别是{4,10}、{8,2}、{1,5}、{10,3}。我们分别对这四个子数组进行局部排序，接下来对h进行递减操作，直到h为1，这样最后一次循环就是一个典型的插入排序。
实现希尔排序
我们将数组分为h个数组，我们将子数组的每个元素交换到比他大的元素前面去，只需要将插入排序的将移动元素的距离1改为h即可。这样希尔排序的实现就转换为了一个类似于插入排序但使用的增量不同的过程。
代码实现如下所示。
public class ShellSort {
public static void main(String[] args) {
int a[] = {4, 8, 9, 1, 10, 6, 2, 5};
ArrayUtils.printArray(a);
int b[] = shellSort(a);
ArrayUtils.printArray(b);
}
public static int[] shellSort(int[] a) {
int h = 1;
int n = a.length;
while (h < n / 3) //1
h = 3 * h + 1;
while (h >= 1) {
//增量为h的插入排序
for (int i = h; i < n; i++) {
int v = a[i];
int j = i - h;
while (j >= 0 && a[j] > v) {
a[j + h] = a[j];
j -= h;
}
a[j + h] = v;
}
h = h / 3;
}
return a;
}
}
注释1处的代码是为了得到h值，关于h选什么样的值是最好的，至今还未有定论，这里我们给出比较常用的h值为h = 3 * h + 1，也就是1、4、13、40、121、346、1093......，这些h值会根据数组的大小而改变。接着往下看，下面的代码则是一个增量为h的插入排序。不理解的同学可以查看算法（二）初等排序前篇[插入和冒泡排序]这篇文章中讲到的插入排序。
输出结果为：
{4, 8, 9, 1, 10, 6, 2, 5}
{1, 2, 4, 5, 6, 8, 9, 10}
希尔排序的复杂度
希尔排序的复杂度要根据h的值来进行计算，不同的h值会导致不同的复杂度，一般情况下，当h = 3 * h + 1时，希尔排序的复杂度基本维持在O(n^1.25)。
欢迎关注我的微信公众号，第一时间获得博客更新提醒，以及更多成体系的Android相关原创技术干货。
扫一扫下方二维码或者长按识别二维码，即可关注。
