【25届秋招备战C++】算法篇-排序算法合集

一、简介

排序算法是计算机科学中的基本算法之一，用于将一组数据按照特定的顺序（升序或降序）进行排列。排序算法广泛应用于数据管理和检索系统，提高数据访问效率，也是其他高级算法的基础，如搜索和合并算法。

二、解题思路

排序算法的解题思路通常包括比较和交换元素位置。根据比较和移动元素的方式，排序算法可以分为多种类型，如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。

三、模板

• 冒泡排序（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)