十大经典排序算法（C语言实现）(一)

2023-06-20 124

版权

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

简介： 十大经典排序算法（C语言实现）(一)

前言

本文代码链接：十大经典排序算法

提取码：2ok3

排序算法是《数据结构与算法》的重要组成部分，在项目实践中，很多时候都需要用到排序算法，而常见的经典排序算法也是很多公司程序员面试的重点。十大经典排序算法如下图所示。

时间复杂度和空间复杂度是衡量一个算法性能好坏的重要指标。而对于排序算法而言，稳定性也是重要指标之一。

教材上给了非常严谨且抽象的定义。

假设ki=kj(1<=i<=n,1<=j<=n,i≠j),且在排序前的序列中ri领先于rj，若果排序后ri仍然领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。

通俗地说，有时候在原序列中两个数值是相等的，如果排序后可以保证原来的相对位置不变，则称该算法是稳定的，若不能保证，则算法是不稳定的。

关于算法的时间复杂度，空间复杂度，稳定性，见下面表格。

1 冒泡排序

冒泡排序是一种交换排序，其基本思想是：两两比较相邻记录的关键字，如果相反则交换，直到没有反序的记录为止。

因较小的数字如同气泡一般慢慢浮到上面，故而得名冒泡排序。

1.1 最简单的排序算法

代码如下：

#include <stdio.h>
#define MAXSIZE 10000
typedef struct
{
  int r[MAXSIZE + 1];
  int length;
}sqList;
void swap(sqList* L, int i, int j)
{
  int temp = L->r[i];
  L->r[i] = L->r[j];
  L->r[j] = temp;
}
void Bubblesort0(sqList* L)
{
  for (int i = 0; i < L->length; i++)
  {
    for (int j = i; j < L->length; j++)
    {
      if (L->r[i] > L->r[j])
        swap(L, i, j);
    }
  }
}
int main()
{
  sqList test = {{9,1,5,8,3,7,4,6,2}, 9};
  Bubblesort0(&test);
  for (int i = 0; i < test.length; i++)
    printf("%d\t", test.r[i]);
 return 0;
}

以上是最简单的冒泡排序算法的实现，每次循环保证得到该范围内的最小值，排在前面，从而完成排序。如图所示：

然而还有改进的空间。是否可在每次循环的时候，比较更多的关键字呢？于是有了改进版的冒泡排序。

1.2 冒泡排序算法

通过以上的改进思路，可以得到一下的代码。

#include <stdio.h>
#define MAXSIZE 10000
typedef struct
{
  int r[MAXSIZE + 1];
  int length;
}sqList;
void swap(sqList* L, int i, int j)
{
  int temp = L->r[i];
  L->r[i] = L->r[j];
  L->r[j] = temp;
}
void Bubblesort1(sqList* L)
{
  for (int i = 0; i < L->length; i++)
  {
    for (int j = L->length - 2; j >= i; j--)
    {
      if (L->r[j] > L->r[j+1])
        swap(L, j, j + 1);
    }
  }
}
int main()
{
  sqList test = {{9,1,5,8,3,7,4,6,2}, 9};
  Bubblesort1(&test);
  for (int i = 0; i < test.length; i++)
    printf("%d\t", test.r[i]);
 return 0;
}

通过以上的改进，在每次循环时，可以比较相邻的关键字，从而变得更加高效。如下图所示：

从上图可以看出，一次循环就可以比较更多的数值。所以是个更好的方法。

1.3 冒泡排序算法优化

上面的例子虽然是正宗的冒泡排序算法，但是仍然有改进的空间，如果能在需要排序的数组有序的时候停止循环，肯定会更加高效，于是有了下面的代码。

#include <stdio.h>
#define MAXSIZE 10000
#define TRUE 1
#define FALSE 0
typedef struct
{
  int r[MAXSIZE + 1];
  int length;
}sqList;
void swap(sqList* L, int i, int j)
{
  int temp = L->r[i];
  L->r[i] = L->r[j];
  L->r[j] = temp;
}
void Bubblesort2(sqList* L)
{
  short flag = TRUE;
  for (int i = 0; i < L->length && flag; i++)
  {
    flag = FALSE;
    for (int j = L->length - 2; j >= i; j--)
    {
      if (L->r[j] > L->r[j + 1])
      {
        swap(L, j, j + 1);
        flag = TRUE;
      }
    }
  }
}
int main()
{
  sqList test = {{9,1,5,8,3,7,4,6,2}, 9};
  Bubblesort2(&test);
  for (int i = 0; i < test.length; i++)
    printf("%d\t", test.r[i]);
 return 0;
}

