C语言数据结构算法,常用10种排序实战

本文涉及的产品
实时计算 Flink 版,5000CU*H 3个月
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
大数据开发治理平台 DataWorks,不限时长
简介: 插入排序(Insertion Sort)希尔排序(Shell Sort)选择排序(Selection Sort)冒泡排序(Bubble Sort)归并排序(Merge Sort)快速排序(Quick Sort)堆排序(Heap Sort)基数排序(Radix Sort)

QQ截图20240523161022.png


一:冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换的元素,也就是说该数列已经排序完成。

冒泡排序的步骤如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序的算法复杂度通常是 O(n^2),其中 n 是数列中元素的数量。这意味着当数列的长度增加时,排序所需的时间会成倍增加。

#include <stdio.h>

void bubbleSort(int arr[], int n)
{
  int i, j, temp;
  for (i = 0; i < n - 1; i++)
  {
    for (j = 0; j < n - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main()
{
  int arr[] = { 64, 34, 25, 12, 22, 11, 190 };
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

运行结果:

image.png


二:选择排序 (Selection Sort)

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

选择排序的步骤如下:

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。

选择排序算法的特点是:

  • 它不受输入数据的影响,无论什么数据,所需的排序时间都是相同的。
  • 它不是一种稳定的排序算法,因为相同元素的顺序可能会被改变。
  • 它的空间复杂度为 O(1),因为它只需要一个额外的存储空间来交换元素。
  • 它的平均时间复杂度和最坏时间复杂度都是 O(n^2),其中 n 是数列中元素的数量。
#include <stdio.h>

void selectionSort(int arr[], int n)
{
  int i, j, min_idx, temp;
  for (i = 0; i < n - 1; i++)
  {
    min_idx = i;
    for (j = i + 1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;

    temp = arr[min_idx];
    arr[min_idx] = arr[i];
    arr[i] = temp;
  }
}

int main()
{
  int arr[] = { 19, 52, 42, 2, 77, 31 };
  int n = sizeof(arr) / sizeof(arr[0]);
  selectionSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

运行结果:

image.png


三:插入排序 (Insertion Sort)

插入排序(Insertion Sort)是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place(即在原始数组上进行操作)排序,这意味着它不需要额外的存储空间。

插入排序的步骤如下:

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置。
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5。

插入排序是稳定的排序算法,因为它不会改变相同元素之间的顺序。

插入排序的时间复杂度:

  • 最好情况:当输入数组已经是有序的,时间复杂度是 O(n)。
  • 最坏情况:当输入数组是逆序的,时间复杂度是 O(n^2)。
  • 平均情况:时间复杂度是 O(n^2)。

插入排序的空间复杂度是 O(1),因为它只需要一个额外的存储空间。

#include <stdio.h>

void insertionSort(int arr[], int n)
{
  int i, key, j, temp;
  for (i = 1; i < n; i++)
  {
    key = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > key)
    {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

int main()
{
  int arr[] = { 38, 27, 43, 3, 9, 82 };
  int n = sizeof(arr) / sizeof(arr[0]);
  insertionSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

运行结果:

image.png


四:希尔排序 (Shell Sort)

希尔排序(Shell Sort)是插入排序的一种更高效的改进版本。它是由Donald Shell于1959年提出的。希尔排序通过将原始数据集分割成若干子序列,分别对这些子序列进行插入排序,然后再逐渐减少子序列的间隔,继续进行排序,直至整个数据集的间隔为1。

希尔排序的关键思想是将原始数据集分成多个子序列,每个子序列的元素之间存在一定的间隔。初始时,间隔可以是数据集大小的一半或者某个特定的序列(如希尔增量序列)。然后,对每个子序列进行插入排序。随着算法的进行,间隔逐渐减小,直到间隔为1,此时整个数据集作为一个子序列进行插入排序。

希尔排序的步骤如下:

  1. 选择一个增量序列,例如初始增量为 n/2,然后依次减半。
  2. 按照增量分组,对每组使用插入排序算法排序。
  3. 逐步减少增量,重复步骤2,直到增量减少到1,完成整个数据集的排序。

希尔排序的时间复杂度:

  • 最好情况:当增量序列选择得当时,时间复杂度可以达到 O(n log n)。
  • 平均情况:时间复杂度通常在 O(n (log n)^2) 到 O(n^(3/2)) 之间,具体取决于增量序列的选择。
  • 最坏情况:时间复杂度是 O(n^2)。

希尔排序的空间复杂度是 O(1),因为它是原地排序算法。

#include <stdio.h>

void shellSort(int arr[], int n)
{
  int i, j, gap, temp;
  gap = n / 2;
  while (gap > 0)
  {
    for (i = gap; i < n; i++)
    {
      temp = arr[i];
      j = i;
      while (j >= gap && arr[j - gap] > temp)
      {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = temp;
    }
    gap = gap / 2;
  }
}

int main()
{
  int arr[] = { 8, 3, 2, 7, 4, 6, 5 };
  int n = sizeof(arr) / sizeof(arr[0]);
  shellSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  return 0;
}

运行结果:

image.png


五:并归排序 (Merge Sort)

并归排序(Merge Sort)是一种分治算法,由约翰·冯·诺伊曼在1945年发明。它采用分治法(Divide and Conquer)的策略来把数据结构分为更小的子问题来解决,然后将子问题的解合并以解决原来的问题。

并归排序的基本思想是:

  1. 分解:将数组递归地分成两半,直到每个子数组只包含一个元素。
  2. 解决:由于每个子数组只有一个元素,它们自然就是有序的。
  3. 合并:将有序的子数组合并成更大的有序数组。

并归排序的步骤如下:

  1. 如果数组只有一个元素或者为空,它已经是有序的,直接返回。
  2. 将数组分成两个子数组,每个子数组包含原数组一半的元素。
  3. 对两个子数组分别进行归并排序。
  4. 将排序后的两个子数组合并成一个有序数组。

并归排序的时间复杂度:

  • 最好、最坏和平均情况的时间复杂度都是 O(n log n),其中 n 是数组中元素的数量。

并归排序的空间复杂度:

  • 由于需要额外的空间来存储子数组和合并后的数组,空间复杂度为 O(n)。
#include <stdio.h>
#include <stdlib.h>

// 合并两个有序子数组为一个有序数组
void merge(int arr[], int left, int mid, int right)
{
  int n1 = mid - left + 1;    // 左子数组的元素个数
  int n2 = right - mid;       // 右子数组的元素个数

  // 创建临时数组来存储两个子数组的元素
  int* leftArr = (int*)malloc(n1 * sizeof(int));
  int* rightArr = (int*)malloc(n2 * sizeof(int));

  // 将元素复制到临时数组中
  for (int i = 0; i < n1; i++)
  {
    leftArr[i] = arr[left + i];
  }
  for (int j = 0; j < n2; j++)
  {
    rightArr[j] = arr[mid + 1 + j];
  }

  // 合并两个子数组为一个有序数组
  int i = 0;      // 左子数组的索引
  int j = 0;      // 右子数组的索引
  int k = left;   // 合并后数组的索引

  while (i < n1 && j < n2)
  {
    if (leftArr[i] <= rightArr[j])
    {
      arr[k] = leftArr[i];
      i++;
    }
    else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }

  // 将剩余的元素放入合并后的数组中
  while (i < n1)
  {
    arr[k] = leftArr[i];
    i++;
    k++;
  }
  while (j < n2)
  {
    arr[k] = rightArr[j];
    j++;
    k++;
  }

  // 释放临时数组的内存
  free(leftArr);
  free(rightArr);
}

// 归并排序递归函数
void mergeSort(int arr[], int left, int right)
{
  if (left < right)
  {
    int mid = left + (right - left) / 2;    // 计算中间索引

    // 递归地对左右子数组进行排序
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // 合并两个有序子数组
    merge(arr, left, mid, right);
  }
}

// 案例用法
int main()
{
  int arr[] = { 51, 12, 18, 11, 31 ,4,76,45,90};
  int n = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, n - 1);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

运行结果:

image.png


六:快速排序 (Quick Sort)

快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它同样采用分治法(Divide and Conquer)的策略,但与归并排序不同,快速排序在平均和最好情况下的时间复杂度为 O(n log n),且它是一种原地排序算法,空间复杂度为 O(log n)。

快速排序的基本思想是:

  1. 选择基准:从数组中选择一个元素作为基准(pivot)。
  2. 分解:重新排列数组,所有比基准小的元素放在基准的左边,所有比基准大的元素放在基准的右边。
  3. 递归:递归地将上述两个子数组排序。

快速排序的步骤如下:

  1. 选择一个基准元素,可以是数组的第一个元素、最后一个元素、中间元素或随机元素。
  2. 将数组分为两部分,左边部分包含所有小于基准的元素,右边部分包含所有大于基准的元素。
  3. 对基准左边和右边的子数组递归地执行快速排序。
  4. 当子数组的大小减小到1或0时,递归结束。

快速排序的时间复杂度:

  • 最好和平均情况:O(n log n)
  • 最坏情况:O(n^2),当每次都选择到最大或最小元素作为基准时(例如,数组已经完全排序或逆序)。

快速排序的空间复杂度:

  • 平均情况下:O(log n),因为递归栈的深度是 log n。
  • 最坏情况下:O(n),当递归深度为 n 时。
#include <stdio.h>

int partition(int arr[], int low, int high)
{
  int pivot = arr[high];
  int i = (low - 1);
  for (int j = low; j <= high - 1; j++)
  {
    if (arr[j] < pivot)
    {
      i++;
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  int temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;

  return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
  if (low < high)
  {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

int main()
{
  int arr[] = { 102, 37, 86, 19, 1, 51 };
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

运行结果:

image.png


七:堆排序 (Heap Sort)

堆排序(Heap Sort)是一种基于比较的排序算法,它利用了二叉堆(Binary Heap)数据结构的特性来实现排序。堆排序可以被认为是一种改进的归并排序,因为它也分为分解和合并两个阶段,但它不需要额外的存储空间来创建子数组。

堆排序的基本思想是:

  1. 构建最大堆:将待排序的数组转换成最大堆,即父节点的值总是大于或等于其子节点的值。
  2. 交换和调整:将堆顶元素(最大值)与最后一个元素交换,缩小堆的范围,然后调整堆,以保持最大堆的性质。
  3. 重复:重复步骤2,直到堆的大小减少到1。

堆排序的步骤如下:

  1. 将无序序列构建成一个最大堆。
  2. 将堆顶元素(最大值)与最后一个元素交换,缩小堆的范围,剩余元素重新调整为最大堆。
  3. 重复步骤2,直到堆的大小为1。

堆排序的时间复杂度:

  • 最好、最坏和平均情况的时间复杂度都是 O(n log n)。

堆排序的空间复杂度:

  • 由于是原地排序,空间复杂度为 O(1)。
#include <stdio.h>

void heapify(int arr[], int n, int i)
{
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;

  if (l < n && arr[l] > arr[largest])
    largest = l;

  if (r < n && arr[r] > arr[largest])
    largest = r;

  if (largest != i)
  {
    int swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;

    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n)
{
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  for (int i = n - 1; i > 0; i--)
  {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;

    heapify(arr, i, 0);
  }

}

int main()
{
  int arr[] = { 12, 11, 13, 5, 6, 7 };
  int n = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

运行结果:

image.png


八:计数排序 (Counting Sort)

计数排序(Counting Sort)是一种非比较型排序算法,它通过使用一个额外的数组(计数数组)来统计输入数组中每个元素出现的次数,然后根据这些计数来确定每个元素在输出数组中的位置。

计数排序的基本思想是:

  1. 统计计数:遍历输入数组,对于每个元素,增加计数数组中对应元素的计数。
  2. 计算累积计数:将计数数组中的每个计数转换为累积计数,累积计数表示每个元素及其之前所有元素的总数。
  3. 构建输出数组:从输入数组的最后一个元素开始,根据元素的值在计数数组中查找其累积计数,这将告诉我们该元素在输出数组中的位置。将元素放置在正确的位置,并将计数数组中相应元素的计数减少。

计数排序的步骤如下:

  1. 找到输入数组中的最大值和最小值,以确定计数数组的大小。
  2. 创建一个计数数组,长度为最大值与最小值之差加1,并初始化所有元素为0。
  3. 遍历输入数组,对于每个元素,增加计数数组中相应位置的计数。
  4. 将计数数组中的每个计数转换为累积计数。
  5. 创建输出数组,长度与输入数组相同。
  6. 从输入数组的最后一个元素开始,根据元素的值,在计数数组中找到其累积计数,这将告诉我们该元素在输出数组中的位置。将元素放置在正确的位置,并将计数数组中相应元素的计数减少。

计数排序的时间复杂度:

  • 最好、最坏和平均情况的时间复杂度都是 O(n + k),其中 n 是输入数组的大小,k 是整数的范围。

计数排序的空间复杂度:

  • 空间复杂度是 O(k),其中 k 是整数的范围。
#include <stdio.h>
#include <stdlib.h>

void countingSort(int arr[], int n)
{
  // 找到最大值和最小值
  int max = arr[0], min = arr[0];
  for (int i = 1; i < n; ++i)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
    if (arr[i] < min)
    {
      min = arr[i];
    }
  }

  // 计算计数数组的长度
  int range = max - min + 1;

  // 创建并初始化计数数组
  int* count = (int*)malloc(range * sizeof(int));
  for (int i = 0; i < range; ++i)
  {
    count[i] = 0;
  }

  // 统计每个元素出现的次数
  for (int i = 0; i < n; ++i)
  {
    count[arr[i] - min]++;
  }

  // 还原排序后的数组
  int index = 0;
  for (int i = 0; i < range; ++i)
  {
    while (count[i] > 0)
    {
      arr[index++] = i + min;
      count[i]--;
    }
  }

  // 释放动态分配的内存
  free(count);
}

// 测试函数
int main()
{
  int arr[] = { 4, 2, 7, 1, 5, 2 };
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("Original array: ");
  for (int i = 0; i < n; ++i)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");

  countingSort(arr, n);

  printf("Sorted array: ");
  for (int i = 0; i < n; ++i)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

运行结果:

image.png


数据结构是计算机科学中存储、组织数据的方式,它不仅影响数据的存储效率,也影响对数据的操作效率。排序算法是数据结构中非常重要的一部分,用于将一系列元素按照特定的顺序重新排列。

1. 冒泡排序(Bubble Sort)

  - 基于重复遍历要排序的数列,比较每对相邻元素的大小,并在必要时交换它们的位置。

2. 选择排序(Selection Sort)

  - 通过重复地在未排序序列中找到最小(或最大)元素,并将其放置在排序序列的开头。

3. 插入排序(Insertion Sort)

  - 通过构建有序序列,对未排序数据从后向前扫描,找到相应位置并插入。

4. 希尔排序(Shell Sort)

  - 是插入排序的一种更高效的改进版本,通过将原始数据集分割成若干子序列,分别对这些子序列进行插入排序。

5. 归并排序(Merge Sort)

  - 使用分治法的一个非常高效的排序算法,将已排序的子序列合并为有序序列。

6. 快速排序(Quick Sort)

  - 通过选取一个“基准”元素,并将数列分为两部分,一部分包含所有小于基准的元素,另一部分包含所有大于基准的元素。

7. 堆排序(Heap Sort)

  - 利用堆这种数据结构所设计的一种排序算法,通过构建最大堆或最小堆来实现排序。

8. 计数排序(Counting Sort)

  - 非基于比较的排序算法,适用于一定范围内的整数排序,通过统计每个数字出现的次数来排序。

这些排序算法可以根据不同的标准进行分类:

- 按时间复杂度分类:

 - 平方级复杂度:冒泡排序、选择排序、插入排序、希尔排序(最坏情况)。

 - 线性对数级复杂度:归并排序、快速排序、堆排序。

 - 线性级复杂度:计数排序(当数据范围不大时)。

- 按空间复杂度分类:

 - 原地排序(空间复杂度为 O(1)):冒泡排序、选择排序、插入排序、希尔排序、快速排序。

 - 非原地排序(需要额外空间):归并排序(需要 O(n) 的额外空间)、计数排序(需要 O(k) 的额外空间,k 是数据范围)。

- 按稳定性分类:

 - 稳定的排序算法:冒泡排序、插入排序、希尔排序、归并排序。

 - 不稳定的排序算法:选择排序、快速排序、堆排序、计数排序。

- 按是否基于比较分类:

 - 基于比较的排序算法:冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序。

 - 非基于比较的排序算法:计数排序(当数据范围已知时)、桶排序、基数排序。

每种排序算法都有其适用场景和优缺点,选择合适的排序算法需要根据实际问题的特点来决定。

相关文章
|
7天前
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
13 3
|
2天前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
2天前
|
存储 算法
【二叉树】数据结构——BST二叉树基本概念及算法设计(插入、删除、遍历操作)
【二叉树】数据结构——BST二叉树基本概念及算法设计(插入、删除、遍历操作)
TU^
|
4天前
|
搜索推荐 算法 测试技术
数据结构~~排序
数据结构~~排序
TU^
7 1
|
4天前
|
搜索推荐 算法 测试技术
数据结构——排序
数据结构——排序
8 1
|
5天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
12天前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
16 0
|
12天前
|
存储 算法 NoSQL
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
14 1
|
8月前
|
存储 缓存 C语言
数据结构——双链表(C语言)
数据结构——双链表(C语言)
|
13天前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
10 2