AI 助理
备案控制台
开发者社区 人工智能 文章 正文

常见排序算法（C语言实现）（下）

2023-04-25 120
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 常见排序算法（C语言实现）
挖坑法


1.基本介绍：

 挖坑法是基于Hoare的，他通过挖坑的方法避免了R和L相遇时的值一定小于key值的问题，因为不是所有人都能理解为什么R和L相遇时的值是小于key值的。但是像Hoare一样，它也需要根据key值的选定来决定是R先走还是L先走。

 挖坑法一开始会取出key值，然后R移动找到比key值小的值，把这里的值填到L的位置上，随后L开始移动，找到比key值大的值填到R的位置上，然后R又开始移动，重复上述步骤，直到R和L相遇，最后把key值填入。

2.代码：

void QuickSortPit(int* a, int begin, int end)
{
  // 当只有一个数据或数列不存在时
  if (begin >= end)
    return;
  int left = begin;
  int right = end;
  int key = a[left];
  int pit = left;
  while (left < right)
  {
    // 右边先走，找比key值小的值
    while (left < right && a[right] >= key)
    {
      right--;
    }
    a[pit] = a[right];
    pit = right;
    // 左边再走，找比key值大的值
    while (left < right && a[left] <= key)
    {
      left++;
    }
    a[pit] = a[left];
    pit = left;
  }
  a[pit] = key;
  QuickSortPit(a, begin, pit - 1);
  QuickSortPit(a, pit + 1, end);
}

3.时间复杂度与空间复杂度：

 核心思想并没有什么变化，换汤不换药，所以时间复杂度与Hoare版本是一样的。

4.图示：


image.gif


前后指针版本


1.基本介绍：

 这个是Hoare的一种变形，还是取一个key值，然后取prev和cur分别指向第一个元素和第二个元素，然后cur向后移动，遇到比key小的值，cur的值就和prev的值交换，遇到比key大的值cur就继续走。这样prev就两种情况与cur在同一位置，或者是停留在值比key值大的位置上，最后cur走到end后，就把prev与key交换，这样也就完成了左右子序列区分的任务。

 这是一种Hoare的变形，过程不容易理解，但是代码容易实现。

2.代码：

void QuickSortPoint(int* a, int begin, int end)
{
  if (begin >= end)
    return;
  int keyI = begin;
  int prev = begin;
  int cur = begin + 1;
  while (cur <= end)
  {
    // 找到比key小的值时，与prev++位置交换，小的向前移动，大的向后移动
    if (a[cur] < a[keyI] && ++prev != cur)
    {
      int tmp = a[prev];
      a[prev] = a[cur];
      a[cur] = tmp;
    }
    cur++;
  }
  int tmp = a[prev];
  a[prev] = a[keyI];
  a[keyI] = tmp;
  keyI = prev;
  QuickSortPoint(a, begin, keyI - 1);
  QuickSortPoint(a, keyI + 1, end);
}

3.时间复杂度与空间复杂度：

 时间复杂度与空间复杂度仍旧与Hoare版本的一样。

4.图示

e8303122daf94975a28bb49ae90353ac.gif

非递归实现

首先我们要知道一个点，每次递归都会开辟一次栈帧空间，而栈帧空间有一个特点就是先开辟的空间最后销毁，但是这也造成了一个问题，如果递归层度过深就会栈溢出。但是快排又依赖于这一先入栈后销毁的特性完成排序。所以我们要实现非递归的快排就需要实现这一特性，而在我们的数据结构中恰好有一个栈的数据结构是具备这种特性的，所以如果我们要非递归实现快排，就要使用栈这个数据结构。

