数据结构之基础入门八(一.插入排序)

喜欢ヅ旅行 2022-11-30 01:36 103阅读 0赞

### 数据结构.基础入门.插入排序.考研复习.面试算法练习 ###

*  0. 目录
 *  8. 排序
 *   *  8.1 插入排序
     *   *  8.1.1 直接插入排序
         *  8.1.2 折半插入排序
         *  8.1.3 希尔排序

# 0. 目录 #

# 8. 排序 #

## 8.1 插入排序 ##

### 8.1.1 直接插入排序 ###

typedef int ElemType;
    
    //直接插入排序
    void Insert(ElemType A[], int n)
    {
        int i, j;
        for (i = 2; i <= n; i++) //依次将A[2]-A[n]插入到前面已排序序列
        {
            if (A[i] < A[i - 1]) //若A[i]关键码小于其前驱,将A[i]插入有序表
            {
                A[0] = A[i];                      //复制为哨兵,A[0]不存放元素
                for (j = i - 1; A[0] < A[j]; --j) //从后往前查找待插入位置
                {
                    A[j + 1] = A[j]; //向后挪位
                }
                A[j + 1] = A[0]; //复制到插入位置
            }
        }
    }

### 8.1.2 折半插入排序 ###

//折半插入排序
    void InsertSort(ElemType A[], int n)
    {
        int i, j, low, high, mid;
        for (i = 2; i < n; i++) //依次将A[2]-A[n]插入前面的已排序序列
        {
            A[0] = A[i]; //将A[i]暂存到A[0]
            low = 1;
            high = i - 1;       //设置折半查找的范围
            while (low <= high) //折半查找(默认递增有序)
            {
                mid = (low + high) / 2; //取中间点
                if (A[mid] > A[0])      //查找做半子表
                {
                    high = mid - 1;
                }
                else //查找右半子表
                {
                    low = mid + 1;
                }
            }
            for (j = i - 1; j > high + 1; --j)
            {
                A[j + 1] = A[j]; //统一后移元素,空出插入位置
            }
            A[high + 1] = A[0]; //插入操作
        }
    }

### 8.1.3 希尔排序 ###

//希尔排序
    void ShellSort(ElemType A[], int n)
    {
        //A[0]只是暂存单元,不是哨兵,当j<=0时,插入位置已到
        for (int dk = n / 2; dk >= 1; dk = dk / 2) //步长变化
        {
            for (int i = dk + 1; i = < n; ++i)
            {
                if (A[i] < A[i - dk]) //需要A[i]插入有序增量子表
                {
                    A[0] = A[i]; //暂存在A[0]
                    for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
                    {
                        A[j + dk] = A[j]; //记录后移,查找插入的位置
                    }
                    A[j + dk] = A[0]; //插入
                }
            }
        }
    }