十大排序算法详解，基本思想+动画演示+C语言实现，太肝了！

下面的99%的代码都是手动敲出来的，参考了诸多资料，已经经过测试，可以放心食用。

1.冒泡排序

基本思想

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

在进行第一轮上面的从左到右的比较时，则会把一个最小或者最大的元素（取决于你想要的排列方式）"冒泡"到最右边的位置，第二轮则是冒泡第二大或第二小的数到最右边，因此我们总共只需要进行n-1轮即可，最后一个数的位置也被固定了（其余n-1个数都比他大且都在其右边）。

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

动画：

实现

//void bubbleSort(){
   //C实现
   int arr[] = {5, 9, 3, 8, 6};
   int len = sizeof(arr)/sizeof(arr[0]);
   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]);
}

小编推荐一个学C语言/C++的学习裙【  712,284,705】，无论你是小白还是进阶者，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！

2.选择排序

基本思想

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

动画：

实现

 //int arr[] = {100, 92, 5, 9, 3, 8, 23, 17, 50, 6};  int len = sizeof(arr)/sizeof(arr[0]);
  int index = 0;                //待会用来存储未排序区最小元素的位置索引
  for (int i = 0; i < len; i++) //从小到大
  {
    index = i;
    for (int j = i + 1; j < len; j++) //用i之后的每一个元素去与i元素比较大小,若小于arr[i]则更新最小元素索引
    {
      if (arr[j] < arr[index])
        index = j;
    }
    //将i与index的元素调换位置
    //注意:此处不可将调换位置的函数写进第二层for循环即for(int j=i+1)中,因为交换后i与min指向的对象会交换,此后循环就可能出现仅仅小于arr[i](此时已经换到了min位置)但不小于arr[min](这时在i位置上)的元素也与初始位置上进行交换的情况,具体情况可以试验!
    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 = sizeof(arr)/sizeof(arr[0]);  

   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)) //从后往前遍历并且判断arr[j]是否大于key
                                        //j>=0防止数组越界
      {
         arr[j + 1] = arr[j];//后移
         j--;//j前移
      }
      arr[j + 1] = key; //arr[j]是第一个比key小的元素,将key置于其后(比key大的有序表元素都已经后移一个位置了)
   }

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

4.希尔排序

基本思想

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

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

具体实现方法:

  1. 把待排序列，分成多个间隔为gap的子序列，
  2. 然后对每个子序列进行插入排序
  3. 重复上述，每次间隔gap不同（并且越来越小），直到最后一次选取间隔gap=1，完成排序。
  4. 我们一般是取数组长度的一半为第一个间隔，即第一次将整个数组以len/2为间隔分为2个子序列，再进行插入排序，然后以len/2/2为间隔一直到gap=1重复上述动作下图来自网络,便于理解

实现

//void shellSort(){

   int arr[] = {1,12,13,19,26,7,8,15,3,23,99,8,35,27,34,5};
   int len = sizeof(arr)/sizeof(arr[0]);  //16

   int gap, i, j;
   int temp;

   for (gap = len / 2; gap >= 1; gap /= 2) //第一个间隔为len/2,然后不断除2缩小
   {
      for (i = gap; i < len; i++) //对每一个下标大于gap的元素进行遍历
                                //arr[gap]是第一组最后一个元素
      {
         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.归并排序

动画

实现

//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;
            int mid = min(start + seg, len);
            int 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中
                b[k++] = a[start1++];
            while (start2 < end2)//将左边剩下的元素放置到数组b中
                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);
}

小编推荐一个学C语言/C++的学习裙【  712,284,705】，无论你是小白还是进阶者，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！

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];//以arr[start]作为基准,将被放置在数组中间
                        //同时将start位置作为交换元素的缓冲点-类比交换两个数的第三个数
   int li = start, ri = end;//li->left index 左索引 li==start 所以初始li是第一个缓冲点
   while (li < ri)
   {
      while (li < ri && arr[ri] > temp)//找到我们右起第一个小于基准值的元素索引ri
         ri--;
      if (li < ri)
      {
         arr[li] = arr[ri];//将右起第一个小于基准值的元素索引放置在缓冲点(li)
                        //同时此时的ri成为新的缓冲点
         li++;
      }
      while (li < ri && arr[li] < temp)//找到我们右起第一个小于基准值的元素索引li
         li++;
      if (li < ri)
      {
         arr[ri] = arr[li];//将左起第一个大于基准值的元素索引放置在缓冲点 (ri)
                        //同时此时的li成为新的缓冲点
         ri--;
      }
       //结束上述操作后li和ri分别是左右已排序部分(置于两端)的后面一个和前面一个元素(不包含在其中)
       //明显若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. 创建一个大顶堆( 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆 )；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，利用剩下的元素再次建立一个大顶堆；
  4. 重复步骤 2 3，直到堆的尺寸为 1。

动画

实现

////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;

   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.桶排序

最简单的桶排序

将数组{1,3,3,7,9,2,4,6,6,0}进行排序:

观察数组元素范围，看出来是从0到9（可以去遍历取得最大最小值），所以我们建立10个有序桶，将数字一个个塞入对应的桶中，然后根据桶的情况进行输出（桶中有几个元素就输出几个，没有就跳过）-实际上就是最简单的计数排序，但网上有人把这个也算作桶排序了，不要搞混，下面来看真正的桶排序吧。

基本思想

桶排序(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[0]);//30
   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];
      if (arr[i] > max)
         max = arr[i];
   }
   //遍历数组,将元素放到对应桶中
   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.基数排序

