PS:页面右边有该文章的目录，可快捷跳转到对应位置 目前该篇只介绍了三种排序算法:冒泡排序、插入排序、快速排序(极度推荐)。以及C++ STL里快排函数sort()的使用。 #### 1.冒泡排序 ##### 1.1 算法介绍 - 时间复杂度(平均) O(n²) - 时间复杂度(最好) O(n) - 时间复杂度(最坏) O(n²) - 空间复杂度 O(1) 这应该是世界上知名度最广的一个排序算法了吧(也是时间复杂度最高的算法) ::twemoji:tilted:: ##### 1.2 代码实现 void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 1; j < n - i; ++j) { if (arr[j-1] > arr[j]) swap(arr[j-1], arr[j]); } } } ##### 1.3 GIF原理图 ![冒泡排序原理][1] #### 2.插入排序 ##### 2.1 算法介绍 - 时间复杂度(平均) O(n²) - 时间复杂度(最好) O(n) - 时间复杂度(最坏) O(n²) - 空间复杂度 O(1) ##### 2.2 代码实现 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; } } ##### 2.3 GIF原理图 ![插入排序原理][2] #### 3.快速排序 ##### 3.1 算法介绍 - 时间复杂度(平均) O(nlogn) - 时间复杂度(最好) O(nlogn) - 时间复杂度(最坏) O(n²) - 空间复杂度 O(nlogn) 快速排序采用了分治策略,通过一个pivot(基准值)将数组分成两部分,一部分小于pivot,一部分大于pivot。然后递归对两部分继续排序,直到数组有序。 **复杂度分析: ** 最坏情况下,每次pivot都位于边界,会导致递归树退化为链表,时间复杂度为O(n^2) 平均情况下,递归树深度为O(logn),每层partition时间为O(n),所以平均时间复杂度为O(nlogn) ##### 3.2 代码实现 int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; ++j) { if (arr[j] < pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[right]); return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } } ##### 3.3 GIF原理图 没找到合适的动图，排序过程请看算法介绍 #### 4. C++ STL里的排序 C++ 标准库里实现了排序的函数std::sort(),印象中其效率是和快排差不多的,该函数定义于头文件 **`<algorithm>`** 传入参数: |参数|说明| |----|----| |first,last|要搜索部分范围的迭代器| |comp|比较函数| ##### 4.1 对数组进行升序排序 sort默认排序顺序是升序 #include <iostream> #include <algorithm> using namespace std; int main() { int a[10] = {1,5,9,8,7,5,3,2,6,4}; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << ' '; // 1 2 3 4 5 5 6 7 8 9 return 0; } ##### 4.2 对数组进行降序排序 这时候就需要自定义比较函数 bool compare(int a, int b) { return a > b; } 然后再排序 sort(a, a+10, compare); ##### 4.3 对结构体数组进行排序 同理自定义排序函数可以让我们对结构体进行排序 bool compare(struct aaa A, struct aaa B) { if (A.a == B.a) return A.b > B.b; return A.a > B.a; } 然后再进行排序 sort(aaa, aaa+10, compare); #### 猫猫说 ![反卷猫猫][3] [1]: https://www.guwolf.com/files/algo-sort/bubble_sort.gif [2]: https://www.guwolf.com/files/algo-sort/insertionSort.gif [3]: https://www.guwolf.com/files/fanjuanmaomao.jpg Loading... PS:页面右边有该文章的目录，可快捷跳转到对应位置 目前该篇只介绍了三种排序算法:冒泡排序、插入排序、快速排序(极度推荐)。以及C++ STL里快排函数sort()的使用。 #### 1.冒泡排序 ##### 1.1 算法介绍 - 时间复杂度(平均) O(n²) - 时间复杂度(最好) O(n) - 时间复杂度(最坏) O(n²) - 空间复杂度 O(1) 这应该是世界上知名度最广的一个排序算法了吧(也是时间复杂度最高的算法) <img src="https://still-truth-8298.60385cc1.er.aliyun-esa.net/assets/img/emotion/twemoji/tilted.png" class="emotion-twemoji"> ##### 1.2 代码实现 void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 1; j < n - i; ++j) { if (arr[j-1] > arr[j]) swap(arr[j-1], arr[j]); } } } ##### 1.3 GIF原理图 ![冒泡排序原理][1] #### 2.插入排序 ##### 2.1 算法介绍 - 时间复杂度(平均) O(n²) - 时间复杂度(最好) O(n) - 时间复杂度(最坏) O(n²) - 空间复杂度 O(1) ##### 2.2 代码实现 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; } } ##### 2.3 GIF原理图 ![插入排序原理][2] #### 3.快速排序 ##### 3.1 算法介绍 - 时间复杂度(平均) O(nlogn) - 时间复杂度(最好) O(nlogn) - 时间复杂度(最坏) O(n²) - 空间复杂度 O(nlogn) 快速排序采用了分治策略,通过一个pivot(基准值)将数组分成两部分,一部分小于pivot,一部分大于pivot。然后递归对两部分继续排序,直到数组有序。 **复杂度分析: ** 最坏情况下,每次pivot都位于边界,会导致递归树退化为链表,时间复杂度为O(n^2) 平均情况下,递归树深度为O(logn),每层partition时间为O(n),所以平均时间复杂度为O(nlogn) ##### 3.2 代码实现 int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; ++j) { if (arr[j] < pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[right]); return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } } ##### 3.3 GIF原理图 没找到合适的动图，排序过程请看算法介绍 #### 4. C++ STL里的排序 C++ 标准库里实现了排序的函数std::sort(),印象中其效率是和快排差不多的,该函数定义于头文件 **`<algorithm>`** 传入参数: |参数|说明| |----|----| |first,last|要搜索部分范围的迭代器| |comp|比较函数| ##### 4.1 对数组进行升序排序 sort默认排序顺序是升序 #include <iostream> #include <algorithm> using namespace std; int main() { int a[10] = {1,5,9,8,7,5,3,2,6,4}; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << ' '; // 1 2 3 4 5 5 6 7 8 9 return 0; } ##### 4.2 对数组进行降序排序 这时候就需要自定义比较函数 bool compare(int a, int b) { return a > b; } 然后再排序 sort(a, a+10, compare); ##### 4.3 对结构体数组进行排序 同理自定义排序函数可以让我们对结构体进行排序 bool compare(struct aaa A, struct aaa B) { if (A.a == B.a) return A.b > B.b; return A.a > B.a; } 然后再进行排序 sort(aaa, aaa+10, compare); #### 猫猫说 ![反卷猫猫][3] [1]: https://www.guwolf.com/files/algo-sort/bubble_sort.gif [2]: https://www.guwolf.com/files/algo-sort/insertionSort.gif [3]: https://www.guwolf.com/files/fanjuanmaomao.jpg 最后修改：2024 年 01 月 06 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
