十大排序算法基本思想及其C语言实现

写在前面:这里是小王成长日志，一名普通在校大学生，想成学习之余将自己的学习笔记分享出来，记录自己的成长轨迹，帮助可能需要的人，平时博客内容主要是一些系统的学习笔记，项目实战笔记，一些技术的探究和自己的一些思考。欢迎大家关注，你们的每一个评论点赞关注我都会仔仔细细去看的。有任何问题欢迎交流，我会尽我所能帮助大家的，共创CSDN美好环境。

前几天想看一下排序算法，结果好几篇博客里都有问题，于是自己重新写了一篇，水平有限，此处不涉及算法复杂度及其优化，只是为了更好的理解。
下面的99%的代码都是手动敲出来的，参考了诸多资料，已经经过测试，可以放心食用。

推荐学习网站:菜鸟教程-十大经典排序算法 (有的地方还是讲的稍微晦涩,但是提供了多种语言实现,代码可能对初学者略难理解)

B站 (蛮多讲解视频可以看)

动画来源:菜鸟教程-十大经典排序算法

文章目录

• 十大排序算法基本思想及其C语言实现
• 1.冒泡排序
• 基本思想
• 动画
• 实现
• 2.选择排序
• 基本思想
• 动画
• 实现
• 3.插入排序
• 基本思想
• 实现
• 4.希尔排序
• 基本思想
• 动画
• 实现
• 5.归并排序
• 基本思想
• 动画
• 实现
• 6.快速排序
• 基本思想
• 动画
• 实现
• 7.堆排序
• 基本思想
• 动画
• 实现
• 8.计数排序
• 基本思想
• 动画
• 实现
• 9.桶排序
• 基本思想
• 动画
• 实现
• 10.基数排序
• 基本思想
• 动画
• 实现

1.冒泡排序

基本思想

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

动画

实现

void bubbleSort()
{
   //C实现
   int arr[] = {5, 9, 3, 8, 6};
   int len = 5; //数组长度也可以用<string.h>中的strlen函数获取数组长度
   int temp;
   for (int i = 0; i < len - 1; i++) //从小到大
   {                                 // 外循环为排序趟数，len个数进行len-1趟
      for (int j = 0; j < len - 1 - i; j++)
      { // 内循环为每趟比较的次数，第i趟比较len-i次,因为第一次已经将最大的元素冒泡到最后一个位置了
         if (arr[j] > arr[j + 1])
         { //相邻元素比较,逆序则将交换位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
         }
      }
   }

   //打印数组
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}

2.选择排序

基本思想

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

动画

实现

int arr[] = {5, 9, 3, 8, 6};
   int len = 5;                  //数组长度也可以用<string.h>中的strlen函数获取数组长度
   int index = 0;                //待会用来存储未排序区最大元素的位置索引
   for (int i = 0; i < len; i++) //从小到大
   {
      index = i;
      for (int j = i; j < len; j++) //用i之后的每一个元素去与i元素比较大小,若
      {
         if (arr[j] < arr[index])
         {
            index = j;
            //其实也可以直接交换的,但估计考虑了内存占用的一些因素,所以我们只存储满足条件的索引
         }
         //将i与index的元素调换位置
         if (i != index) //判断是否需要调换
         {
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
         }
      }
   }

   //打印数组
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}

3.插入排序

基本思想

插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而形成一个新的、记录数增1的有序表。

一般将第一个元素看做最小的有序组,然后用第二个元素插入到第一个元素组成的有序表中(其实就是个简单的比较大小),然后将第三个元素插入到前两个元素组成的有序表中,形成一个三个元素的有序表,以此类推,最终获得一个包含全部元素的有序表

实现