Hoare版本
int Hoare(int* a, int begin, int end)
{
  int left = begin, right = end;
  int keyI = left;
  while (left < right)
  {
    // 右边先走，找小于key值的值
    while (left < right && a[right] >= a[keyI])
      right--;
    // 左边后走，找大于key值的值
    while (right < right && a[left] <= a[keyI])
      left++;
    int tmp = a[left];
    a[left] = a[right];
    a[right] = tmp;
  }
  int tmp = a[left];
  a[left] = a[keyI];
  a[keyI] = a[left];
  keyI = left;
  return keyI;
}
void QuickSortNonR(int* a, int begin, int end)
{
  // 创建、初始化栈，将begin、end插入栈中
  Stack st;
  StackInit(&st);
  StackPush(&st, begin);
  StackPush(&st, end);
  // 栈非空就循环
  while (!StackEmpty(&st))
  {
    int right = StackTop(&st);
    StackPop(&st);
    if (StackEmpty(&st))
      break;
    int left = StackTop(&st);
    StackPop(&st);
    if (StackEmpty(&st))
      break;
    int keyI = Hoare(a, left, right);
    if (keyI + 1 < right)
    {
      StackPush(&st, keyI + 1);
      StackPush(&st, right);
    }
    if (left < keyI - 1)
    {
      StackPush(&st, left);
      StackPush(&st, keyI - 1);
    }
  }
  StackDestroy(&st);
}
挖坑法
int Pit(int* a, int begin, int end)
{
  int left = begin;
  int right = end;
  int key = a[left];
  int pit = left;
  while (left < right)
  {
    // 右边先走，找比key值小的值
    while (left < right && a[right] >= key)
    {
      right--;
    }
    a[pit] = a[right];
    pit = right;
    // 左边再走，找比key值大的值
    while (left < right && a[left] <= key)
    {
      left++;
    }
    a[pit] = a[left];
    pit = left;
  }
  a[pit] = key;
  return pit;
}
void QuickSortNonR(int* a, int begin, int end)
{
  // 创建、初始化栈，将begin、end插入栈中
  Stack st;
  StackInit(&st);
  StackPush(&st, begin);
  StackPush(&st, end);
  // 栈非空就循环
  while (!StackEmpty(&st))
  {
    int right = StackTop(&st);
    StackPop(&st);
    if (StackEmpty(&st))
      break;
    int left = StackTop(&st);
    StackPop(&st);
    if (StackEmpty(&st))
      break;
    int keyI = Pit(a, left, right);
    if (keyI + 1 < right)
    {
      StackPush(&st, keyI + 1);
      StackPush(&st, right);
    }
    if (left < keyI - 1)
    {
      StackPush(&st, left);
      StackPush(&st, keyI - 1);
    }
  }
  StackDestroy(&st);
}
前后指针版本
int Point(int* a, int begin, int end)
{
  int keyI = begin;
  int prev = begin;
  int cur = begin + 1;
  while (cur <= end)
  {
    // 找到比key小的值时，与prev++位置交换，小的向前移动，大的向后移动
    if (a[cur] < a[keyI] && ++prev != cur)
    {
      int tmp = a[prev];
      a[prev] = a[cur];
      a[cur] = tmp;
    }
    cur++;
  }
  int tmp = a[prev];
  a[prev] = a[keyI];
  a[keyI] = tmp;
  keyI = prev;
  return keyI;
}
void QuickSortNonR(int* a, int begin, int end)
{
  // 创建、初始化栈，将begin、end插入栈中
  Stack st;
  StackInit(&st);
  StackPush(&st, begin);
  StackPush(&st, end);
  // 栈非空就循环
  while (!StackEmpty(&st))
  {
    int right = StackTop(&st);
    StackPop(&st);
    if (StackEmpty(&st))
      break;
    int left = StackTop(&st);
    StackPop(&st);
    if (StackEmpty(&st))
      break;
    int keyI = Point(a, left, right);
    if (keyI + 1 < right)
    {
      StackPush(&st, keyI + 1);
      StackPush(&st, right);
    }
    if (left < keyI - 1)
    {
      StackPush(&st, left);
      StackPush(&st, keyI - 1);
    }
  }
  StackDestroy(&st);
}

快排的优化

三值取中

我们之前提到过，如果每次key值的位置恰好在最边上，那么快排的的时间效率就会变成O(n2)，虽然这样的概率很小，但是还是有概率会出现。这时我们可以采用三值取中法来避免这种的情况发生。因为key值是影响划分次数的关键，三值取中，就是找到首、中、尾三个位置的值，比较大小，将中间大小的值与key值交换，这样就能保证key值的位置不会是在最边上。

