FDS（一）：排序算法

FDS之排序算法

前言

以排序算法作为起始，我也不知道合不合适

排序问题有许多有趣的算法解决方案，体现了许多计算机科学的思想：

1. 比较和非比较的策略
2. 迭代与递归实现
3. 分治范式（例如，并归排序或快速排序）
4. 最好/最坏/平均时间复杂度分析
5. 随机算法

本文将实现：

1. 基于比较的排序算法：
   • BUB 冒泡排序
   • SEL 选择排序
   • INS 插入排序
   • MER 并归排序（递归实现）
   • QUI 快速排序 （递归实现）
   • R-Q 随机快速排序 （递归实现）
2. 不基于比较的排序算法：
   • COU 计数排序
   • RAD 基数排序

关于算法的稳定性：我之前一直有一个误区：以为是不一定能排序成功所以叫做不稳定排序，实际上都是能排成功的。

那什么是稳定性呢？简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。

1 基于比较的排序算法

BUB,SEL,INS 最容易实现，但不是效率最高的，他们的时间复杂度是O(N^2^)

1.1 冒泡排序

算法时间复杂度

​ 最坏情况：O(n^2)

​ 最好情况：O(n)

​ 平均情况：O(n^2)

算法空间复杂度：S(n)=O(1)

算法稳定性：稳定排序

#include<stdio.h>
int main()
{
    int n,num[100];
    int i,j,temp;
    while(scanf("%d",&n)!=EOF)//这一行语句非常有意义
    {
        for(i = 0;i < n;i++)
            scanf("%d",&num[i]);
        for(i = 0;i < n - 1;i++)
            for(j = 0;j < n - i - 1;j++)//优化，因为最后一位在一轮冒泡后一定处于正确的位置
            {
                if(num[j] > num[j + 1])
                {
                    temp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = temp;
                }
            }
        for(i = 0;i < n;i++)
        {
            printf("%d ",num[i]);
        }
        printf("\n");
    }
    return 0;
}

1.2 选择排序

算法时间复杂度

​ 最坏情况：O(n^2)

​ 最好情况：O(1) //即不需要排序，本身已是正序

​ 平均情况：O(n^2)

算法空间复杂度：S(n)=O(1)

算法稳定性：不稳定排序

#include<stdio.h>
int main()
{
    int a[10];
    int i=0;
    for(i=0;i<10;i++)
    scanf("%d",&a[i]);
    for(int i = 0;i<10;i++ )
    {
        int temp = i;           //就是从第一个开始，寻找每个[i,10]区间上的最小值，并且与i交换
        for(int j =i;j<10;j++)
        {
            if(a[temp]>a[j])
            {
                temp = j;    //temp用于记录其最小值的位置
            }
        }
        if(temp!=i)
        {
            int t = a[i];
            a[i] = a[temp];
            a[temp] = t;
        }
    }
    for(int i = 0;i<10;i++)
    printf("%d\n",a[i]);
}

1.3 插入排序

算法时间复杂度

​ 最坏情况：O(n^2)

​ 最好情况：O(n)

​ 平均情况：O(n^2)

算法空间复杂度：S(n)=O(1)

算法稳定性：稳定排序