插入排序（直接插入排序、折半插入排序、希尔排序）的实现(Java)与讲解

系统管理员 2023-09-24 21:17 92阅读 0赞

## 插入排序（直接插入排序、折半插入排序、希尔排序）的实现(Java)与讲解 ##

### 1、算法概述 ###

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法:直接插入排序、折半插入排序和希尔排序

### 2、直接插入排序 ###

2｜58369147
    1、将数组分为有序部分和无序部分，如上面，2一个数必然有序，后面一部分无序
    2、将后面的数依次插入到前面，即将5拿出来，插入到前面 于是成为。 
    	25｜8369147 -> 258|369147 -> 2358|69147
    3、依次重复上面的1和2，直到所有的全部有序

**时间复杂度**：最好情况下为O(n^2)，

**稳定的排序**

**适用于**：顺序存储和链式存储的线性表

**代码实现**

//1、直接插入排序
        public static int[] insertDirectSort(int[] arr){
        
            int l=arr.length;//数组长度
            int temp;//中间变量
            int j;
            for(int i=1;i<l;i++){
        
                //判断i与i-1这两个数的大小
                if(arr[i]<arr[i-1]){
        
                    temp=arr[i];//i更小，将i存入中间变量
                    for(j=i-1;j>=0&&temp<arr[j];j--){
        
                        //将大于arr[i]且小于等于arr[i-1]的部分往后移动
                        arr[j+1]=arr[j];
                    }
                    arr[j+1]=temp;
                }
            }
            return arr;
        }

### 3、折半插入排序 ###

折半插入排序主要是优化直接插入排序的查找部分，先利用折半查找找到需要插入的地方，然后再统一移动。

**时间复杂度**：O(n^2)

**稳定的排序方法**

**适用于**：仅用于顺序存储的线性表

代码实现：

//2、折半插入排序
        public static int[] halfInsertSort(int[] arr){
        
            if(arr == null ||arr.length == 0){
        //判断数组为空
                return null;
            }
            int n=arr.length;
            int i, j, low, high, mid,tmp;
            for (i = 1; i < n; i++)  //依次将a[2]~a[n]插入到前面已经排好序的列表
            {
        
                tmp = arr[i];  //将a[i]暂存到a[0]
                low = 0;
                high = i - 1;
                while (low <= high)
                {
        
                    mid = low + (high - low) / 2;  //取中间位置(利用low + (high - low) / 2求mid是为了防止整数溢出问题)
                    if (arr[mid] > tmp)  //查找左子表
                    {
        
                        high = mid - 1;
                    }
                    else  //查找右子表
                    {
        
                        low = mid + 1;
                    }
                }
                for (j = i - 1; j >= high + 1; --j)  //i - 1指待插入元素的前一个元素，即有序列表中所有大于待插入元素的最后一个元素；high + 1指有序列表中所有大于待插入元素的第一个元素
                {
        
                    arr[j + 1] = arr[j];  //统一后移元素
                }
                arr[high + 1] = tmp;  //插入操作
            }
            return arr;
        }

### 4、希尔排序 ###

基本思想：希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。

插入排序只能一个一个往后面移动，希尔排序可以跳着步长移动，小的数很快就会到达最前面。

人话：1，1+x，1+2x，1+3x ······一组，然后组内使用直接插入排序；第二组就是 2，2+x，······

一轮完成后，就减小x的大小，直到x=1；

**代码实现**：

//3、希尔排序
        public static int[] hillSort(int[] arr){
        
            //实现增量的变化
            for(int gap = arr.length / 2; gap > 0; gap /= 2) {
        
                for(int i = gap; i < arr.length; i++) {
        
                    for(int j = i - gap; j >= 0; j -= gap) {
        
                        if(arr[j] > arr[j + gap]) {
        
                            int temp = arr[j];
                            arr[j] = arr[j + gap];
                            arr[j + gap] = temp;
                        }
                    }
                }
            }
            return arr;
        }