排序笔记

直接插入排序

原理分析

代码实现

#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$)

稳定性:稳定

广告 广告位招租
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
小黄脸
上一篇
下一篇