插入排序（直接插入、折半插入、希尔）

/**
 * 
 * 插入排序
 * 直接查找排序
 * 折半插入排序
 * 希尔排序
 *
 * ①算法思想
 *
 * ②算法设计
 *
 */

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <malloc.h>
#include <cstdlib>
#define MaxSize 20
#define INF 999999

//1、直接插入排序（链表的形式之前习题中已写过）
//排成增序
void InsertSort(int arr[],int n){
    int i,j;
    for(i = 2;i <= n ;i ++){
        //0的位置不存放元素，0的位置是“哨兵”，要进入有序区的元素直接被覆盖就行，因为哨兵存储了被覆盖的元素。
        if(arr[i] < arr[i - 1]){
            arr[0] = arr[i];
            for (j = i - 1;arr[0] < arr[j]; --j) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = arr[0];
        }
    }
}
//2、折半查找排序
//排成增序
void InsertSortByBinary(int arr[],int n){
    int i,j,low,high,mid;
    for (i = 2; i <= n; ++i) {
        arr[0] = arr[i];
        low = 1;
        high = i - 1;//有序区是1到 i - 1
        while(low <= high){//注意插入和查找的区别，就算mid==key，也不能停下来
            mid = (low + high) / 2;
            if(arr[mid] > arr[0])
                high = mid - 1;
            else
                low = mid + 1;//arr[mid]==arr[0]的情况时，让low=mid+1，而不是high=mid-1,保证了稳定性
        }
        for (j = i - 1; j >= low; j--) {//把low换成high + 1 是一样的
            arr[j + 1] = arr[j];
        }
        arr[low] = arr[0];//把low换成high + 1 是一样的
    }
}

//3、希尔排序
//排成增序
void ShellSort(int arr[],int n){
    int dk,i,j;//dk为每次的增量，一般一开始取长度的一半
    for (dk = n / 2; dk >= 1 ; dk /= 2) {
        //直接插入排序
        //直接插入排序里，默认第一个元素是有序的（arr[0]不算是第一个元素，还是放哨兵），从第二个元素开始排序，
        //这里是一样的，这里的第一个元素是这个增量序列的第一个,第二个元素是这个增量序列的第二个
        for (i = dk + 1;i <= n; ++i) {//++i说明一次性对此前增量状态下的所有的子表里的元素进行直接插入
            if(arr[i] < arr[i-dk]){//i - dk 是有序区的最后一个
                arr[0] = arr[i];
                for (j = i - dk;j > 0 && arr[0] < arr[j] ; j -= dk) {
                    arr[j + dk] = arr[j];
                }
                arr[j + dk] = arr[0]; 
            }
        }
    }
}

最后

以上就是羞涩钢笔为你收集整理的插入排序（直接插入、折半插入、希尔）的全部内容，希望文章能够帮你解决插入排序（直接插入、折半插入、希尔）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。