int GetMidIndex(int* a, int begin, int end)
{
  int mid = (begin + end) / 2;
  if (a[begin] < a[mid])
  {
    if (a[mid] < a[end])
    {
      return mid;
    }
    else if (a[begin] > a[end])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
  else // a[begin] > a[mid]
  {
    if (a[mid] > a[end])
    {
      return mid;
    }
    else if (a[begin] < a[end])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
}
小区间优化

  每一层的递归都会以2倍数进行增长，即1,2,4,8,16……，通过这个数列我们可以发现，在逻辑上只要我们减少一层递归，就能减少约一半的递归次数。所以我们可以结合其他排序，进行一个判断，在只有多少数的时候就采用其他排序，这样就能有效的避免递归过深。

void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  if ((end - begin + 1) < 15)
  {
    // 小区间用直接插入替代，减少递归调用次数
    InsertSort(a + begin, end - begin + 1);
  }
  else
  {
    int keyi = PartSort3(a, begin, end);
    // [begin, keyi-1]  keyi [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
  }
}

归并排序

递归实现

  1. 基本介绍：

归并排序是建立在归并操作上的一种有效的排序算法，它采用了分治的思想。将已经有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，然后合并成一个有序的序列。将两个有序表合并成一个有序表叫做二路归并。归并排序需要先分解，在合并。

image.png

  1. 代码：
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
    return;
  int mid = (begin + end) / 2;
  // [begin, mid] [mid+1, end] 递归让子区间有序
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid+1, end, tmp);
  // 归并[begin, mid] [mid+1, end]
  int begin1 = begin, end1 = mid;
  int begin2 = mid+1, end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] <= a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int)*n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
  tmp = NULL;
}
  1. 时间复杂度与空间复杂度：
      归并排序有点类似二叉树结构，高度O(logn)，每层循环n次，所以时间复杂度O(n*logn)；
      归并排序额外开辟了n个空间加上递归的logn，所以空间复杂度为O(n+logn），但是logn是可以忽略掉的，最后的复杂度为O(n)。
  2. 图示：

d48a988a7d804acca5fef4819fead68f.gif

非递归实现

基本介绍：

 归并排序的非递归算法并不需要借助栈这个数据结构来实现，如果使用了栈反而会非常的麻烦，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序。

 但是我们需要考虑到一些特殊情况，因为归并是两两归并的，也就是它归并的元素个数是1,2,4,8,16……这样增长的，那么如果元素个数不是这样标准的倍数呢？这时就会有三种情况。

 ①：最后一个分组中，右侧区间元素个数不够，此时我们合并序列，就需要对这个区间的边界进行控制；

 ②：最后一个分组中，右侧区间没有元素，就是元素刚好只够左侧区间，那么我们就不需要对这个分组进行合并，因为它本身已经是有序的了；

 ③：最后一个分组中，左侧区间的元素个数不够，那么我们就不需要对该小组进行合并了。

18389a36340947779ee6b262c7e88fac.png

代码：

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int)*n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  // 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并
  int rangeN = 1;
  while (rangeN < n)
  {
    for (int i = 0; i < n; i += 2 * rangeN)
    {
      // [begin1,end1][begin2,end2] 归并
      int begin1 = i, end1 = i + rangeN - 1;
      int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
      int j = i;
      // end1 begin2 end2 越界
      // 修正区间  ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝
      if (end1 >= n)
      {
        end1 = n - 1;
        // 不存在区间
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        // 不存在区间
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] <= a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
    }
    // 也可以整体归并完了再拷贝
    memcpy(a, tmp, sizeof(int)*(n));
    rangeN *= 2;
  }
  free(tmp);
  tmp = NULL;
}

计数排序

  1. 基本介绍：
      计数排序又称为鸽巢排序，是对哈希直接定址法的变形应用，是一种非比较排序。它先统计相同元素出现的次数，然后根据统计的结果将序列回收到原来的序列中。
      计数排序适用于数据范围集中的序列，此时效率很高，但是适用的范围及场景受到限制。
  2. 代码：
void CountSort(int* a, int n)
{
  int max = a[0], min = a[0];
  for (int i = 1; i < n; i++)
  {
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }
  int range = max - min + 1;
  int* countA = (int*)calloc(range, sizeof(int));
  if (NULL == countA)
  {
    perror("calloc fail\n");
    exit(-1);
  }
  // 统计次数
  for (int i = 0; i < n; i++)
    countA[a[i] - min]++;
  // 排序
  int k = 0;
  for (int j = 0; j < range; j++)
  {
    while (countA[j]--)
      a[k++] = j + min;
  }
  free(countA);
}
  1. 时间复杂度与空间复杂度：
      它的时间复杂度和空间复杂度都是由它自身元素的区间跨度决定的，时间复杂度是O(MAX(n,范围))，空间复杂度是O(范围)。
  2. 图示：

