今天学习了一下 Java 数组的相关操作,包含排序和查找,现在先将排序记录巩固一下。
常用并且比较重要的几种排序:插入排序希尔排序快速排序归并排序冒泡排序选择排序

一、插入排序

1. 插入排序算法思想

1) 普遍思想
插入排序的算法是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

2) 我的理解与分析
我最初看到上面的思想,就是一脸懵逼,读都读不懂,又去找了很多资料,才能理解那么一点点,所以这里用通俗一点的话来解释:

假设有一个数组:

int[] arr = { 22, 11, 10, 55, 44 };
  • 第 0 个元素 22 看作已经排好序;
  • 取出第 1 个元素 11,在已经排序的元素序列中(第一步的 22)从后向前扫描;
  • 如果新元素 11 比已排序的元素 22 小,就把 22 往后挪,并将 11 插入到前面。这个时候数组应该如下:
    int[] arr = { 11, 22, 10, 55, 44 }
    
  • 接着在取出第 2 个元素 10,与第一个元素 22 相比,如果比第一个元素小,就插入到 22 之前。这个时候数组应该如下:
    int[] arr = { 11, 10, 22, 55, 44 }
    
  • 10 插入后继续与前面的元素相比,小则插入,大则不动。这个时候数组应该如下:
    int[] arr = { 10, 11, 22, 55, 44 }
    
  • 取出第 3 个元素继续比较……

插入排序的特点:越有序,操作的次数越少,效率越高。

2. 算法图解附视频

insertSort

视频 点此查看

3. 算法代码

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = { 11, 22, 10, 55, 44 };
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {  // 从第一个元素开始遍历
            for (int j = i; (j > 0) && (arr[j] < arr[j - 1]); j--) {    // 条件:是否比前一个元素小,j-- 是为了挪位后再次与前一个元素比较
                int temp = arr[j];      // 把移动的元素暂时存起来
                arr[j] = arr[j - 1];    // 把大的元素往后挪
                arr[j - 1] = temp;      // 把小的元素放到前面
            }
        }
    }
}

二、希尔排序

1. 算法简介

希尔排序 是插入排序的改进版本。为什么是插入排序的改进版本呢?上面说过的插入排序,它是取出一个元素然后从后向前比较,如果小于就放到前面来,并且它的特点是 越有序,效率越高。对于插入排序,序列数据少的话还行,要是序列数据特别多,并且是无序,那么插入排序的效率就会很慢,所以就出现了一个希尔排序,使序列更 接近有序,这样的话,相对于插入排序操作数据较大的时候要快一点,不过它最终属于插入排序类中。

2. 算法分析

希尔排序,先将要排序的一组数据按某个增量 d(n/2,n 为排序数的个数) 分成若干组(把相隔 d 的数据分为一组),并在各组内进行直接插入排序,然后再用一个较小的增量 (d/2) 对它进行分组,在每组中再进行插入排序,当增量减到 1 时,进行插入排序后,排序完成。

假设有一个数组:

int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
  • 先取一个增量 d = n/2 = 5,把每相隔 5 的数据分为一组,如下:
    第一组 ---> 49 -- 13
    第二组 ---> 38 -- 27
    第三组 ---> 65 -- 49
    第四组 ---> 97 -- 55
    第五组 ---> 76 -- 04
    
  • 每一组进行插入排序,如下:
    第一组 ---> 13 -- 49
    第二组 ---> 27 -- 38
    第三组 ---> 49 -- 65
    第四组 ---> 55 -- 97
    第五组 ---> 04 -- 76
    
  • 第一次的结果为:
    { 13, 27, 49, 55, 04, 49, 38, 65, 97, 76 };
    
  • 取第二个增量 d2 = d/2 = 3,把每相隔 3 的数据分为一组,如下:
    第一组 ---> 13 -- 55 -- 38 -- 76
    第二组 ---> 27 -- 04 -- 65
    第三组 ---> 49 -- 49 -- 97
    
  • 每一组进行插入排序,如下:
    第一组 ---> 13 -- 38 -- 55 -- 76
    第二组 ---> 04 -- 27 -- 65
    第三组 ---> 49 -- 49 -- 97
    
  • 第二次的结果为:
    { 13, 04, 49, 38, 27, 49, 55, 65, 97, 76 };
    
  • 取第三个增量 d3 = d2/2 = 1,把每相隔 1 的数据分为一组,这时开始直接插入排序即可,结果如下:
    { 04, 13, 27, 38, 49, 49, 55, 65, 76, 97 };
    

    增量 d 取值为奇数。

3. 算法图解附视频

shellSort

视频 点此查看

4. 算法代码

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        for (int d = arr.length / 2; d > 2; d /= 2) {
            for (int i = 0; i < d; i++) {
                insertSort(arr, i, d);
            }
        }
        insertSort(arr, 0, 1); 
    }

    // 插入排序
    public static void insertSort(int[] arr, int i, int d) {
        for (int a = i + d; a < arr.length; a += d) {    // a += d 
            for (int j = a; (j >= d) && (arr[j] < arr[j - d]); j -= d) {
                int temp = arr[j];
                arr[j] = arr[j - d];
                arr[j - d] = temp;
            }
        }
    }
}

-- 全文完 --

如果这篇文章对你有用,可以的话,随意打赏! 打赏
支付宝打赏 支付宝打赏
微信打赏 微信打赏
上一篇
下一篇