基础算法|7 希尔排序 HDU 1425
我们从最初的冒泡排序算法，到上篇文章的折半插入排序算法，我们一共学习了5种排序算法，相信以大家的聪明才智肯定都消化了^_^。在本篇文章中，我们又将学习第6种排序算法——希尔排序算法。那就让我们直奔主题吧。
希尔排序
让我们回想一下直接插入排序算法，是不是每次都是讲一个待排序的元素按顺序插入到一个有序序列中。那我们想，如果整个待排序的序列都是"基本有序"的，而且元素数量较少，是不是直接插入排序的执行效率会更高呢？显然，这是肯定的，希尔排序就是通过这种思想来改进直接插入排序算法。
希尔排序的算法思想
希尔排序通过一个增量序列（最后一个增量必须为1），按逐个增量将待排序序列划分为若干个组，然后对每个组中的两个元素进行排序（第一次改进，使待排序元素数量较少），这样通过每个增量划分成的组通过排序之后，整体序列就成了"基本有序"了（第二次改进，使整个待排序序列整体有序），然后当增量为1时，对整体在进行一次直接插入排序，即得到了有序序列。
tip：增量是指元素间的间隔数，比如序列[4,2,3,6]，4与6的增量就是3，因为间隔数为3。
是不是有点难以理解，没事，让我们来个例子演示一下。
希尔排序的实现过程
例如，我们要对序列[8,6,10,13,5,7]进行希尔排序，我可以选取增量序列，d1=3，d2=1。（tip：增量的选取没有明确的规定，笔者较喜欢奇数的增量，只要保证最后一个增量为1即可）。按第一个增量d1分组，我们可以分为3组——8与13，6与5,10与7（间隔数均为3），对每个组进行一次排序，8小于13所以8和13的位置不变；6大于5，所以6与5交换位置，得到序列[8,5,10,13,6,7];同理10大于7，交换位置得到序列[8,5,7,13,6,10]。这样通过第一个增量排序后，我们得到了一个基本有序的数列。之后的增量重复上述操作，直到最后一个增量为1时，对整体在进行一个直接插入排序即可。
代码实现
public static void shellSort (int[] a){
int d1 = a.length/2; //取第一个增量
if(d1 %2 ==0){ //如果为偶数，则自减变为奇数
d1 --;
}
for(int i=d1;i>=1;i=i-2){ //将第一个增量逐次减2
if(i == 1){ //若增量为1，则对整个数列直接插入排序
straightInsertSort(a);
break;
}
for(int j=0;j<i;j++){ //每次将序列划分为增量值的组数（例如增量为3，则分为3组），然后对每个组排序
if(a[j]>a[j+i]){ //若前面的数大于后面的数
a[j] = (a[j]+a[j+i]) - (a[j+i] = a[j]); //将两数进行交换
}
}
}
}
public static void straightInsertSort(int[] a) {
int elements = 1; //记录结果集中元素的个数,起初只有a[0]这一个元素
for(int i=1;i<a.length;i++){ //从a[1]开始逐个插入
int j;
for(j=0;j<elements;j++){ //遍历结果集，逐次与a[i]作比较
if(a[j] > a[i]){ //若a[j] >a[i]，则把结果集从最后位置(即a[elements-1])到j位置逐个向后移动一个位置
int temp = a[i]; //将要插入的值保留到temp中
for(int k =elements-1;k>=j;k--){
a[k+1] = a[k];
}
a[j] = temp; //将要插入的值插入到j位置
elements++; //结果集元素的个数加1
break;
}
}
if(j == elements){ //说明结果集中的元素都小于等于a[i]，即将a[i]的值插入到末尾
a[elements] = a[i];
elements++;
}
}
}
</elements;j++){ </a.length;i++){ </i;j++){ 让我们来测试一下我们的算法吧
public static void main(String[] args) {
int[] a = new int[]{8,10,6,19,17,3,13,16};
shellSort(a);
for(int i :a){
System.out.print(i+" ");
}
}
我们又来到了我们的老规矩时间，上题~
HDU 1425 sort
Problem Description
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。< p=""></n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。<>
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input
5 3
3 -35 92 213 -644Sample Output
213 92 3分析：是不是感觉so easy呢~只要我们先对这个序列进行希尔排序，然后从后往前输出m个数即可。
代码实现：
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n, m; // 输入元素数量n，和输出前m大的数中的m
n = input.nextInt();
m = input.nextInt();
do {
if (n <= 0 || n >= 1000000 || m <= 0 || m >= 1000000) {
System.out.println("请重新输入");
n = input.nextInt();
m = input.nextInt();
}
else{
break;
}
} while (true);
int[] a = new int[n];
for (int i = 0; i < n; i++) { // 输入元素
a[i] = input.nextInt();
if(a[i]<-500000 || a[i]>500000){
System.out.println("请重新输入：");
a[i] = input.nextInt();
}
}
shellSort(a);
for (int i = n - 1; i >= n - m; i--) {
System.out.print(a[i] + " ");
}
}让我们来测试一下吧
总述
本篇文章我们学习了第6种排序算法——希尔排序，我们可以将其与之前所学习的算法进行比较式学习，这样学习的效率的更佳呢ヾ(◍°∇°◍)ﾉﾞ
点赞的时候，请宠溺一点