姓名: 点赞姐
赛道: 普及组
类型: 算法技能
关键词: 排序
1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，比较相邻的元素并交换它们的位置，如果它们的顺序错误的话。这个过程被重复地进行，直到没有更多的交换需要进行，也就是数列已经排序好了。
冒泡排序的具体步骤:
- 从序列的开头开始，比较相邻的两个元素。
- 如果前面的元素大于后面的元素，则交换它们。
- 对每对相邻元素进行比较和交换操作，直到最后一个元素。
- 重复以上步骤，直到没有元素需要交换为止。
- 最坏情况：O(n²)
- 平均情况：O(n²)
- 最好情况：O(n)（当数组已经有序时，并且需要增加判断）
伪代码:
cpp
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2. 插入排序（Insertion Sort）
插入排序是一种简单的排序算法，通过构建一个有序的序列来将每个元素插入到正确的位置。
插入排序的具体步骤:
- 从第二个元素开始，认为第一个元素已经排序。
- 取当前元素，并与已排序的部分进行比较，将当前元素插入到合适的位置。
- 移动元素以为当前元素腾出位置。
- 重复步骤 2 和 3 直到所有元素都被插入到正确的位置。
- 最坏情况：O(n²)
- 平均情况：O(n²)
- 最好情况：O(n)（当数组已经有序时）
伪代码:
cpp
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
3. 选择排序（Selection Sort）
选择排序是一种简单的排序算法，主要通过在每一轮中选择最小（或最大）元素并放到已经排序的序列的末尾。
选择排序的具体步骤:
- 从未排序部分中选择最小的元素。
- 将其与未排序部分的第一个元素交换。
- 将排序部分扩大一位，未排序部分缩小一位。
- 重复步骤 1 至 3 直到所有元素都排序完成。
- 最坏情况：O(n²)
- 平均情况：O(n²)
- 最好情况：O(n²)
伪代码:
cpp
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换 arr[i] 和 arr[minIndex]
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
4. 快速排序（Quick Sort）
快速排序是一种高效的排序算法，通过选择一个“基准”元素，将数组分成两部分，然后递归地对这两部分进行排序。
快速排序的具体步骤:
- 选择一个基准元素。
- 重新排列数组，使得比基准小的元素在基准左边，比基准大的元素在基准右边。
- 递归地对基准左边和右边的子数组进行快速排序。
- 最坏情况：O(n²)（当数组已经是逆序时）
- 平均情况：O(n log n)
- 最好情况：O(n log n)
伪代码:
cpp
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i + 1] 和 arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
5. 归并排序（Merge Sort）
归并排序是一种有效的排序算法，采用分治法的思想，将数组分成两个子数组，分别排序后再合并。
归并排序的具体步骤:
- 将数组分成两个子数组。
- 递归地对两个子数组进行归并排序。
- 合并两个已排序的子数组。
伪代码:
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
- 最好情况：O(n log n)
cpp
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);
}
}
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
6. 堆排序（Heap Sort）
堆排序是一种基于堆数据结构的排序算法，它首先将数组构建成一个最大堆或最小堆，然后反复提取堆顶元素并调整堆。
堆排序的具体步骤:
- 将数组构建成一个最大堆。
- 交换堆顶元素与最后一个元素，然后调整堆。
- 重复步骤 2 直到堆的大小减少到 1。
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
- 最好情况：O(n log n)
伪代码:
cpp
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 temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
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);
}
}
7. 计数排序（Counting Sort）
计数排序是一种非比较的排序算法，适用于范围有限的整数排序。它通过计算每个元素出现的次数来确定元素的最终位置。
计数排序的具体步骤:
- 计算每个元素的出现次数。
- 对计数进行累加以确定每个元素的最终位置。
- 根据累加计数填充结果数组。
- 最坏情况：O(n + k)（其中 k 是数组中最大元素的值）
- 平均情况：O(n + k)
- 最好情况：O(n + k)
伪代码:
void countingSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];
int count[max + 1];
for (int i = 0; i <= max; i++) count[i] = 0;
for (int i = 0; i < n; i++)
count[arr[i]]++;
for (int i = 1; i <= max; i++)
count[i] += count[i - 1];
int output[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
8. 基数排序（Radix Sort）
基数排序是一种非比较的排序算法，它通过对各个位进行排序来排序整个数字。
基数排序的具体步骤:
从最低位开始，对每一位进行计数排序。
按从低位到高位的顺序重复步骤 1，直到所有位数都处理完毕。
- 最坏情况：O(nk)（其中 k 是数字的位数）
- 平均情况：O(nk)
- 最好情况：O(nk)
伪代码:
void countingSortForRadix(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];
for (int exp = 1; max / exp > 0; exp *= 10)
countingSortForRadix(arr, n, exp);
}
9. 希尔排序（Shell Sort）
希尔排序是插入排序的一种改进版，通过使数组部分有序来减少整体的排序时间。
伪代码:
cpp
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
- 最坏情况：O(n²)（取决于增量序列）
- 平均情况：O(n log n)（取决于增量序列）
- 最好情况：O(n log n)（取决于增量序列）