# 插入排序

By [张十二(jonathan_zhang )](https://paragraph.com/@jonathan-zhang) · 2023-06-28

---

**直接插入排序**

    void Insert(ElemType A[], int n) {
        int i, j;
        for (i = 2; i <= n; i++) {
            if (A[i] < A[i-1]) {
                A[0] = A[i];
                for (j = i-1; A[0] < A[j]; --j) {
                    A[j+1] = A[j];
                }
                A[j+1] = A[0];
            }
        }
    }
    

**折半插入排序**

    void InsertSort(ElemType A[], int n) {
        int i, j, low, high, mid;
        for (i = 2; i <= n; i++) {
            A[0] = A[i];
            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];
        }
    }
    

**希尔排序**

    void ShellSort(ElemType A[], int n) {
        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[0] = A[i];
                    int j;
                    for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) {
                        A[j + dk] = A[j];
                    }
                    A[j + dk] = A[0];
                }
            }
        }
    }

---

*Originally published on [张十二(jonathan_zhang )](https://paragraph.com/@jonathan-zhang/vibdvDMMRmfV0XLoE2Ok)*