排序算法复习——插入类排序

在插入类排序的算法中，有直接插入排序，折半插入排序，希尔排序。

直接插入排序：

程序代码演练：

#include <stdio.h>

#define N 10

int main()
{
    int a[N] = {62, 48, 35, 77, 55, 14, 35, 98, 22, 10};
    int tmp, i, j;

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    /*插入排序算法*/
    for(i = 1; i < N; i++) {  //控制插入的次数
        tmp = a[i];
        j = i-1;
        while(tmp < a[j]) {   //寻找插入位置;如果改为<=的话，就会是不稳定的排序
            a[j+1] = a[j];
            j = j-1;
        }
        a[j+1] = tmp;
    }

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

62 48 35 77 55 14 35 98 22 10
10 14 22 35 35 48 55 62 77 98

折半插入排序：

折半插入排序其实是对直接插入排序的改进，是在寻找插入位置的时候把折半查找的算法加了进来。

程序代码演练：

#include <stdio.h>

#define N 10

int main()
{
    int a[N] = {62, 48, 35, 77, 55, 14, 35, 98, 22, 10};
    int tmp, i, j, low, mid, high;

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
     /*折半排序算法*/
    for(i = 1; i < N; i++) {
        tmp = a[i];
        low = 0;
        high = i-1;
        while(low <= high) {    //使用折半查找算法进行查找插入位置
            mid = (low+high)/2;
            if(a[mid] > a[i]) {
                high = mid-1;
            } else {
                low = mid+1;
            }
        }
        for(j=i; j>low; j--) {
            a[j] = a[j-1];
        }
        a[low] = tmp;
    }

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

62 48 35 77 55 14 35 98 22 10
10 14 22 35 35 48 55 62 77 98

希尔排序：

对于这个排序算法，首先要清楚它的实现过程。

演练程序：

#include <stdio.h>

#define N 8

void hillsort(int *a, int delta)
{
    int i, tmp, j;
/*
 *
 *这里没有按照一趟插入排序就把当前子序列排序完毕，而是从第一个子序列的第二个元
 *素开始进行插入排序，顺序遍历完整个待排序记录的序列
 *
 */
    for(i=delta; i<N; i++) {
        if(a[i] < a[i-delta]) {
            tmp = a[i];
            for(j=i; j>=delta && tmp<a[j-delta]; j=j-delta) {
                a[j] = a[j-delta];
            }
            a[j] = tmp;
        }
    }
}

int main()
{
    int a[N] = {62, 48, 35, 77, 55, 14, 35, 98};
    int i;

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    /*确定分割距离，每次为上次分隔距离的一半，并且最后一次距离是1，之后结束*/
    for(i=N/2; i>=1; i=i/2) {
        hillsort(a, i);
    }

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

62 48 35 77 55 14 35 98 100 29
14 29 35 35 48 55 62 77 98 100