直接插入排序

原理分析

代码实现

#include<stdio.h>

void InsertSort(int A[],int n) {
    for (int i = 2;i<=n;i++) {  //从第二个元素开始比较
        if (A[i]<A[i-1]) {      //若待比较元素比前一个元素小，进行下一步，否则这个元素符合，进入下一个循环
            A[0] = A[i];       //将待插入元素放入A[0]
            int j;
            for (j=i-1;A[0]<A[j];j--){  //将大于A[0]的元素逐个向后挪
                A[j+1] = A[j];
            }
            A[j+1] = A[0]; //插入元素
        }
    }
}
int main() {
    int test[] = {-1,9,3,4,3,1,5,7,3,5,6,8,9};
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
    printf("\n");
    InsertSort(test,sizeof(test)/sizeof(test[0])-1);
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
}

性能分析

空间效率：使用了常数个辅助变量，可见复杂度为 o(1)

时间效率：o($n^2$)

稳定性：从后向前比较后移动，稳定

适用性：适用于顺序存储和链式存储

折半插入排序

代码实现

#include<stdio.h>

void InsertSort(int A[],int n) {
    for (int i = 2;i<=n;i++) {  //从第二个元素开始比较
        if (A[i]<A[i-1]) {      //若待比较元素比前一个元素小，进行下一步，否则这个元素符合，进入下一个循环
            A[0] = A[i];       //将待插入元素放入A[0]
            int begin = 1;
            int end = i-1;
            while (begin <= end) {
                int mid = (begin + end) / 2;
                if (A[i] < A[mid]) {
                    end = mid - 1;
                } else {
                    begin = mid + 1;
                }
            }
            int j;
            for (j=i-1;j>=begin;j--){  //将大于A[0]的元素逐个向后挪
                A[j+1] = A[j];
            }
            A[begin] = A[0]; //插入元素
        }
    }
}
int main() {
    int test[] = {-1,9,3,4,3,1,5,7,3,5,6,8,9};
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
    printf("\n");
    InsertSort(test,sizeof(test)/sizeof(test[0])-1);
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
}

性能分析

空间效率：o(1)

时间效率：o($n^2$)

稳定性：稳定

适用性：适用于顺序存储

希尔排序

原理分析

将排序表分割成若干个 L[i, i+d, i+2d, …, i+kd]子表，对子表进行插入排序，然后d=$\lfloor d/2 \rfloor$再进行插入排序，直到d=1是进行最后一次插入排序。

代码实现

#include<stdio.h>


void ShellSort(int A[],int n) {
    for (int d = n/2; d >= 1; d=d/2) {
        for (int i = d+1;i<=n;i++) {
            if (A[i]<A[i-d]) {
                A[0] = A[i];
                int j;
                for (j = i-d;j>0 && A[0] <A[j];j-=d) {
                    A[j+d] = A[j];
                }
                A[j+d] = A[0];
            }
        }
    }
}
int main() {
    int test[] = {-1,9,3,4,3,1,5,7,3,5,6,8,9};
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
    printf("\n");
    ShellSort(test,sizeof(test)/sizeof(test[0])-1);
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
}

性能分析

空间效率：使用了常数个辅助变量，可见复杂度为 o(1)

时间效率：o($n^2$)

稳定性：不稳定，当相同关键字被分配到不同子表时会导致相对位置发生改变

适用性：适用于顺序存储

冒泡排序

原理分析

两两相互比较，每趟都有一个元素到达最终位置

代码实现

#include<stdio.h>


void BubbleSort(int A[],int n) {
    for (int i=1;i<=n-1;i++) {
        int flag = 1;
        for (int j=1;j<=n-i;j++) {
            if (A[j+1]<A[j]) {
                int tmp = A[j+1];
                A[j+1] = A[j];
                A[j] = tmp;
                flag = 0;
            }
        }
        if (flag) {
            return;
        }
    }
}
int main() {
    int test[] = {-1,9,3,4,3,1,5,7,3,5,6,8,9};
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
    printf("\n");
    BubbleSort(test,sizeof(test)/sizeof(test[0])-1);
    for (int i=1;i<sizeof(test)/sizeof(test[0]);i++) {
        printf("%d ",test[i]);
    }
}

性能分析

空间效率：使用了常数个辅助变量，可见复杂度为 o(1)

时间效率：o($n^2$)

稳定性：稳定