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

插入排序 一、直接插入

时间复杂度：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元起，快前往官网查看详情吧

文章名称：排序算法知识点-创新互联
文章出自：http://cdkjz.cn/article/dggjig.html