f5fec650132f493489c11f84864f6c48.gif

排序算法复杂度及稳定性分析

image.png

不同算法的运行效率

  数据过大可能会导致栈溢出，所以选择非递归的快排和归并排序来测试。

void TestOP()
{
  srand(time(0));
  const int N = 50000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  int* a7 = (int*)malloc(sizeof(int) * N);
  int* a8 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
    a7[i] = a1[i];
    a8[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  BubbleSort(a5, N);
  int end5 = clock();
  int begin6 = clock();
  QuickSortNonR(a6, 0, N - 1);
  int end6 = clock();
  int begin7 = clock();
  MergeSortNonR(a7, N);
  int end7 = clock();
  int begin8 = clock();
  CountSort(a8, N);
  int end8 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("BubbleSort:%d\n", end5 - begin5);
  printf("QuickSort:%d\n", end6 - begin6);
  printf("MergeSort:%d\n", end7 - begin7);
  printf("CountSort:%d\n", end8 - begin8);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
  free(a8);
}

1a863479bc7f4e4281caf0cad00268ad.png

文章标签：
C语言
搜索推荐
算法
关键词：
排序算法C语言
算法c语言
C语言排序算法
姜君竹
目录
相关文章
ephemerals__
|
2月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现（c语言）
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低，而三路快排通过将数组分为三部分（小于、等于、大于基准值）来优化这一问题。文章详细讲解了三路快排的实现步骤，并提供了完整的代码示例。
ephemerals__
62 4
土木林森
|
5月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树：一场数据结构与算法的华丽舞蹈，让你的程序效率飙升，直击性能巅峰！"
【8月更文挑战第20天】红黑树是自平衡二叉查找树，通过旋转和重着色保持平衡，确保高效执行插入、删除和查找操作，时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中，节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架，用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
土木林森
117 1
土木林森
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
65 1
ephemerals__
|
2月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
142 7
ephemerals__
|
2月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
122 8
倔强的石头_
|
7月前
|
存储 算法 C语言
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
倔强的石头_
81 3
aliyun1622584902-46568
|
7月前
|
算法 C语言
C语言----判断n是否是2的次方数，利用到按位与&，算法n&(n-1)
C语言----判断n是否是2的次方数，利用到按位与&，算法n&(n-1)
aliyun1622584902-46568
79 2
陈佳烨
|
7月前
|
算法 Java C语言
Java中的算法与C语言中的函数
Java中的算法与C语言中的函数
陈佳烨
47 2
反季雪
|
7月前
|
存储 算法 搜索推荐
【数据结构和算法】--- 基于c语言排序算法的实现（2）
【数据结构和算法】--- 基于c语言排序算法的实现（2）
反季雪
41 0
反季雪
|
7月前
|
搜索推荐 算法 C语言
【数据结构和算法】--- 基于c语言排序算法的实现（1）
【数据结构和算法】--- 基于c语言排序算法的实现（1）
反季雪
53 0

热门文章

最新文章

  • 1
    【C语言】深入浅出：C语言链表的全面解析
  • 2
    【C语言】输入/输出函数详解
  • 3
    【C语言】宏定义详解
  • 4
    C 语言中所有可用的关系运算符
  • 5
    【c语言】运算符汇总（万字解析）
  • 6
    【C语言】结构体详解 -《探索C语言的 “小宇宙” 》
  • 7
    【C语言】enum 关键字详解
  • 8
    C 语言中的数据类型转换：连接不同数据世界的桥梁
  • 9
    【C语言】原码、反码、补码详解 -《码上有道 ! 》
  • 10
    【C语言】深入解析C语言结构体：定义、声明与高级应用实践
  • 1
    【Paddle】PCA线性代数基础 + 领域应用：人脸识别算法（1.1w字超详细：附公式、代码）
    126
  • 2
    BASE64的算法说明
    70
  • 3
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    119
  • 4
    理解并应用机器学习算法：决策树
    150
  • 5
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    442
  • 6
    【机器学习】为什么K-means算法使用欧式距离度量？
    434
  • 7
    【机器学习】描述K-means算法的步骤
    158
  • 8
    【机器学习】K-means和KNN算法有什么区别？
    670
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    63
  • 10
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    66

    • 相关课程

    更多
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 语言入门-2：基本类型
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月