算法基础===》==》=》排序（内部排）

分手后的思念是犯贱 2022-10-02 04:53 97阅读 0赞

转自： [https://blog.csdn.net/qq\_43595030/article/details/91344579][https_blog.csdn.net_qq_43595030_article_details_91344579]

版权声明： https://blog.csdn.net/qq\_43595030/article/details/91344579  
一些最基本的排序算法：

插入排序  
交换排序  
选择排序  
@ 插入排序：

1-直接插入排序：

从前端插入  
从后端插入  
2-希尔（Shell）排序

1-直接插入排序：

从前端插入：  
int arr\[\]=\{999,1,2,5,8,4,3,9,7\};//"999"是一个容储器(arr\[0\]是一个监视哨),不参与排序。  
void InsertSort(int n)  
\{  
    int i,j;  
    for(i=2;i<=n;i++)//进行n-1次排序  
    \{  
        arr\[0\]=arr\[i\];//设置监视哨---减少扫描量，提高效率。  
        j=i-1;//j代表有序序列的最后一个元素  
        while(arr\[0\]<arr\[j\])  
        \{  
            arr\[j+1\]=arr\[j\];//记录后移  
            j--;  
        \}  
            arr\[j+1\]=arr\[0\];//把存放在arr\[0\]中的原记录插入到正确位置  
    \}  
\}  
  
从后端插入：  
int arr\[\]=\{0,1,2,5,8,4,3,9,7,999\};//"999"是一个容储器(arr\[n+1\]是一个监视哨),"0"是填补i=0的空白位置,"999"与"0"均不参与排序。  
void InsertSort(int n)//从第n-1个元素开始向它前面插入，直到第一个元素插入为止。  
\{  
    int i,j;  
    for(i=n-1;i>=1;i--)//进行n-1次排序  
    \{  
        arr\[n+1\]=arr\[i\];//设置监视哨  
        j=i+1;//j代表有序序列的最后一个元素  
        while(arr\[n+1\]>arr\[j\])  
        \{  
            arr\[j-1\]=arr\[j\];//记录前移  
            j++;  
        \}  
            arr\[j-1\]=arr\[n+1\];//把存放在arr\[n+1\]中的原记录插入到正确位置  
    \}  
\}

2-希尔（Shell）排序==>直接插入排序的改进版

void InsertSort(int n)  
\{  
    int i,j,d;  
    for(d=n/2;d>=1;d=d/2)//进行n-1次排序  
    \{  
        for(i=d+1;i<=n;i++)  
        \{  
        arr\[0\]=arr\[i\];//设置监视哨  
        j=i-d;//前后位置的增量为d,而不是1  
        while(j>0&&arr\[0\]<arr\[j\])  
        \{  
            arr\[j+d\]=arr\[j\];//记录后移，查找插入位置  
            j=j-d;  
        \}  
            arr\[j+d\]=arr\[0\];//插入  
        \}  
    \}  
\}  
  
\------》源代码：

\#include<iostream>  
using namespace std;

//1.数组的初始化：  
int arr\[\]=\{999,1,2,5,8,4,3,9,7\};//"999"是一个容储器(arr\[0\]是一个监视哨),不参与排序。

//2.希尔排序：  
void InsertSort(int n)  
\{  
    int i,j,d;  
    for(d=n/2;d>=1;d=d/2)//进行n-1次排序  
    \{  
        for(i=d+1;i<=n;i++)  
        \{  
        arr\[0\]=arr\[i\];//设置监视哨  
        j=i-d;//前后位置的增量为d,而不是1  
        while(j>0&&arr\[0\]<arr\[j\])  
        \{  
            arr\[j+d\]=arr\[j\];//记录后移，查找插入位置  
            j=j-d;  
        \}  
            arr\[j+d\]=arr\[0\];//插入  
        \}  
    \}  
\}

void Show\_arr(int n)  
\{  
    int i;  
    for(i=1;i<=n;i++)  
        cout<<arr\[i\]<<'\\t';  
    cout<<endl;  
\}

void main()  
\{  
    InsertSort(8);  
    Show\_arr(8);  
\}

直接插入排序的算法的时间复杂度为O(n^2)，直接插入排序是一种稳定的排序方法。而shell\_sort的算法的时间复杂度为O(n\* log2^n)~ O（n ^2） 大略为O(n^(3/2)),shell\_sort不是一种稳定的排序方法

@交换排序：

冒泡排序  
快速排序  
1- 冒泡排序：

void Bubble\_Sort(int \*a,int n)  
\{  
    int  i, j, t;  
    for(i=0;i<n-1;i++)  
    \{  
        for(j=0;j<n-i-1;j++)  
            if(a\[j\]>a\[j+1\])  
            \{  
                t=a\[j\];  
                a\[j\]=a\[j+1\];  
                a\[j+1\]=t;  
            \}  
    \}  
\}  
  
2-快速排序:

void Quick\_Sort(int low,int high)  
\{  
    if(low>=high)  
        return ;  
    int i=low,j=high;//避免引起歧义  
    arr\[0\]=arr\[low\];  
    while(i<j)  
    \{  
        while(i<j&&arr\[0\]<=arr\[j\])//"i<j"绝对不能省,此处与外循环的含义不同  
            j--;  
        arr\[i\]=arr\[j\];  
        while(i<j&&arr\[i\]<=arr\[0\])  
            i++;  
        arr\[j\]=arr\[i\];  
    \}  
    arr\[i\]=arr\[0\];  
    Quick\_Sort(low,i-1);  
    Quick\_Sort(i+1,high);  
\}  
  
\------》源代码：

\#include<iostream>  
using namespace std;

//1.数组的初始化：  
int arr\[\]=\{0,1,2,5,8,4,3,9,7\};

//2.快速排序：一个形象的比喻-》“选取一个中间点，两边互相扔石头”  
void Quick\_Sort(int low,int high)  
\{  
    if(low>=high)  
        return ;  
    int i=low,j=high;//避免引起歧义  
    arr\[0\]=arr\[low\];  
    while(i<j)  
    \{  
        while(i<j&&arr\[0\]<=arr\[j\])//"i<j"绝对不能省,此处与外循环的含义不同  
            j--;  
        arr\[i\]=arr\[j\];  
        while(i<j&&arr\[i\]<=arr\[0\])  
            i++;  
        arr\[j\]=arr\[i\];  
    \}  
    arr\[i\]=arr\[0\];  
    Quick\_Sort(low,i-1);//这里采用递归来化简算法的难度  
    Quick\_Sort(i+1,high);  
\}  
void Show\_arr(int n)  
\{  
    int i;  
    for(i=1;i<=n;i++)  
        cout<<arr\[i\]<<'\\t';  
    cout<<endl;  
\}

void main()  
\{  
    Quick\_Sort(1,8);  
    Show\_arr(8);  
\}  
  
冒泡排序的算法的时间复杂度为O(n^2)，是一种稳定的排序方法。  
快速排序的算法的时间复杂度为O(n\* log2^n)~ O（n ^2），不是一种稳定的排序方法。

@选择排序:

直接选择排序  
堆排序  
直接选择排序：

void Sort(int \*a,int len)  
\{  
    int i,j,min,t;  
    for(i=0;i<len-1;i++)  
    \{  
        for(min=i,j=i+1;j<len;j++)  
            if(a\[min\]>a\[j\])  
            \{  
                min=j;  
            \}  
            if(min!=i)  
            \{  
                t=a\[i\];  
                a\[i\]=a\[min\];  
                a\[min\]=t;  
            \}  
    \}  
\}  
  
\------》源代码：

\#include<iostream>  
using namespace std;

//1.数组的初始化：  
int arr\[\]=\{1,2,5,8,4,3,9,7\};

//2.选择排序：  
void Sort(int \*a,int len)  
\{  
    int i,j,min,t;  
    for(i=0;i<len-1;i++)  
    \{  
        for(min=i,j=i+1;j<len;j++)  
            if(a\[min\]>a\[j\])  
            \{  
                min=j;  
            \}  
            if(min!=i)  
            \{  
                t=a\[i\];  
                a\[i\]=a\[min\];  
                a\[min\]=t;  
            \}  
    \}  
\}  
void Show\_arr(int n)  
\{  
    int i;  
    for(i=0;i<n;i++)  
        cout<<arr\[i\]<<'\\t';  
    cout<<endl;  
\}

void main()  
\{  
    Sort(arr,8);  
    Show\_arr(8);  
\}  
  
堆排序：==>选择排序的改进版  
\*什么是堆？—  
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的数值或索引总是小于（或者大于）它的父节点。  
堆排序的生成及其排序原理：

堆排序的实现：

void Adjust(int i,int n)//i代表待调整元素的下标，n代表最后一元素的下标。  
\{  
    int j;  
    arr\[0\]=arr\[i\];  
    while(i<n&&2\*i<=n)  
    \{  
        j=2\*i;//j为i左孩子下标  
        if(j<n&&arr\[j\]>arr\[j+1\])  
            j++;//j指向较小的孩子  
        if(arr\[0\]>arr\[j\])  
        \{  
            arr\[i\]=arr\[j\];  
            i=j;  
        \}  
        else  
            break;  
    \}  
    arr\[i\]=arr\[0\];  
\}  
void Build\_Heap(int n)  
\{  
    int i;  
    for(i=n/2;i>0;i--)  
        Adjust(i,n);  
\}  
void Show\_arr(int n)  
\{  
    int i;  
    for(i=1;i<=n;i++)  
        cout<<arr\[i\]<<'\\t';  
    cout<<endl;  
\}  
void Heap\_Sort(int n)  
\{  
    int i,t;  
    Build\_Heap(n);  
    cout<<"初始堆积树："<<endl;  
    Show\_arr(8);  
    cout<<endl;  
    for(i=n;i>1;i--)  
    \{  
        t=arr\[1\];  
        arr\[1\]=arr\[i\];  
        arr\[i\]=t;  
        cout<<endl<<"第  "<<n-i+1<<"趟："<<endl;  
        Show\_arr(8);  
        Adjust(1,i-1);  
    \}  
\}  
  
\------》源代码：

\#include<iostream>  
using namespace std;

//1.数组的初始化：  
int arr\[\]=\{0,1,2,5,8,4,3,9,7\};

/\*2.堆积树的调整过程：  
从二叉树的叶子节点处往上逐一比较来建立最大堆积树：\*/  
void Adjust(int i,int n)//i代表待调整元素的下标，n代表最后一元素的下标。  
\{  
    int j;  
    arr\[0\]=arr\[i\];  
    while(i<n&&2\*i<=n)  
    \{  
        j=2\*i;//j为i左孩子下标  
        if(j<n&&arr\[j\]>arr\[j+1\])  
            j++;//j指向较小的孩子  
        if(arr\[0\]>arr\[j\])  
        \{  
            arr\[i\]=arr\[j\];  
            i=j;  
        \}  
        else  
            break;  
    \}  
    arr\[i\]=arr\[0\];  
\}

//3.堆积树的建立：  
void Build\_Heap(int n)  
\{  
    int i;  
    for(i=n/2;i>0;i--)  
        Adjust(i,n);  
\}

//显示：  
void Show\_arr(int n)  
\{  
    int i;  
    for(i=1;i<=n;i++)  
        cout<<arr\[i\]<<'\\t';  
    cout<<endl;  
\}

//4.堆积排序：  
void Heap\_Sort(int n)  
\{  
    int i,t;  
    Build\_Heap(n);  
    cout<<"初始堆积树："<<endl;  
    Show\_arr(8);  
    cout<<endl;  
    for(i=n;i>1;i--)  
    \{  
        t=arr\[1\];  
        arr\[1\]=arr\[i\];  
        arr\[i\]=t;  
        cout<<endl<<"第  "<<n-i+1<<"趟："<<endl;  
        Show\_arr(8);  
        Adjust(1,i-1);  
    \}  
\}  
void main()  
\{  
    Show\_arr(8);  
    cout<<endl;  
    Heap\_Sort(8);  
\}  
  
直接选择排序的算法的时间复杂度为O(n^2)，由于直接选择排序交换次数少，当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。但它却并不是一种稳定的排序方法,综合来看其性价比 较低.  
堆排序方法对记录数较小的排序效果并不理想，但对于n较大的文件很有意义，因为其运行时间主要建立在初始建堆和反复调整堆上。  
建堆的时间复杂度与堆所对应的完全二叉树的深度的数量级log2^n 有关，而调用数量级为n,所以整个堆排序的时间复杂度为O(n\* log2^n)。在空间复杂度方面，堆排序只需要一个辅助空间，为O(1)。此外，堆排序并不是稳定的排序哦。

\*ps:在算法的设计中排序的方法有很多种，但具体情况还需要具体分析，在情景中应当采取最合适的排序算法。  
\---------------------   
作者：九霄云客   
来源：CSDN   
原文：https://blog.csdn.net/qq\_43595030/article/details/91344579   
版权声明：本文为博主原创文章，转载请附上博文链接！

[https_blog.csdn.net_qq_43595030_article_details_91344579]: https://blog.csdn.net/qq_43595030/article/details/91344579