首页 算法与数据结构

这里总结如下算法：

  • 基于比较的排序算法：
    冒泡排序
    选择排序
    插入排序
    归并排序
    快速排序
  • 不基于比较的排序算法：
    计数排序
    基数排序

# 写在前面

这次的算法实现全都使用 C 语言，并不是说 C 有多好，只是因为 C 比较接近底层，掌握 C 的写法后，其他语言的写法也很好实现，其次，也是因为现在很多算法的讲解也使用 C。

然后，本文的算法实现可能还不够完美，虽然都经过了测试用例，但难免还有些疏忽，如有错误或是有更好的意见，欢迎提出。

# 基于比较的排序算法 - O (N^2)

# 冒泡排序

# 核心原理

从左到右，依次将较大的元素交换到后面，那么一次一次排序后，最大的元素就在数组末尾，然后不断重复。

给定一个 N 个元素的数组，冒泡法排序将：

  1. 如果元素大小关系不正确，交换这两个数（在本例中为 a> b）
  2. 比较一对相邻元素（a，b）
  3. 重复步骤 1 和 2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
  4. 到目前为止，最大的元素将在最后的位置。 然后我们将 N 减少 1，并重复步骤 1，直到 N = 1。

(引用 VisuAlgo)

可视化见 VisuAlgo

# 算法实现

#define BOOL size_t
#define FALSE 0
#define TRUE 1
// 原地排序
void bubbleSort(int *arr, int len)
{
    BOOL exchanged = FALSE;
    int last = len; //last 随着冒泡次数而减小
    do
    {
        for (int i = 0; i < last; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                // 交换前后项
                //int 整数型可以使用这种算法，不使用中间变量
                arr[i] ^= arr[i + 1];
                arr[i + 1] ^= arr[i];
                arr[i] ^= arr[i + 1];
                // 交换过了
                exchanged = TRUE;
            }
        }
        last--;// 当 last 减到 0 时，说明已经遍历结束，结束排序
    } while (exchanged && last > 0); // 如果一次冒泡后没有发生交换，说明数组已经有序，结束排序
}
# 选择排序


# 核心原理


从左到右，选择未被排序的数里最小的那个，与数组第一个数交换，然后第二个… 不断重复。




给定 N 个项目和 L = 0 的数组，选择排序将：


    

  1. 在 [L … N-1] 范围内找出最小项目 X 的位置
    2. 

  2. 用第 L 项交换 X
    3. 

  3. 将下限 L 增加 1 并重复步骤 1 直到 L = N-2。
    4. 



(引用 VisuAlgo)




可视化见 VisuAlgo


# 算法实现


// 原地排序
void selectSort(int *arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        // 找出未被排序的数里最小的那个
        int min = arr[i];
        int minIdx = i;
        for (int j = i; j < len; j++)
        {
            if (min > arr[j])
            {
                min = arr[j];
                minIdx = j;
            }
        }
        // 交换
        arr[minIdx] = arr[i];
        arr[i] = min;
    }
}
# 插入排序


# 核心原理


将未排序的数依次插入到排序好的数中




插入排序类似于大多数人安排扑克牌的方式。


    

  1. 从你手中的一张牌开始
    2. 

  2. 选择下一张卡并将其插入到正确的排序顺序中
    3. 

  3. 对所有的卡重复上一步。
    4. 



(引自 VisuAlgo)




可视化见 VisuAlgo


# 算法实现


// 原地排序
void insertSort(int *arr, int len)
{
    for (int i = 1; i < len; i++) // 这里默认第一个数就是排好序的，所以索引从第二个数开始
    { 
        // 将未排序的数插入到排序好的数中
        for (int j = 0; j < i; j++)
        {
            if (arr[i] < arr[j]) // 插入
            { 
                // 先缓存要插入的数，因为后面要移动前面的数列，会覆盖它
                int n = arr[i];
                // 移动数列
                for (int k = i; k > j; k--)
                    arr[k] = arr[k - 1];
                // 放入正确的位置
                arr[j] = n;
            }
        }
    }
}
# 优点 & 缺点


