数据结构——排序-创新互联-成都创新互联网站建设

成都创新互联网站制作

028-86922220

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

数据结构——排序-创新互联

目录

建昌网站建设公司成都创新互联,建昌网站设计制作，有大型网站制作公司丰富经验。已为建昌近1000家提供企业网站建设服务。企业网站搭建\成都外贸网站制作要多少钱，请找那个售后服务好的建昌做网站的公司定做！

个人观点：

排序的概念：

排序的稳定性：

内排序与外排序：

概念：

排序用到的结构与函数：

代码：

最简单排序的实现：

举例：

代码：

时间复杂度:

冒泡排序：

举例：

代码：

时间复杂度：

在优化：

举例：

代码：

简单选择排序：

思想:

代码:

时间复杂度：

直接插入排序：

举例：

代码：

时间复杂度：

希尔排序：

分析：

举例：

推荐视频：

代码：

注意：

堆排序：

堆定义;

举例：

基本思想：

举例：

代码：

归并排序：

算法思想：

理解图解：

举例：

分析一下它的合并操作是如何进行的：

代码实现：

快速排序：

算法思想：

举例：

代码：

个人观点：

（仅代表个人）

对于我初学者来讲，排序这个章节我们注重的思想而不是用法（个人看法而言，因为我刷题量很少，对我来说sort现在够用），那么我们就先注重这些算法的内容思想。

排序的概念：

排序的稳定性：

通俗来讲就是相同的关键字，在排序之后，它们的前后关系不会变

举例

内排序与外排序： 概念：

内排序是在整个排序过程中，待排序的所有记录全部被放置在内存中。

外排序是由于排序记录个数过多，不能同时防止在内存中，整个排序过程需要在内外存之间多次数据交换才能进行

对于内排序性能而言：

（1）时间性能

（2）辅助空间

（3）算法复杂性

内排序分为插入排序、交换排序、选择排序和归并排序

排序用到的结构与函数： 代码：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len=0;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    cout<
最简单排序的实现：

它的基本思想就是相邻两两比较，有冒泡思想但不是冒泡排序

举例：

下标从1开始

代码：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void BubbleSort0(Sqlist*L){
    for(int i=1;i<=L->len;i++){
        for(int j=1;j<=L->len;j++){
            if(L->res[i]>L->res[j])
            swaq(L,i,j);
        }
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    for(int i=1;i<=L.len;i++)cout<
时间复杂度:

时间复杂度高，O(n^2)


冒泡排序： 举例：

从后往前交换，则必定会把相对小的数向前移动，时间复杂度提高了

代码：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Bubblesort(Sqlist*L){
    for(int i=1;ilen;i++){
        for(int j=L->len-1;j>=i;j--){
            if(L->res[j]>L->res[j+1])
            swaq(L,j,j+1);
        }
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Bubblesort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
时间复杂度：

O(n^2)，但是相对来说总归有优化



在优化： 举例：

代码：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Bubblesort(Sqlist*L){
    for(int i=1;ilen;i++){
        bool flag=1;
        for(int j=L->len-1;j>=i;j--){
            if(L->res[j]>L->res[j+1])
            swaq(L,j,j+1);
            flag=0;
        }
        if(flag)
            break;
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Bubblesort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
简单选择排序： 思想:

与冒泡排序差不多，只不过不是遇见小的就交换，而是每次循环遇到最小的才交换

代码:
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Selectsort(Sqlist*L){
    int j,mn;
    for(int i=1;ilen;i++){
        mn=i;
        bool flag=0;
        for(j=i+1;j<=L->len;j++){
            if(L->res[mn]>L->res[j]){
                mn=j;
                flag=1;
            }
        }
        if(flag)
            swaq(L,i,mn);
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Selectsort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
时间复杂度：

O(n^2)，但是相对于冒泡排序，总归有一定的优化

直接插入排序： 举例：

此时哨兵（L.res[0]）就起到了作用

代码：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Insertsort(Sqlist*L){
    int j;
    for(int i=2;i<=L->len;i++){
        if(L->res[i]res[i-1]){
            L->res[0]=L->res[i];
            for(j=i-1;L->res[j]>L->res[0];j--)
                L->res[j+1]=L->res[j];
            L->res[j+1]=L->res[0];
        }
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Insertsort(&L);
    for(int i=1;i<=L.len;i++){
        cout<

时间复杂度：

O(n^2)，但是时间效率更好点

希尔排序： 分析：

希尔排序是在直接插入排序上的优化

直接插入排序的最好情况：{2,3,4,5,6}，时间复杂度为O（n）

最坏情况：{6,5,4,3,2}，时间复杂度为O（n^2）

希尔排序是将一个数组分为若干个子序列，然后各自排序然后合并，实现基本有序

基本有序，就是小的关键字基本在前面，大的关键字基本在后面

采用跳跃式分割策略。。。

举例：

推荐视频：

排序算法：希尔排序【图解+代码】_哔哩哔哩_bilibili

代码：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void shellsort(Sqlist*L){
    int i,j,k=0;
    int lon=L->len;
    do{
        lon=lon/3+1;
        for(i=lon+1;i<=L->len;i++){
            if(L->res[i]res[i-lon]){
                L->res[0]=L->res[i];
                for(j=i-lon;j>0&&L->res[0]res[j];j-=lon){
                    L->res[j+lon]=L->res[j];
                }
                L->res[j+lon]=L->res[0];
            }
        }
        
        
    }while(lon>1);
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    shellsort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
注意：

增量序列的最后一个增量必须等于1才行

堆排序： 堆定义;

其实就是特殊的完全二叉树

举例：

大顶堆，所有结点大于其左右孩子结点，小顶堆反之

基本思想：

将待排序的序列构造成一个大顶堆。此时整个序列的大值就是堆顶的根结点

将它移走（其实就是将其与堆数组末尾元素交换，此时末尾元素就是大值），然后将剩余的n-1

个序列重新构造一个堆，这样就会得到n个元素中的次大值，反复执行，便能得到一个有序序列

举例：

（建树）

代码：

归并排序：

算法思想：

是利用归并的思想实现的排序方法，通俗理解起来就是

对于一个无序的数组，先让子序列为1的序列两两归并，然后让子序列为2的序列两两归并，以此类推

理解图解：

举例：

分析一下它的合并操作是如何进行的：

举例：

代码实现：

快速排序： 算法思想：

通过一趟排序将待排记录分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后对这两部分继续进行排序，以达到整个序列有序的目的

举例：

代码：

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


当前标题：数据结构——排序-创新互联
文章分享：http://kswsj.cn/article/dsegce.html

其他资讯