|
java初学--希尔(Shell)法排序和数组排序
Java 私塾跟我学系列——JAVA 篇
从前面介绍的冒泡排序法,选择排序法,插入排序法可以发现,如果数据已经大致排好序的时候,其交换数据位置的动作将会减少。例如在插入排序法过程中,如果某一整数 d不是较小时,则其往前比较和交换的次数会更少。如何用简单的方式让某些数据有一定的大小次序呢?Donald Shell(Shell 排序的创始人)提出了希尔法排序。
基本思路:先将数据按照固定的间隔分组,例如每隔 4 个分成一组,然后排序各分组的数据,形成以分组来看数据已经排序,从全部数据来看,较小值已经在前面,较大值已经在后面。将初步处理了的分组再用插入排序来排序,那么数据交换和移动的次数会减少。可以得到比插入排序法更高的效率。
示例如下:
- public class Test {
- public static void main(String[] args) {
- // 需要排序的数组,目前是按照升序排列的
- int a[] = new int[5];
- a[0] = 3;
- a[1] = 4;
- a[2] = 1;
- a[3] = 5;
- a[4] = 2;
- // shell法排序
- int j = 0;
- int temp = 0;
- //分组
- for (int increment = a.length / 2; increment > 0; increment /= 2)
- {
- //每个组内排序
- for (int i = increment; i < a.length; i++) {
- temp = a;
- for (j = i; j >= increment; j -= increment) {
- if (temp < a[j - increment]){
- a[j] = a[j - increment];
- }
- }
- }else{
- break;
- }
- }
- a[j] = temp;
- }
- }
- // 检测一下排序的结果
- for (int i2 : a) {
- System.out.println("i=" + i2);
- }
复制代码 运行结果:
i=1
i=2
i=3
i=4
i=5
如果你想要按照降序排列,很简单,只需要把:if (temp < a[j - increment])这句话修改成:if (temp > a[j - increment])就可以了。
数组排序
事实上,数组的排序不用那么麻烦,上面只是想让大家对一些基本的排序算法有所了解而已。在 java.util.Arrays 类中有一个静态方法 sort,可以用这个类的 sort 方法来对数组进行排序。
示例如下:
- public class Test {
- public static void main(String[] args) {
- // 需要排序的数组,目前是按照升序排列的
- int a[] = new int[5];
- a[0] = 3;
- a[1] = 4;
- a[2] = 1;
- a[3] = 5;
- a[4] = 2;
- //数组排序
- java.util.Arrays.sort(a);
- // 检测一下排序的结果
- for (int i2 : a) {
- System.out.println("i=" + i2);
- }
- }
- }
复制代码 注意:现在的 sort 方法都是升序的,要想实现降序的,还需要 Comparator 的知识。 |
|