# 优点


这几个排序算法比较简单，容易想到，也比较容易理解算法原理。


# 缺点


在数据量变大时，运行效率会非常低，不是很实用。


# 基于比较的排序算法 - O (N log N)


# 归并排序


# 核心原理


将待排序的数组一分为二，分别对左右数组排序，排序时再一分为二，直到分成单个元素，排序完成后再依次合并。




给定一个 N 个项目的数组，归并排序将：


    

  1. 将每对单个元素（默认情况下，已排序）归并为 2 个元素的有序数组
    2. 

  2. 将 2 个元素的每对有序数组归并成 4 个元素的有序数组，重复这个过程…
    3. 

  3. 最后一步：归并 2 个 N / 2 元素的排序数组（为了简化讨论，我们假设 N 是偶数）以获得完全排序的 N 个元素数组。
    4. 



(引自 VisuAlgo)




可视化见 VisuAlgo


# 算法实现


注：需要 O (n) 的额外空间


// 借助临时数组进行排序
void merge(int *arr, int low, int mid, int high) // 归并排序子函数
{
    int N = high - low + 1;                   // 要排序的数字个数
    int *b = (int *)malloc(N * sizeof(int));  // 创建一个新的数组用来排序
    int lIdx = low, rIdx = mid + 1, bIdx = 0; //lIdx-> 左边数组索引，rIdx-> 右边数组索引，bIdx-> 数组 b 的索引
    // 因为在 low~mid 和 mid+1~high 之间的数都是有序的（从小到大的），所以可以这样
    while (lIdx <= mid && rIdx <= high)
    {
        if (arr[lIdx] < arr[rIdx])
        {
            b[bIdx] = arr[lIdx];
            lIdx++;
        }
        else
        {
            b[bIdx] = arr[rIdx];
            rIdx++;
        }
        bIdx++;
    }
    // 可能左数组或右数组还有剩余项
    // 比如：左数组所有数都小于右数组数的情况下
    while (lIdx <= mid)
        b[bIdx++] = arr[lIdx++];
    while (rIdx <= high)
        b[bIdx++] = arr[rIdx++];
    // 现在数组 b 中是已经排好序的数，再给它们复制回 arr 中
    for (int i = 0, j = low; i < N; i++, j++)
    {
        arr[j] = b[i];
    }
    free(b);
}
void mergeSort(int *arr, int low, int high) // 归并排序
{
    if (low < high)
    {
        // 将待排序的数组一分为二，递归
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high); // 注：这里的 mid+1 只要和 merge 子函数里 rIdx 的值保持相同就行
        // 归并
        merge(arr, low, mid, high); //mid 从这里传入，在 merge 子函数中 rIdx=mid+1
    }
}
在此基础上还可以加以改进，使得归并排序在原地排序（不借用中间数组），降低空间复杂度，但是似乎会提升时间复杂度O(N log^2 N)-wikipedia。


# 快速排序 - O (N^2)/O (N log N)


# 核心原理


    

  • 经典的快速排序 - O (N^2)/O (N log N)：在一开始先选择第一个数作为枢轴点 p，遍历剩余数，把所有小于 p 的数放在左边，所有大于 p 的数放在右边，然后把 p 放在中间；然后对左边的数组和右边的数组再分别重复上面的步骤。（不稳定）
    • 

  • 随机快速排序 - O (N log N)：在经典快速排序的基础上，每次随机选择枢轴点 p。（比较稳定）
    • 





划分步骤：


    

  1. 选择一个项目 p（称为枢轴点）
    2. 

  2. 然后将 a [i…j] 的项目分为三部分：a [i…m-1]，a [m] 和 a [m + 1…j]。 a [i…m-1]（可能为空）包含小于 p 的项目。 a [m] 是枢轴点 p，例如：指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1…j]（可能为空）包含大于或等于 p 的项目。
    3. 

  3. 然后，递归地对这两部分进行排序。
    4. 