这样一来就避免了无意义的循环，如果上次发现算法已经完成了排序，程序就不会进入循环，从而提前结束运行，完成排序任务。

1.4 冒泡排序算法总结

冒泡算法是最常用的算法之一，也是最简单的排序算法之一，但却不是最高效的，以下将介绍其他几种排序算法。

2 选择排序

选择排序的方法也非常好理解，但它并不像冒泡排序一样，遇到顺序不合适的就直接调换位置，而是记录下最小关键字的位置，待循环完毕后再将其与此次循环的第一个关键字的位置做调换，从而保证了每次循环都可以得到该范围内的最小值，故而得名选择排序。

2.1 选择排序的代码实现

具体的实现代码如下。

#include <stdio.h>
#define MAXSIZE 10000
#define TRUE 1
#define FALSE 0
typedef struct
{
  int r[MAXSIZE + 1];
  int length;
}sqList;
void swap(sqList* L, int i, int j)
{
  int temp = L->r[i];
  L->r[i] = L->r[j];
  L->r[j] = temp;
}
void SelectSort(sqList *L)
{
  int i, j, min;
  for (i = 0; i < L->length; i++)
  {
    min = i;
    for (j = i + 1; j < L->length; j++)
    {
      if (L->r[min] > L->r[j])
        min = j;
    }
    if (i != min)
      swap(L, i, min);
  }
}
int main()
{
  sqList test = {{9,1,5,8,3,7,4,6,2}, 9};
  SelectSort(&test);
  for (int i = 0; i < test.length; i++)
  printf("%d\t", test.r[i]);
  return 0;
}

通俗地理解，就是不轻易“出手”，外部循环一次，最多调换一次，所以相比冒泡排序稍微高效一些。选择排序的过程如下图所示：

2.2 选择排序算法总结

虽然选择排序比冒泡排序高效一些，但仍然是n²的时间复杂度。

3 插入排序

插入排序又叫直接插入排序或者简单插入排序，这样称呼其实是为了与希尔排序进行区分，其实是同一种排序算法。

所谓插入排序，是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数值增1的有序表。

3.1 插入排序的代码实现

插入排序的具体代码如下所示。

注意在插入排序中有个辅助空间，所以数组的第一个元素值为0，排序后的值无效。

#include <stdio.h>
#define MAXSIZE 10000
#define TRUE 1
#define FALSE 0
typedef struct
{
  int r[MAXSIZE + 1];
  int length;
}sqList;
void InsertSort(sqList *L)
{
  int i, j;
  for (i = 2; i < L->length; i++)
  {
    if (L->r[i] < L->r[i - 1])
    {
      L->r[0] = L->r[i];
      for (j = i - 1; L->r[j] > L->r[0]; j--)
        L->r[j + 1] = L->r[j];
      L->r[j + 1] = L->r[0];
    }
  }
}
int main()
{
  sqList test = {{0,9,1,5,8,3,7,4,6,2}, 10};
  InsertSort(&test);
  for (int i = 0; i < test.length; i++)
  printf("%d\t", test.r[i]);
  return 0;
}

插入排序的算法思想可简单理解为，首先确定需要排序的关键字，然后再放到整个数组的第一个位置，再将其放回原数组中，放回的时候进行排序，但只保证该位置及其前面关键字的相对位置没有问题。

如图所示：

从上图中可以看出，所谓的插入排序，是两两进行比较，若发现顺序相反，则将其放入辅助空间中，然后调整其他元素的位置，找到合适的位置插入，从而完成此次排序。

3.2 插入排序算法总结

与冒泡排序和选择排序算法不同的是，插入排序算法需要一个额外的空间来存储数据，但其性能比前两者要稍微好一些，平均比较和移动的次数约为（n²）/4。