21天经典算法之折半插入排序

​
​

活动地址：CSDN21天学习挑战赛

专栏前言:

本专栏主要是算法训练，目的很简单。就是为了进厂
最近官方在组织 21 天挑战赛，趁此机会我也更新一下经典算法的文章
如果想一起“狂”或者交流，欢迎来私聊
还不快趁着这个机会来提升自己💪

👉排序算法介绍

排序算法是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。最终序列按照一定的规律进行呈现。

在排序算法中，稳定性和效率是我们经常要考虑的问题。

稳定性：稳定是指当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。

复杂度分析：
（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

常见的排序算法分为以下几种：

👉折半插入排序

原理

折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进。不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

代码实现

在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为 a[low] ，末元素设置为 a[high] ，则每轮比较时将待插入元素与 a[m] ，其中 m = (low+high)/2 相比较，如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择 a[m+1] 到 a[high] 为新的插入区域（即low=m+1），如此直至low<=high 不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。

总之：利用已排好的元素有序的特点，使用折半查找的特点来快速找到要插入的位置。

    // Binary Insertion Sort method    
    private static void binaryInsertSort(int[] array){
       
        for(int i = 1; i < array.length; i++){
           
            int temp = array[i];            
            int low = 0;            
            int high = i - 1;  
           
            while(low <= high){                
                int mid = (low + high) / 2;                
                if(temp < array[mid]){                    
                    high = mid - 1;                
                }else{                    
                    low = mid + 1;
                }       
            }
           
            for(int j = i; j >= low + 1; j--){            
                array[j] = array[j - 1];                                                      
            }       
           
            array[low] = temp;       
        }   
    }

复杂度分析

折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。

时间复杂度：

• 最好的情况：$O(n)$。如果元素排序正向有序，开始的时候就直接找到了位置，不需要寻找和移位。
• 最坏的情况：$O(n^2)$。如果元素排序反向有序，那么每次都需要进行数据查找。
• 平均复杂度：$O(n^2)$。

空间复杂度：$O(1)$。仅需几个存储空间用于记录信息的关键单元，即空间复杂度为 $O(1)$。

👉示例：

👉算法实践

💭
算法的整体思想已经在上面讲述了，下面直接使用一个例子来试试水。

折半插入排序

题目描述：

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

class Solution {
    public int[] sortArray(int[] nums) {
        for(int i = 1; i < nums.length; i++){
           
            int temp = nums[i];            
            int low = 0;            
            int high = i - 1;  
           
            while(low <= high){                
                int mid = (low + high) / 2;                
                if(temp < nums[mid]){                    
                    high = mid - 1;                
                }else{                    
                    low = mid + 1;
                }       
            }
           
            for(int j = i; j >= low + 1; j--){            
                nums[j] = nums[j - 1];                                                      
            }       
           
            nums[low] = temp;       
        }   
        return nums;
    }
}

这个题目非常nice，你可以尝试去使用不同的排序方法去测试。

👉课后习题

如果你觉得掌握了，那么赶快来实践一下吧

​