一、简介
排序算法是计算机科学中的基本算法之一，用于将一组数据按照特定的顺序（升序或降序）进行排列。排序算法广泛应用于数据管理和检索系统，提高数据访问效率，也是其他高级算法的基础，如搜索和合并算法。
二、解题思路
排序算法的解题思路通常包括比较和交换元素位置。根据比较和移动元素的方式，排序算法可以分为多种类型，如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。
三、模板
- 冒泡排序（Bubble sort）
void bubble_sort(vector<int> &nums, int n) {
bool swapped;
for (int i = 1; i < n; ++i) {
swapped = false;
for (int j = 1; j < n- i + 1; ++j) {
if (nums[j] < nums[j-1]) {
swap(nums[j], nums[j-1]);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
- 选择排序（Selection sort）
void selection_sort(vector<int> &nums, int n) {
int mid;
for (int i = 0; i < n- 1; ++i) {
mid = i;
for (int j = i + 1; j < n; ++j) {
if (nums[j] < nums[mid]) {
mid = j;
}
}
swap(nums[mid], nums[i]);
}
}
- 插入排序（Insertion sort）
void insertion_sort(vector<int> &nums, int n) {
for (int i = 0; i < n; ++i) {
for (int j = i; j > 0 && nums[j] < nums[j-1];--j) {
swap(nums[j], nums[j-1]);
}
}
}
- 快速排序（Quicksort）
void quick_sort(vector<int> &nums, int l, int r) {
if (l + 1 >= r) {
return;
}
int first = l, last = r- 1, key = nums[first];
while (first < last){
while(first < last && nums[last] >= key) {--last;}
nums[first] = nums[last];
while (first < last && nums[first] <= key) {
++first;
}
nums[last] = nums[first];
}
nums[first] = key;
quick_sort(nums, l, first);
quick_sort(nums, first + 1, r);
}
- 归并排序（Merge sort）
void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp) {
if (l + 1 >= r) {return;}
// divide
int m = l + (r- l) / 2;
merge_sort(nums, l, m, temp);
merge_sort(nums, m, r, temp);
// conquer
int p = l, q = m, i = l;
while (p < m || q < r) {
if (q >= r || (p < m && nums[p] <= nums[q])) {
temp[i++] = nums[p++];
} else {
temp[i++] = nums[q++];
}
}
for (i = l; i < r; ++i) {
nums[i] = temp[i];
}
}
四、参考
LeetCode 101 - A LeetCode Grinding Guide (C++ Version)
