排序算法知识点-创新互联

插入排序 一、直接插入

时间复杂度：O(n^2)

成都创新互联公司始终坚持【策划先行，效果至上】的经营理念，通过多达10余年累计超上千家客户的网站建设总结了一套系统有效的营销解决方案，现已广泛运用于各行各业的客户，其中包括：木制凉亭等企业，备受客户赞誉。

void InsertSort(int a[], int n){// 数据基本有序的情况下时间复杂度低
    for(int i = 1; i< n; i++){
        if(a[i]< a[i-1]){
            a[0] = a[i];// 找到无序的第一个值，设置哨兵
            for(int j = i - 1; a[j] >a[0]; j--){
                a[j+1] = a[j];
                a[j+1] = a[0];
            }
        }
    }
}

二、希尔排序

时间复杂度：O(n^(3/2))

给定增量d，数据分为d组

void ShellSort(int a[], int n, int d){
    for(int i = 1 + d; i<= n; i++){
        if(a[i]< a[i-d]){
            a[0] = a[i];
            for(int j = i - d; a[j] >a[0]; j -= d){
                a[j+d] = a[j];
                a[j+d] = a[0];
            }
        }
    }
}

快速排序

时间复杂度：O(n)

C++ 详解快速排序代码_snowman22的博客-博客_快速排序c++代码

练习：洛谷 P1923

归并排序 

时间复杂度：nlogn

// 归并排序：稳定，nlogn
int a[N], c[N];// c数组为临时数组
void msort(int s, int t){
    if(s == t) return ;
    // 先分再合
    int mid = s + t >>1;
    msort(s, mid);
    msort(mid + 1, t);
    int i = s, j = mid + 1, k = s;
    while(i<= mid && j<= t){
        if(a[i]<= a[j]){
            c[k++] = a[i++];
        }
        else c[k++] = a[j++];
    }
    while(i<= mid) c[k++] = a[i++];
    while(j<= t) c[k++] = a[j++];
    for(int i = s; i<= t; i++){
        a[i] = c[i];// 将临时数组的数据复制回来
    }
}

**应用：求序列中的逆序对

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

本文标题：排序算法知识点-创新互联
网页URL：https://www.cdcxhl.com/article6/dggjig.html

成都网站建设公司_创新互联，为您提供App开发、网站改版、动态网站、网站排名、静态网站、品牌网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联