此处我们介绍一下一些常用的排序模版：
- 冒泡排序
- 插入排序
- 选择排序
- 快速排序
- 堆排序
1 冒泡排序
冒泡排序的两个循环的作用：- 外循环：保证能有n次循环就行；i (0, n-1)
- 内循环：j和j+1进行比较；j (0, n-1-i)
void bubble_sort(vector &nums) {
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size() - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
} 2 插入排序
插入排序的两个循环的作用：- 外循环：定位准备插入的元素位置；i (1, size()]
- 内循环：将准备插入的元素与该元素前位置的元素进行比较；j (0, i)
void insert_sort(vector &nums) {
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] < nums[j]) {
swap(nums[i], nums[j]);
}
}
}
} 3 选择排序
选择排序两个循环的作用：- 外循环：需要选择的最小或者最大元素的位置； i (0, size()-1]
- 内循环：找到最小或者最大元素；j (i+1, size()-1]
void select_sort(vector &nums) {
for (int i = 0; i < nums.size(); i++) {
int min_index = i;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[min_index] > nums[j])
min_index = j;
}
swap(nums[i], nums[min_index]);
}
} 4 快速排序
快速排序的原理是先选择最右边的元素为锚点，然后从左往右将小于锚点的元素放在左边，大于锚点的元素放在右边。 一次分区操作使用快慢指针来实现：- 慢指针：指向大于锚点的元素
- 快指针：指向小于锚点的元素
- 当快指针找到小于锚点的元素时，交换快慢指针的值，同时快慢指针的位置同时+1
- 分区操作
- 左孩子分区操作
- 右孩子分区操作
int partition(vector &nums, int start, int end) {
int slow = 0, fast = 0;
int povit = nums[end - 1];
while (fast < end) {
if (nums[fast] < povit) {
swap(nums[fast], nums[slow]);
slow++;
}
fast++;
}
swap(nums[slow], nums[end - 1]);
return slow;
}
void quick_sort(vector &nums, int start, int end) {
if (start >= end)
return;
int middle = partition(nums, start, end);
quick_sort(nums, start, middle);
quick_sort(nums, middle + 1, end);
} 5 堆排序
堆排序需要考虑的是两个过程：- 1下滤：递归的将子树中最大值交换到根节点（O(logn)）
- 2 建堆：在数组的基础上建立大根堆（细节：从下往上建堆，O(nlogn)）
- 2 交换：每次将堆的根节点与尾结点交换，再执行下滤操作时不考虑尾结点。
// 1 下滤
void heapify(vector &nums, int size, int root) {
int largest = root;
int lson = 2 * root + 1;
int rson = 2 * root + 2;
if (lson < size && nums[lson] > nums[largest])
largest = lson;
if (rson < size && nums[rson] > nums[largest])
largest = rson;
if (largest != root) {
swap(nums[largest], nums[root]);
heapify(nums, size, largest);
}
}
void heap_sort(vector &nums) {
// 2 建堆
for (int i = (nums.size() / 2) - 1; i >= 0; i--) {
heapify(nums, nums.size(), i);
}
// 3 交换
for (int i = nums.size() - 1; i >= 0; i--) {
swap(nums[i], nums[0]);
heapify(nums, i, 0);
}
}
全部代码：
void bubble_sort(vector &nums) {
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size() - 1 - i; j++) { if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
}
void insert_sort(vector &nums) {
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] < nums[j]) {
swap(nums[i], nums[j]);
}
}
}
}
void select_sort(vector &nums) {
for (int i = 0; i < nums.size(); i++) {
int min_index = i;
for (int j = i + 1; j < nums.size(); j++) { if (nums[min_index] > nums[j])
min_index = j;
}
swap(nums[i], nums[min_index]);
}
}
int partition(vector &nums, int start, int end) {
int slow = 0, fast = 0;
int povit = nums[end - 1];
while (fast < end) {
if (nums[fast] < povit) {
swap(nums[fast], nums[slow]);
slow++;
}
fast++;
}
swap(nums[slow], nums[end - 1]);
return slow;
}
void quick_sort(vector &nums, int start, int end) {
if (start >= end)
return;
int middle = partition(nums, start, end);
quick_sort(nums, start, middle);
quick_sort(nums, middle + 1, end);
}
// 1 下滤
void heapify(vector &nums, int size, int root) {
int largest = root;
int lson = 2 * root + 1;
int rson = 2 * root + 2;
if (lson < size && nums[lson] > nums[largest])
largest = lson;
if (rson < size && nums[rson] > nums[largest])
largest = rson;
if (largest != root) {
swap(nums[largest], nums[root]);
heapify(nums, size, largest);
}
}
void heap_sort(vector &nums) {
// 2 建堆
for (int i = (nums.size() / 2) - 1; i >= 0; i--) {
heapify(nums, nums.size(), i);
}
// 3 交换
for (int i = nums.size() - 1; i >= 0; i--) {
swap(nums[i], nums[0]);
heapify(nums, i, 0);
}
}
int main() {
vector nums = {12, 43, 21, 47, 87, 9, 13, 40};
// bubble_sort(nums);
// insert_sort(nums);
// select_sort(nums);
// quick_sort(nums, 0, nums.size());
heap_sort(nums);
for (auto num : nums) {
cout << num << "\t";
}
cout << endl;
return 0;
}