基本思想

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

动画

实现

#include <stdio.h>
//void radixsort(int *a, int n){
    int b[n], m = a[0], exp = 1, BASE = 10, i;

    //寻找最大值
    for (i = 1; i < n; i++)
        if (a[i] > m)
            m = a[i];

    while (m / exp > 0)
    {
        int bucket[BASE] = {0};
        //按照exp所在的位将所有元素放入桶中
        for (i = 0; i < n; i++)
            bucket[(a[i] / exp) % BASE]++;
        //做前缀和-以<=i结尾的数的个数-以i结尾的数的最大索引+1
        for (i = 1; i < BASE; i++)
            bucket[i] += bucket[i - 1];
        //依据前缀和将原数组中每一个元素放置在基于技术排列后的位置 并将前缀和减1
        for (i = n - 1; i >= 0; i--)
            b[--bucket[(a[i] / exp) % BASE]] = a[i];
        //复制回原数组
        for (i = 0; i < n; i++)
            a[i] = b[i];

        exp *= BASE;
    }
}

int main()
{
    int arr[10] = {1, 35, 98, 256, 789, 47, 4, 956, 64, 222};
    int len = sizeof(arr) / sizeof(arr[0]);

    radixsort(&arr[0], len);

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

    return 0;
}

来源：https://blog.csdn.net/weixin_45761327/article/details/105908057

赞 (0)

相关推荐

  • c语言必会排序算法集（含代码解析）

      一.冒泡排序 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小.首字母从A到Z)错误就 ...

  • 算法之十大滤波算法详解

    限幅滤波法 1.方法限幅滤波法又称嵌位滤波法,或程序判断滤波法.这种滤波法的思路是: 先根据经验判断,确定两次采样允许的最大偏差值(设为A)每次检测到新采样值时进行判断: (1)如果本次新采样值与上次 ...

  • 古代江苏的十大名门望族详解

    自从秦朝开始实行郡县制,江苏境内的长江以南属会稽郡,以北分属东海郡和泗水郡. 西汉初年,郡国并行,江苏省先后分属楚国.荆国.吴国.广陵国.泗水国.会稽郡.丹阳郡.东海郡.临淮郡.琅邪郡.沛郡等郡. 在 ...

  • 古代安徽的十大名门望族详解

    安徽在秦代实行郡县制时,境内长江以南属会稽郡.九江郡,以北分属泗水郡.砀郡.陈郡.秦末至楚汉相争期间,增置鄣郡.衡山郡.庐江郡,并为九江.西楚.衡山等诸侯国分领. 西汉时,安徽先后分属为淮南国.庐江国 ...

  • 古代江西的十大名门望族详解

    秦始皇一统天下,设三十六郡,江西属九江郡. 汉高帝初年,因赣江原称豫章江,在江西境内设豫章郡,郡治南昌县,这是江西第一次作为明确的行政区域建制. 唐太宗贞观元年,划全国为10道监察区,江西属于江南道. ...

  • 古代湖北的十大名门望族详解

    秦始皇一统天下,废除分封制,实行郡县制,设三十六郡,湖北大部属南郡. 西汉时期,湖北大部属荆州刺史部. 东汉时期,沿置南郡.南阳郡.江夏郡以及汉中郡.庐江郡等. 隋朝统一全国后,今湖北除西北部分和东部 ...

  • 古代湖南的十大名门望族详解

    秦始皇一统天下,废除分封制,实行郡县制,设三十六郡,湖南分属黔中郡.长沙郡. 西汉初期,湖南属于长沙国:汉武帝之后属荆州刺史部辖区,下辖武陵郡.桂阳郡.零陵郡和长沙郡. 东晋时,湖南分属荆州.湘州和江 ...

  • 古代广东的十大名门望族详解

    公元前214年,秦始皇发兵平定岭南,在广东地区设南海郡. 公元前111年,汉武帝平定南越国,将原赵佗割据地区划分为九郡,广东仍称南海郡,归交州管辖. 公元217年,吴国交州刺史步骘把交州州治从广信东迁 ...

  • 古代宁夏的十大名门望族详解

    秦始皇一统天下,废除分封制,实行郡县制,设三十六郡,宁夏属北地郡. 两汉时,宁夏分属北地郡和安定郡. 唐朝时,宁夏全境属关内道,设原州.灵州.西会州.安乐州.雄州和警州. 元朝时,忽必烈在宁夏设宁夏府 ...

  • 古代贵州的十大名门望族详解

    春秋以前,贵州为荆州西南夷,属于荆楚或南蛮的一部分. 战国时期,贵州大部分属于夜郎国. 三国时,贵州属蜀汉牂牁郡.朱提郡.兴古郡.江汉郡.涪陵郡. 唐朝时,贵州属播州.思州等管辖. 宋代,贵州主要属于 ...