可视化见 VisuAlgo


# 算法实现


// 原地排序
int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
    int p = arr[low]; // 选取第一个数作为枢轴点
    int m = low;      // 分界点，因为左右区域一开始都是空的，所以 m 要在 0 的位置
    for (int i = low + 1; i <= high; i++)
    {
        // 如果 arr [i]>=p，什么都不用做，继续下一次循环即可 (i++)
        if (arr[i] < p)
        {
            // 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
            m++;
            // 交换 arr [m] 和 arr [i]
            int tmp = arr[m];
            arr[m] = arr[i];
            arr[i] = tmp;
            // 进入下一次循环 i++
        }
    }
    // 交换枢轴点和分界点
    arr[low] = arr[m];
    arr[m] = p;
    // 返回枢轴点所在位置
    return m;
}
void quickSort(int *arr, int low, int high)// 快速排序
{
    if (low < high) // 如果 low>high，说明已经划分为单个
    {
        // 先划分为左右两个区域
        int m = partition(arr, low, high);
        // 再递归对左右两个区域排序
        // 注：m 所在位置已经在正确的位置了，所以不需要包括进去
        quickSort(arr, low, m - 1);
        quickSort(arr, m + 1, high);
    }
}
上面是经典快速排序，使用随机快速排序只需要让 p 随机选取即可。


int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
    int pIdx = (rand() % (high - low + 1)) + low; // 随机选取 [low,high]
    // 交换 arr [pIdx] 和 arr [low]
    int p = arr[pIdx];
    arr[pIdx] = arr[low];
    arr[low] = p;
    int m = low; // 分界点，因为左右区域一开始都是空的，所以 m 要在 0 的位置
    for (int i = low + 1; i <= high; i++)
    {
        // 如果 arr [i]>=p，什么都不用做，继续下一次循环即可 (i++)
        if (arr[i] < p)
        {
            // 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
            m++;
            // 交换 arr [m] 和 arr [i]
            int tmp = arr[m];
            arr[m] = arr[i];
            arr[i] = tmp;
            // 进入下一次循环 i++
        }
    }
    // 交换枢轴点和分界点
    arr[low] = arr[m];
    arr[m] = p;
    // 返回枢轴点所在位置
    return m;
}
void quickSort(int *arr, int low, int high) // 随机快速排序
{
    srand((unsigned)time(NULL));
    if (low < high) // 如果 low>high，说明已经划分为单个
    {
        // 先划分为左右两个区域
        int m = partition(arr, low, high);
        // 再递归对左右两个区域排序
        // 注：m 所在位置已经在正确的位置了，所以不需要包括进去
        quickSort(arr, low, m - 1);
        quickSort(arr, m + 1, high);
    }
}
# 优点 & 缺点


# 优点


在基于比较的排序算法中已经是最快的了（当然还可以针对不同的数据继续优化），比较实用，在数据量大的情况下表现也不错，可能是现在使用最多的排序算法。


# 缺点


归并排序需要额外的空间，快速排序不是稳定的排序（即它会交换同样大小的数字的顺序）。


# 不基于比较的排序算法


# 计数排序 - O (n+k)


# 核心原理


针对小范围的自然数，统计每个数字出现的次数，然后按照从小到大依次输出。




如果要排序的项目是小范围的整数，我们可以计算每个整数（在这个小范围内）的出现频率，然后通过循环该小范围来按排序顺序输出项目。


(引自 VisuAlgo)




# 算法实现


注：需要 O (n+k) 的额外空间


// 借助临时数组排序
void countSort(int *arr, int len, int maxNum) // 计数排序
{
    int *con = (int *)calloc(maxNum + 1, sizeof(int));
    for (int i = 0; i < len; i++)
    {
        con[arr[i]]++; // 统计每个数字出现次数
    }
    for (int i = 0, idx = 0; i <= maxNum; i++)
    {
        while (con[i]-- > 0)
        {
            arr[idx++] = i; // 复制回去
        }
    }
    free(con);
}
# 基数排序 - O (kN)


