排序 冒泡排序

#includeusing namespace std;
int main()
{int a[10] = {0, 9, 5, 6, 3, 1, 2, 7, 8, 4};

    for(int i = 0; i< 9; i++)
    {for(int j = 0; j< 9 - i; j++)
        {if (a[j] >a[j + 1]) 
            {int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    for(int i = 0; i< 10; i++) printf("%d ", a[i]);

    return 0;
}

T( n n n) = O( n 2 n^2 n2)
S( n n n) = O( 1 1 1)
优点：稳定。
缺点：慢，每次只能移动相邻两个数据

创新互联是一家集网站建设,方城企业网站建设,方城品牌网站建设,网站定制,方城网站建设报价,网络营销,网络优化,方城网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

选择排序

#includeusing namespace std;
int main()
{int a[10] = {0, 9, 5, 6, 3, 1, 2, 7, 8, 4};

    for (int i = 0; i< 9; i++)
    {int pos = i;
        for (int j = i; j< 10; j++)
        {if (a[j]< a[pos]) pos = j;
        }
        
        int t = a[i];
        a[i] = a[pos];
        a[pos] = t;
    }

    for(int i = 0; i< 10; i++) printf("%d ", a[i]);

    return 0;
}

T( n n n) = O( n 2 n^2 n2) = Ω( n 2 n^2 n2)
S( n n n) = O( 1 1 1)
优点：移动数据的次数已知（n-1次）。
缺点：比较次数多。

插入排序

#includeusing namespace std;
int main()
{int a[10] = {0, 9, 5, 6, 3, 1, 2, 7, 8, 4};

    for (int i = 0; i< 10; i++)
    {int t = a[i], j = 0;
        for (j = i - 1; j >= 0 && a[j] >t; j--)
            a[j + 1] = a[j];
        a[j + 1] = t;
    }

    for(int i = 0; i< 10; i++) printf("%d ", a[i]);

    return 0;
}

T( n n n) = O( n 2 n^2 n2) = Ω( n n n)
S( n n n) = O( 1 1 1)
优点：稳定，快。
缺点：比较次数不一定，比较次数越多，插入点后的数据移动越多

桶排序

T( n n n) = O( 1 1 1)
S( n n n) = O( n n n)

#includeint main()
{int n = 0, a[100] = {0}, t[100] = {0};
    scanf("%d", &n);
    for(int i = 0; i< n; i++)
    {scanf("%d",&a[i]);
        t[a[i]]++;
    }

    for (int i = 0; i< 100; i++)
    {if (t[i] != 0){while (t[i]--)
                printf("%d ", i);
        }
    }
    return 0;
}

优劣
优点：快，效率达到O( 1 1 1)。
缺点：数据范围必须为正整数并且比较小。

---

作为科普，可以自己先了解，

快速排序

T( n n n) = O( n 2 n^2 n2) = Ω( n l o g n nlogn nlogn)
S( n n n) = O( 1 1 1)

归并排序

T( n n n) = O( n l o g n nlogn nlogn)
S( n n n) = O( n n n)

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：C语言基础-排序-创新互联
标题路径：http://chengdu.cdxwcx.cn/article/dcjedh.html