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

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

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元起，快前往官网查看详情吧