【数据结构】经典排序算法—C/C++实现

SarPro

发布于 2024-02-20 13:09:19

4340

1. 冒泡排序

基本原理：

对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。如果从小到大排序，这时，较小的数据就会逐个向前移动，好像气泡向上漂浮一样。是一种稳定的排序方法。

平均时间复杂度

O（n ^ 2）稳定

图示排序过程：

为什么每趟比较次数减少一次？

在冒泡排序的过程中，每一趟都会将未排序部分的最大元素沉底（或最小元素浮顶），因此在第一趟排序过程中，最大（或最小）的元素会被放置在合适的位置。接下来的每一趟排序中，由于最大（或最小）的元素已经在正确的位置上，因此比较时无需再考虑该元素，而是只需比较未排序部分的其他元素。结论：N个数仅需排序N-1次。

参考链接：冒泡排序视频讲解

冒泡排序C语言源程序：

#include <stdio.h>
void BubbleSort(int a[],int n);//冒泡排序
void DispArray(int a[],int n); //输出数组
int main()
{
    int a[10]={0,3,2,1,4,6,5,7,9,8};

    BubbleSort(a,10);
    DispArray(a,10);

    return 0;
}

void BubbleSort(int a[],int n)//冒泡排序
{
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1;j++){
            if(a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

void DispArray(int a[],int n)//输出数组
{
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}

运行结果：

2. 选择排序

基本原理：

首先在未排序序列中找到最小元素（或最大元素)存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小元素（或最大元素)然后放到已排序序列的末尾，重复上述步骤，直到所有元素均排序完毕。

平均时间复杂度

O （n ^ 2），不稳定

图示排序过程：

选择排序和冒泡排序区别：

冒泡排序是在每轮遍历中比较相邻的元素，如果顺序不正确就交换位置，逐渐将最大（或最小）的元素冒泡到合适的位置，每轮可能需要进行多次元素交换。选择排序是在每一轮遍历中选择未排序部分的最小（或最大）元素，然后将其放到已排序部分的末尾，每轮只需进行一次元素交换。冒泡排序稳定，选择排序不稳定。

参考链接：选择排序动画演示

选择排序C语言源程序：

#include <stdio.h>
void BubbleSort(int a[],int n);//冒泡排序
void DispArray(int a[],int n); //输出数组
void ChooseSort(int a[],int n);//选择排序

int main()
{
    int a[10]={0,3,2,1,4,6,5,7,9,8};

    //BubbleSort(a,10);
    ChooseSort(a,10);
    DispArray(a,10);

    return 0;
}

void BubbleSort(int a[],int n)//冒泡排序
{
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1;j++){
            if(a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

void ChooseSort(int a[],int n)//选择排序
{
    for(int i=0;i<n-1;i++){
        int k=i;
        for(int j=i+1;j<n;j++){
            if(a[k]>a[j]){
                int temp=a[k];
                a[k]=a[j];
                a[j]=temp;
            }  
        }
    }
}
void DispArray(int a[],int n)//输出数组
{
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}

运行结果：

3. 快速排序

基本原理：

1.选定Pivot中心轴 2.将大于Pivot的数字放在Pivot的右边 3.将小于Pivot的数字放在Pivot的左边 4.分别对左右子序列重复前三步操作，直至子序列长度为1

平均时间复杂度

O （ n log n ），不稳定

图示排序过程：

快速排序优势：

快速排序通常比冒泡排序和选择排序等简单排序算法要快得多，因此在实际应用中常被选为首选排序算法。在平均情况下，它的时间复杂度为O(n log n)。

参考链接：快速排序视频讲解

快速排序C语言源程序：

#include <stdio.h>
void BubbleSort(int a[],int n);//冒泡排序
void DispArray(int a[],int n); //输出数组
void ChooseSort(int a[],int n);//选择排序
void FastSort(int a[],int L,int R);//快速排序

int main()
{
    int a[10]={0,3,2,1,4,6,5,7,9,8};

    //BubbleSort(a,10);
    //ChooseSort(a,10);
    FastSort(a,0,9);
    DispArray(a,10);

    return 0;
}

void BubbleSort(int a[],int n)//冒泡排序
{
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1;j++){
            if(a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

void ChooseSort(int a[],int n)//选择排序
{
    for(int i=0;i<n-1;i++){
        int k=i;
        for(int j=i+1;j<n;j++){
            if(a[k]>a[j]){
                int temp=a[k];
                a[k]=a[j];
                a[j]=temp;
            }  
        }
    }
}

void FastSort(int a[],int L,int R)//快速排序
{
    int left=L,right=R;
    int pivot=a[left];
    while (left<right)
    {
        while (left<right && pivot<=a[right])
        {
            right--;
        }
        if(left<right){
            a[left]=a[right];
        }
        while (left<right && pivot>=a[left])
        {
            left++;
        }
        if(left<right){
            a[right]=a[left];
        }
        
        if(left>=right){
            a[right]=pivot;
        }

        FastSort(a,L,left-1);
        FastSort(a,left+1,R);
    }
    
}
void DispArray(int a[],int n)//输出数组
{
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}

运行结果：