十大排序算法，基本思想+C语言源码

2023-03-30 09:58:24

1.冒泡排序

基本思想

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

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

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

实现

void bubbleSort()
{
   //C实现
   int arr[] = {5, 9, 3, 8, 6};
   int len = sizeof(arr)/sizeof(arr[]);  
   int temp;
   for (int i = ; i < len - 1; i++) //从小到大
   {                                 // 外循环为排序趟数，len个数进行len-1趟
      for (int j = ; 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 = ; i < len; i++)
      printf("%d\t", arr[i]);
}

2.选择排序

基本思想

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

实现

int arr[] = {100, 92, 5, 9, 3, 8, 23, 17, 50, 6};
  int len = sizeof(arr)/sizeof(arr[]);                 
  int index = ;                //待会用来存储未排序区小元素的位置索引
  for (int i = ; 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 = ; 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[]);  

   int i, j, key;
   for (i = 1; i < len; i++) //从1开始是因为默认个元素是小的有序表
   {
      key = arr[i];
      j = i - 1; //a[j]是有序表后一个元素
      while ((j >= ) && (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 = ; i < len; i++)
      printf("%d\t", arr[i]);
}

4.希尔排序

基本思想

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

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

具体实现方法:

把待排序列，分成多个间隔为gap的子序列，
然后对每个子序列进行插入排序
重复上述，每次间隔gap不同（并且越来越小），直到后一次选取间隔gap=1，完成排序。
我们一般是取数组长度的一半为个间隔，即次将整个数组以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[]);  //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 >= ; 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 = ; i < len; i++)
      printf("%d\t", arr[i]);
}

5.归并排序

基本思想

说实话我今天刚看的时候没太搞懂…

这篇博客写的蛮好的,可以参照https://www.cnblogs.com/chengxiao/p/6194356.html

动画

实现

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 = ; 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 = ; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

6.快速排序

基本思想

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

动画

实现

void quickSort()
{
   int arr[10] = {11, 7, 9, 3, 4, 6, 2, 8, 5, 3};
   quick_sort(arr, , 9);
   for (int i = ; 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。

动画

实现

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

   //打印结果
   for (int i = ; i < len; i++)
      printf("%d ", arr[i]);
   return ;
}

//构造一个大顶堆并将大值换至后一位
void heap_Sort(int arr[], int len)
{
   int dad = len / 2 - 1; //后一个父节点
   int son = 2 * dad + 1; //该父节点下的子节点
   while (dad >= )
   {
      //判断是否有两个子节点若有则在其中寻找大子节点
      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[], &arr[len - 1]);
}

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

8.计数排序

基本思想

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

动画

实现

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

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

void counting_Sort(int arr[], int LEN)
{
   //寻找大小值
   int max = arr[], min = arr[], i, j = ;
   for (i = ; 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 = ; i < new_len; i++) //初始化
      conunting_arr[i] = ;
   
   for (i = ; i < LEN; i++)    //计数
      conunting_arr[arr[i] - min]++;

   //根据计数结果进行排序
   for (i = ; i < new_len; i++)
   {
      int index = conunting_arr[i];
      while (index != )
      {
         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, , 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, , 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, , 2, 6};
   int len = (int)sizeof(arr) / sizeof(arr[]);//30
   bucket_Sort(arr, len);

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

void bucket_sort(int arr[], int LEN)
{
   int bucket[5][6] = {}, i, j, k, temp; //初始化桶,每个桶存放6个数据
   //寻找大小值
   int min = arr[], max = arr[];
   for (i = ; i < LEN; i++)
   {
      if (arr[i] < min)
         min = arr[i]; 
      if (arr[i] > max)
         max = arr[i]; 
   }
   //遍历数组,将元素放到对应桶中
   int index0 = , index1 = , index2 = , index3 = , index4 = ;
   for (i = ; i < LEN; i++)
   {
      if (arr[i] < min + (max - min + 1) / 5 * 1 && index0 < 7)
      {
         bucket[][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 = ; i < 5; i++)
   {
      for (int j = ; j < 5; j++) //从小到大
      {                           // 外循环为排序趟数，len个数进行len-1趟
         for (int k = ; 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 = ; i < 5; i++)
   {
      for (j = ; 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[], exp = 1, BASE = 10, i;

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

    while (m / exp > )
    {
        int bucket[BASE] = {};
        //按照exp所在的位将所有元素放入桶中
        for (i = ; 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 >= ; i--)
            b[--bucket[(a[i] / exp) % BASE]] = a[i];
        //复制回原数组
        for (i = ; 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[]);

    radixsort(&arr[], len);

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

    return ;
}