插入排序--直接插入、折半插入

青旅半醒 2022-04-10 05:11 271阅读 0赞

昨天写了交换排序的算法（包括冒泡排序、快速排序），今天写一写插入排序。插入排序有三种：直接插入排序、折半插入排序、希尔排序。时间有限，今天先写一下直接插入排序和折半插入排序，希尔排序等明天有时间再写！  
  插入排序是将未排序序列中的元素依次拿出来与已排序序列中的元素进行比较，插入到已排序序列中的适当位置的排序方法。  
  直接插入排序是一种简单的排序的方法，基本操作为：将一个元素插入到已排序的序列中。初始默认第一个元素为有序序列，从第二个元素开始依次进行插入排序。  
代码如下：

//简单插入排序
    void straightInsertSort(int *arr,int len)
    {
        
        int i = 0;
        int j = 0;
        for(i = 2;i < len;i++)
        {
        
            arr[0] = arr[i];//元素a[0]用于存放待比较元素，不用来存放数据
            for(j = i - 1;j > 0;j--)
            {
        
                if(arr[0] < arr[j])
                {
        
                    arr[j + 1] = arr[j];
                }
                else
                {
        
                    break;
                }
            }
            arr[j + 1] = arr[0];
        }
    }

折半插入排序原理与直接插入排序一致，只不过折半插入排序首先查找元素要插入的位置，其查找方法采用折半查找，提高来运行效率。  
代码如下：

//折半查找
    int halveSearch(int *arr,int low,int high,int elem)
    {
        
        int mid = (low + high)/2;
        while(low <= high)
        {
        
            if(elem > arr[mid])
            {
        
                low = mid + 1;
            }
            else
            {
        
                high = mid - 1;
            }
            mid = (low + high) / 2;
        }
        return low;
    }
    
    //折半插入排序
    void halveInsertSort(int *arr,int len)
    {
        
        int i = 0;
        int j = 0;
        int temp = 0;
        for(i = 2;i < len;i++)
        {
        
            if(arr[i] > arr[i - 1])
            {
        
                continue;
            }
            temp = halveSearch(arr,1,i - 1,arr[i]);
            arr[0] = arr[i];
            for(j = i;j > temp;j --)
            {
        
                arr[j] = arr[j - 1];
            }
            arr[temp] = arr[0];
        }
    }

这两个算法看起来很简单，但是如果逻辑搞不清楚，还是很容易出错。有的时候看起来简单的东西做起来并不一定简单，而看起来复杂的事情做起来并不一定那么难。但是关键是自己要动手才知道事情到底是怎样的，会犯哪些错误，走哪些弯路，才能积累相应的经验！之前一直觉得直接插入排序很简单，但是真正去实现的时候发现自己并没有做到一次性编写成功，正确的运行结果是在修改了几个位置之后才得到的；而之前一直以为快排很麻烦，但是昨天写过后发现快排也没有自己想象的那么难，所以还是要多动手！  
最后附上所有代码：

#include <stdio.h>
    
    //简单插入排序
    void straightInsertSort(int *arr,int len)
    {
        
        int i = 0;
        int j = 0;
        for(i = 2;i < len;i++)
        {
        
            arr[0] = arr[i];//元素a[0]用于存放待比较元素，不用来存放数据
            for(j = i - 1;j > 0;j--)
            {
        
                if(arr[0] < arr[j])
                {
        
                    arr[j + 1] = arr[j];
                }
                else
                {
        
                    break;
                }
            }
            arr[j + 1] = arr[0];
        }
    }
    
    //折半查找
    int halveSearch(int *arr,int low,int high,int elem)
    {
        
        int mid = (low + high)/2;
        while(low < high)
        {
        
            if(elem > arr[mid])
            {
        
                low = mid + 1;
            }
            else
            {
        
                high = mid - 1;
            }
            mid = (low + high) / 2;
        }
        return low;
    }
    
    //折半插入排序
    void halveInsertSort(int *arr,int len)
    {
        
        int i = 0;
        int j = 0;
        int temp = 0;
        for(i = 2;i < len;i++)
        {
        
            if(arr[i] > arr[i - 1])
            {
        
                continue;
            }
            temp = halveSearch(arr,1,i - 1,arr[i]);
            arr[0] = arr[i];
            for(j = i;j > temp;j --)
            {
        
                arr[j] = arr[j - 1];
            }
            arr[temp] = arr[0];
        }
    }
    
    int main()
    {
        
        int i = 0;
        int arr[7] = {
        0,6,4,9,2,5,3};
        printf("Before straight insertSort arr:\n");
        for(i = 1;i < 7;i ++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        straightInsertSort(arr,7);
        printf("After straight insertSort arr:\n");
        for(i = 1;i < 7;i ++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        int arr2[7] = {
        0,6,4,9,4,5,3};
        printf("Before halve insertSort arr2:\n");
        for(i = 1;i < 7;i ++)
        {
        
            printf("%d ",arr2[i]);
        }
        printf("\n");
        halveInsertSort(arr2,7);
        printf("After halve insertSort arr2:\n");
        for(i = 1;i < 7;i ++)
        {
        
            printf("%d ",arr2[i]);
        }
        printf("\n");
        return 0;
    }