C++编程：数值排序算法详解——插入排序与快速排序

“C++数值的排序（二）.ppt 是一份适合C++初学者学习的教程，主要介绍了插入排序和快速排序两种常见的数值排序方法。” 本文档详细讲解了C++中对数值进行排序的两种常见算法：插入排序和快速排序。 1. 插入排序： 插入排序是一种简单直观的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。以下是一个简单的插入排序C++实现： ```cpp // exam6.14-3 #include<iostream> const int maxn = 100001; using namespace std; int main() { float a[maxn], temp; int n, i, j, k; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; for (i = 0; i < n; i++) { for (j = i - 1; j >= 0; j--) if (a[j] < a[i]) break; if (j != i - 1) { temp = a[i]; for (k = i - 1; k > j; k--) a[k + 1] = a[k]; a[k + 1] = temp; } } for (i = 0; i < n; i++) cout << a[i] << ""; return 0; } ``` 2. 快速排序： 快速排序是一种高效的排序算法，由英国计算机科学家Tony Hoare在1960年提出。它采用分治法，选择一个基准元素，将数组分为两部分，一部分的所有元素都比基准小，另一部分的所有元素都比基准大，然后对这两部分再分别进行快速排序。以下是快速排序的C++实现： ```cpp // 使用qsort函数进行快速排序 #include<iostream> #include<cstdlib> using namespace std; int kp(const void* a, const void* b) { return *(float*)a - *(float*)b; } int main() { int n, m, i, low, mid, high; int num[101]; cin >> n; for (i = 0; i < n; i++) cin >> num[i]; qsort(num, n, sizeof(num[0]), kp); for (i = 0; i < n; i++) cout << num[i] << " "; return 0; } ``` 快速排序的核心在于“分”和“治”，通过选取基准元素并分区，将大问题不断分解为小问题，最后再合并解决。这里的`kp`函数是一个比较函数，用于比较两个浮点数的大小。 总结： C++中的排序算法是编程基础的重要组成部分，无论是插入排序还是快速排序，都有其独特的应用场景。插入排序适合于小规模或近似有序的数据，而快速排序则在大多数情况下都能提供较高的效率。学习和理解这些排序算法不仅有助于提升编程能力，也是为理解和应用更复杂的算法打下基础。