一:冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换的元素,也就是说该数列已经排序完成。
冒泡排序的步骤如下:
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
冒泡排序的算法复杂度通常是 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; }
运行结果:
二:选择排序 (Selection Sort)
选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
选择排序的步骤如下:
- 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
选择排序算法的特点是:
- 它不受输入数据的影响,无论什么数据,所需的排序时间都是相同的。
- 它不是一种稳定的排序算法,因为相同元素的顺序可能会被改变。
- 它的空间复杂度为 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; }
运行结果:
三:插入排序 (Insertion Sort)
插入排序(Insertion Sort)是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place(即在原始数组上进行操作)排序,这意味着它不需要额外的存储空间。
插入排序的步骤如下:
- 从第一个元素开始,该元素可以认为已经被排序。
- 取出下一个元素,在已经排序的元素序列中从后向前扫描。
- 如果该元素(已排序)大于新元素,将该元素移到下一位置。
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤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; }
运行结果:
四:希尔排序 (Shell Sort)
希尔排序(Shell Sort)是插入排序的一种更高效的改进版本。它是由Donald Shell于1959年提出的。希尔排序通过将原始数据集分割成若干子序列,分别对这些子序列进行插入排序,然后再逐渐减少子序列的间隔,继续进行排序,直至整个数据集的间隔为1。
希尔排序的关键思想是将原始数据集分成多个子序列,每个子序列的元素之间存在一定的间隔。初始时,间隔可以是数据集大小的一半或者某个特定的序列(如希尔增量序列)。然后,对每个子序列进行插入排序。随着算法的进行,间隔逐渐减小,直到间隔为1,此时整个数据集作为一个子序列进行插入排序。
希尔排序的步骤如下:
- 选择一个增量序列,例如初始增量为 n/2,然后依次减半。
- 按照增量分组,对每组使用插入排序算法排序。
- 逐步减少增量,重复步骤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; }
运行结果:
五:并归排序 (Merge Sort)
并归排序(Merge Sort)是一种分治算法,由约翰·冯·诺伊曼在1945年发明。它采用分治法(Divide and Conquer)的策略来把数据结构分为更小的子问题来解决,然后将子问题的解合并以解决原来的问题。
并归排序的基本思想是:
- 分解:将数组递归地分成两半,直到每个子数组只包含一个元素。
- 解决:由于每个子数组只有一个元素,它们自然就是有序的。
- 合并:将有序的子数组合并成更大的有序数组。
并归排序的步骤如下:
- 如果数组只有一个元素或者为空,它已经是有序的,直接返回。
- 将数组分成两个子数组,每个子数组包含原数组一半的元素。
- 对两个子数组分别进行归并排序。
- 将排序后的两个子数组合并成一个有序数组。
并归排序的时间复杂度:
- 最好、最坏和平均情况的时间复杂度都是 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; }
运行结果:
六:快速排序 (Quick Sort)
快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它同样采用分治法(Divide and Conquer)的策略,但与归并排序不同,快速排序在平均和最好情况下的时间复杂度为 O(n log n),且它是一种原地排序算法,空间复杂度为 O(log n)。
快速排序的基本思想是:
- 选择基准:从数组中选择一个元素作为基准(pivot)。
- 分解:重新排列数组,所有比基准小的元素放在基准的左边,所有比基准大的元素放在基准的右边。
- 递归:递归地将上述两个子数组排序。
快速排序的步骤如下:
- 选择一个基准元素,可以是数组的第一个元素、最后一个元素、中间元素或随机元素。
- 将数组分为两部分,左边部分包含所有小于基准的元素,右边部分包含所有大于基准的元素。
- 对基准左边和右边的子数组递归地执行快速排序。
- 当子数组的大小减小到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; }
运行结果:
七:堆排序 (Heap Sort)
堆排序(Heap Sort)是一种基于比较的排序算法,它利用了二叉堆(Binary Heap)数据结构的特性来实现排序。堆排序可以被认为是一种改进的归并排序,因为它也分为分解和合并两个阶段,但它不需要额外的存储空间来创建子数组。
堆排序的基本思想是:
- 构建最大堆:将待排序的数组转换成最大堆,即父节点的值总是大于或等于其子节点的值。
- 交换和调整:将堆顶元素(最大值)与最后一个元素交换,缩小堆的范围,然后调整堆,以保持最大堆的性质。
- 重复:重复步骤2,直到堆的大小减少到1。
堆排序的步骤如下:
- 将无序序列构建成一个最大堆。
- 将堆顶元素(最大值)与最后一个元素交换,缩小堆的范围,剩余元素重新调整为最大堆。
- 重复步骤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; }
运行结果:
八:计数排序 (Counting Sort)
计数排序(Counting Sort)是一种非比较型排序算法,它通过使用一个额外的数组(计数数组)来统计输入数组中每个元素出现的次数,然后根据这些计数来确定每个元素在输出数组中的位置。
计数排序的基本思想是:
- 统计计数:遍历输入数组,对于每个元素,增加计数数组中对应元素的计数。
- 计算累积计数:将计数数组中的每个计数转换为累积计数,累积计数表示每个元素及其之前所有元素的总数。
- 构建输出数组:从输入数组的最后一个元素开始,根据元素的值在计数数组中查找其累积计数,这将告诉我们该元素在输出数组中的位置。将元素放置在正确的位置,并将计数数组中相应元素的计数减少。
计数排序的步骤如下:
- 找到输入数组中的最大值和最小值,以确定计数数组的大小。
- 创建一个计数数组,长度为最大值与最小值之差加1,并初始化所有元素为0。
- 遍历输入数组,对于每个元素,增加计数数组中相应位置的计数。
- 将计数数组中的每个计数转换为累积计数。
- 创建输出数组,长度与输入数组相同。
- 从输入数组的最后一个元素开始,根据元素的值,在计数数组中找到其累积计数,这将告诉我们该元素在输出数组中的位置。将元素放置在正确的位置,并将计数数组中相应元素的计数减少。
计数排序的时间复杂度:
- 最好、最坏和平均情况的时间复杂度都是 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; }
运行结果:
数据结构是计算机科学中存储、组织数据的方式,它不仅影响数据的存储效率,也影响对数据的操作效率。排序算法是数据结构中非常重要的一部分,用于将一系列元素按照特定的顺序重新排列。
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 是数据范围)。
- 按稳定性分类:
- 稳定的排序算法:冒泡排序、插入排序、希尔排序、归并排序。
- 不稳定的排序算法:选择排序、快速排序、堆排序、计数排序。
- 按是否基于比较分类:
- 基于比较的排序算法:冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序。
- 非基于比较的排序算法:计数排序(当数据范围已知时)、桶排序、基数排序。
每种排序算法都有其适用场景和优缺点,选择合适的排序算法需要根据实际问题的特点来决定。