void insertionSort()
{
   int arr[] = {1, 5, 3, 9, 7};
   int len = 5;

   int i, j, key;
   for (i = 1; i < len; i++) //从1开始是因为默认第一个元素是最小的有序表
   {
      key = arr[i];
      j = i - 1; //a[j]是有序表后第一个元素,也是无序表第一个元素
      while ((j >= 0) && (arr[j] > key)) //从后往前遍历并且判断是否比要插入的数大 j>=0是为了防止数组越界(前面的界)
      {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = key; //得以跳出死循环的a[j]就是第一个比key小的第一个元素,将key置于其后一个位置,因为在从后往前遍历时所有比key大的值都向后移1位了
   }

   //打印数组
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}

4.希尔排序

基本思想

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本

基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

B站参考视频:哔哩哔哩

动画

实现

具体实现方法:

1. 把待排序列，分成多个间隔为gap的子序列，
2. 然后对每个子序列进行插入排序
3. 重复上述，每次间隔gap不同（并且越米越小），直到最后一次选取间隔gap=1，完成排序。
4. 我们一般是取数组长度的一半为第一个间隔,即第一次将整个数组分为len/2个子序列(下标为0和下标为gap(len/2)的两个元素就是一个子序列),再进行插入排序,然后以len/2/2为间隔一直到gap=1重复上述动作

void shellSort()
{

   int arr[] = {1, 5, 3, 9, 7};
   int len = 5;

   int gap, i, j;
   int temp;

   for (gap = len / 2; gap >= 1; gap /= 2) //第一个间隔为len/2,然后不断缩小
   {
      for (i = gap; i < len; i++) //对每一个下标大于gap的元素进行遍历(0-(gap-1)是每一个子序列的首个有序表)
      {
         temp = arr[i]; //将要插入的值赋值给temp,因为它所处的位置可能被覆盖
         for (j = i - gap; arr[j] > temp && j >= 0; j -= gap)
         {                         //i所处的子序列:i i-gap i-2gap i-n*gap( i-n*gap >= 0)
            arr[j + gap] = arr[j]; //arr[j]若大于要插入的值则将位置后移
         }
         arr[j + gap] = temp; //无论是arr[j]<temp还是j<0了,都将temp插入到arr[j]这一个子序列的后一个位置(j+gap)
      }
   }

   //打印数组
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}

5.归并排序

基本思想

对于两个有序数列,想象一下擂台赛,两边首先各出一名实力最弱的选手,胜者为王,继续在场上与对面派出来弱者下场排队,

B站参考视频:哔哩哔哩

动画

实现

//5.归并排序
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

6.快速排序

基本思想

1. 从数列中挑出一个元素，称为 “基准”（pivot）;

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

动画

实现

void quickSort()
{
   int arr[10] = {11, 7, 9, 3, 4, 6, 2, 8, 5, 3};
   quick_sort(arr, 0, 9);
   for (int i = 0; i < 10; i++)
      printf("%d\t", arr[i]);
}

int partition(int arr[], int start, int end)
{
   int temp = arr[start];
   int li = start, ri = end;
   while (li < ri)
   {
      while (li < ri && arr[ri] > temp)
         ri--;
      if (li < ri)
      {
         arr[li] = arr[ri];
         li++;
      }
      while (li < ri && arr[li] < temp)
         li++;
      if (li < ri)
      {
         arr[ri] = arr[li];
         ri--;
      }
   }
   arr[li] = temp;
   return li;
}

void quick_sort(int arr[], int start, int end)
{
   if (start < end)
   {
      int index = partition(arr, start, end);
      quick_sort(arr, start, index - 1);
      quick_sort(arr, index + 1, end);
   }
}

7.堆排序

基本思想

1. 创建一个堆 H[0……n-1]；

2. 把堆首（最大值）和堆尾互换；

3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

4. 重复步骤 2，直到堆的尺寸为 1。

   推荐资源:图解算法之堆排序
   B站视频`

动画

实现

//7.堆排序
void heapSort()
{
   int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
   int len = (int)sizeof(arr) / sizeof(*arr);
   for (int i = len; i > 1; i--)
      heap_Sort(arr, i); //建立堆 每次规模-1

   for (int i = 0; i < len; i++)
      printf("%d ", arr[i]);
   return 0;
}

//构造一个大顶堆并将最大值换至最后一位
void heap_Sort(int arr[], int len)
{
   int dad = len / 2 - 1; //最后一个父节点
   int son = 2 * dad + 1; //该父节点下的首个子节点
   while (dad >= 0)
   {
      //判断是否有两个子节点若有则在其中寻找最大子节点
      if (son + 1 <= len - 1 && arr[son] < arr[son + 1])
         son++;
      if (arr[dad] < arr[son]) //若父节点小于子节点则交换位置
         swap(&arr[dad], &arr[son]);
      dad--;             //回退到上一个父节点
      son = 2 * dad + 1; //上一个父节点的首个子节点
   }
   swap(&arr[0], &arr[len - 1]);
}

void swap(int *a, int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp;
}

8.计数排序

基本思想

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

动画

实现

void countingSort()
{
   int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
   int len = (int)sizeof(arr) / sizeof(*arr);
   counting_Sort(arr, len);

   for (int i = 0; i < len; i++)
      printf("%d ", arr[i]);
}

void counting_Sort(int arr[], int LEN)
{
   //寻找最大最小值
   int max = arr[0], min = arr[0], i, j = 0;
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] < min)
         min = arr[i];
      if (arr[i] > max)
         max = arr[i];
   }

   //建立计数数组
   int new_len = max - min + 1;
   printf("%d\n", new_len);
   int conunting_arr[new_len];
   //计数
   for (i = 0; i < new_len; i++) //初始化
   {
      conunting_arr[i] = 0;
   }
   for (i = 0; i < LEN; i++)
   {
      conunting_arr[arr[i] - min]++;
   }

   //根据计数结果进行排序
   for (i = 0; i < new_len; i++)
   {
      int index = conunting_arr[i];
      while (index != 0)
      {
         arr[j] = i + min;
         index--;
         j++;
      }
   }
}

9.桶排序

基本思想

桶排序(Bucket sort)或所谓的箱排序，计数排序的升级版，工作的原理是将数组分到有限数量的桶子里。 每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

每个桶对应一个数据或者一个数据段(实际上当每个桶对应一个数据的时候其实就是前面的计数排序)

这里我们使每个桶对应一个数据段并且对桶中元素使用冒泡排序进行排序操作

动画

实现

void bucketSort()
{
   int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
   int len = (int)sizeof(arr) / sizeof(*arr);
   bucket_Sort(arr, len);

   for (int i = 0; i < len; i++)
      printf("%d ", arr[i]);
}

void bucket_sort(int arr[], int LEN)
{
   int bucket[5][6] = {0}, i, j, k, temp; //初始化桶,每个桶存放6个数据
   //寻找最大最小值
   int min = arr[0], max = arr[0];
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] < min)
         min = arr[i]; //0
      if (arr[i] > max)
         max = arr[i]; //9
   }
   //遍历数组,将元素放到对应桶中
   int index0 = 0, index1 = 0, index2 = 0, index3 = 0, index4 = 0;
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] < min + (max - min + 1) / 5 * 1 && index0 < 7)
      {
         bucket[0][index0] = arr[i];
         index0++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 2 && (index1 < 7 || index0 >= 7))
      {
         bucket[1][index1] = arr[i];
         index1++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 3 && (index2 < 7 || index1 >= 7))
      {
         bucket[2][index2] = arr[i];
         index2++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 4 && (index3 < 7 || index2 >= 7))
      {
         bucket[3][index3] = arr[i];
         index3++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 5 && (index4 < 7 || index3 >= 7))
      {
         bucket[4][index4] = arr[i];
         index4++;
      }
   }

   //在每个桶中使用冒泡排序
   for (i = 0; i < 5; i++)
   {
      for (int j = 0; j < 5; j++) //从小到大
      {                           // 外循环为排序趟数，len个数进行len-1趟
         for (int k = 0; k < 5 - i; k++)
         { // 内循环为每趟比较的次数，第i趟比较len-i次,因为第一次已经将最大的元素冒泡到最后一个位置了
            if (bucket[i][k] > bucket[i][k + 1])
            { //相邻元素比较,逆序则将交换位置
               temp = bucket[i][k];
               bucket[i][k] = bucket[i][k + 1];
               bucket[i][k + 1] = temp;
            }
         }
      }
   }

   //将桶中排序结果还原到原数组中
   for (i = 0; i < 5; i++)
   {
      for (j = 0; j < 6; j++)
      {
         arr[i * 6 + j] = bucket[i][j];
      }
   }
}

10.基数排序

基本思想

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

动画

实现

void radixSort()
{
   int arr[] = {31, 25, 33, 40, 78, 26, 1, 52, 88, 63, 22, 44, 69, 42, 17, 10, 11, 28, 19, 47};
   int LEN = (int)sizeof(arr) / sizeof(*arr);

   int LEVEL = 0; //最大数的位数
   //寻找最大值以确定位数
   int max = arr[0], i;
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] > max)
         max = arr[i];
   }
   for (i = max; i > 0; i /= 10)
   {
      LEVEL++;
   }
   // printf("%d",LEVEL);

   for (i = 0; i < LEVEL; i++)
   {
      radix_sort(arr, LEN, i);
      for (int i = 0; i < LEN; i++)
         printf("%d ", arr[i]);
      printf("\n");
   }

   for (int i = 0; i < LEN; i++)
      printf("%d ", arr[i]);

   return 0;
}

void radix_sort(int arr[], int LEN, int level)
{
   int bucket[10] = {0}, temp[LEN], i, j;

   int flag = pow(10, level); //用于确定当前比较的是什么位

   //获取个位并进行第一次基数排序
   //获取个位存储入桶
   for (i = 0; i < LEN; i++)
   {
      bucket[arr[i] / flag % 10]++;
   }
   bucket[0]--;
   for (i = 1; i < 10; i++)
   {
      bucket[i] += bucket[i - 1];
   }

   //根据桶结果将原数组进行第一次排序后复制到temp数组
   //注意这里必须要反向遍历
   for (i = LEN - 1; i >= 0; i--)
   {
      temp[bucket[arr[i] / flag % 10]] = arr[i];
      bucket[arr[i] / flag % 10]--;
   }

   //利用temp数组修改原数组
   for (i = 0; i < LEN; i++)
   {
      arr[i] = temp[i];
   }
}

都看到这里了，各位哥哥姐姐叔叔阿姨给小王点个赞 关个注 留个言吧，和小王一起成长吧，你们的关注是对我最大的支持。
有事没事进来看看吧 : 小王的博客目录索引

如果以上内容有任何不准确或遗漏之处，或者你有更好的意见，就在下面留个言让我知道吧-我会尽我所能来回答。