# 核心原理


针对范围大但数位小的自然数，创建 10 个桶 (0-9)，按照指定数位，依次放入对应桶中，再放入顺序取出，对每个数位从低到高重复操作。




如果要排序的项目是大范围但小数位的整数，我们可以将计数排序（Counting Sort）思想与基数排序（Radix Sort）结合起来，以实现线性时间复杂度。

在基数排序中，我们将每个项目排序为一个 w 数字串（如果需要，我们填充小于 w 数字的前几个零的整数）。

对于最低有效位（最右边）到最高有效位（最左边），我们通过 N 个项目并将它们按照活动数字放到 10 个队列中（每个数字 [0…9] 一个），就好像 一个修改的计数排序，因为这保留了稳定性。 然后我们再次重新连接组，以便进行后续迭代。


(引自 VisuAlgo)




# 算法实现


注：需要 O (N+k) 的额外空间


void radixSort(int *arr, int len) // 基数排序
{
    int N = len / 10;         // 桶初始化可以装下的元素数 & 后续每次增加量
    int count[10] = {0};      // 每个桶当前装载的元素数量
    int maxCount[10] = {len}; // 每个桶当前能装下的最大元素数量，0 桶设置为 len，原因见下面
    // 初始化桶
    int **con = (int **)malloc(10 * sizeof(int *));
    // 最后遍历完所有数位后，所有的数都会过一遍 0 桶，所以一开始就设置为 len 的长度
    con[0] = (int *)malloc(len * sizeof(int));
    for (int i = 1; i < 10; i++)
    {
        con[i] = (int *)malloc(N * sizeof(int));
        maxCount[i] = N;
    }
    // 遍历每个数位
    BOOL ended = FALSE;
    for (int Bit = 10; Bit <= INT_MAX && !ended; Bit *= 10)
    {
        ended = TRUE;
        for (int i = 0; i < len; i++)
        {
            // 提取当前数位，并将该数放入桶中
            int radix = arr[i] % Bit / (Bit / 10); // 当前数位
            if (count[radix] >= maxCount[radix])
            {
                // 桶满了，重新分配内存空间
                maxCount[radix] *= 2;
                con[radix] = (int *)realloc(con[radix], maxCount[radix] * sizeof(int *));
                if (con[radix] == NULL)
                {
                    // 内存分配失败
                    exit(0);
                }
            }
            con[radix][count[radix]] = arr[i];
            count[radix]++;
        }
        for (int i = 1; i < 10; i++)
        {
            // 判断是否已经遍历结束
            if (count[i] > 0)
            {
                ended = FALSE;
                break;
            }
        }
        for (int i = 0, aIdx = 0; i < 10; i++)
        {
            // 把桶中的元素按照放入顺序放回数组
            for (int cIdx = 0; cIdx < count[i]; cIdx++)
            {
                arr[aIdx++] = con[i][cIdx];
            }
            count[i] = 0;
        }
    }
    for (int i = 0; i < 10; i++)
    {
        free(con[i]);
    }
    free(con);
}
# 优点 & 缺点


# 优点


基于比较的算法有 O (N log N) 的时间复杂度下限，而这些不基于比较的排序可以突破这个下限，使时间复杂度降到线性，针对于特定的数据是最优解。


# 缺点


对数据类型的要求比较苛刻，只在一些特定的数据集时有效。




参考文章:

VisuAlgo - 排序

 Wikipedia - 排序算法


      

          
      

  


   


    

  
    
      
    
    更新于
    
  
  
      
        
      
      阅读次数
      
      次
  



      


  
  
请我喝[茶]~(￣▽￣)~*

  

      
      

        TagBug 微信支付
        
微信支付

      

      
      

        TagBug 支付宝
        
支付宝