C++排序算法
4、快速排序是一种分治策略的排序算法,其核心思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。2、选择排序是一种简单的排序算法,它的基本思想是每次从未排序的序列中选择最小(或最大)的元素,放到已排序的序列的末尾。3、插入排序是一种简单的排序算法
1、冒泡排序是一种简单的排序算法,它的基本思想是通过重复地交换相邻的元素来排序。下面是一个使用C++实现冒泡排序的示例代码:
#include <iostream> // 数组的长度 const int LENGTH = 5; // 冒泡排序函数,将数组arr升序排序 void bubbleSort(int arr[]) { // 外层循环控制排序轮数 for (int i = 0; i < LENGTH - 1; i++) { // 内层循环控制每轮排序中的比较次数 for (int j = 0; j < LENGTH - i - 1; j++) { // 如果前一个数大于后一个数,交换两个数的位置 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int arr[] = { 3, 1, 4, 2, 5 }; // 调用冒泡排序函数对数组进行排序 bubbleSort(arr); // 输出排序后的数组 for (int i = 0; i < LENGTH; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }
输出结果如下:
输出结果
2、选择排序是一种简单的排序算法,它的基本思想是每次从未排序的序列中选择最小(或最大)的元素,放到已排序的序列的末尾。下面是一个使用C++实现选择排序的示例代码:
#include <iostream> // 数组的长度 const int LENGTH = 5; // 选择排序函数,将数组arr升序排序 void selectionSort(int arr[]) { // 外层循环控制排序轮数 for (int i = 0; i < LENGTH - 1; i++) { // 内层循环查找未排序部分的最小值 int minIndex = i; for (int j = i + 1; j < LENGTH; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 将最小值与第i个元素交换位置 int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } int main() { int arr[] = { 9, 6, 22, 1, 5 }; // 调用选择排序函数对数组进行排序 selectionSort(arr); // 输出排序后的数组 for (int i = 0; i < LENGTH; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }
输出结果如下:
输出结果
3、插入排序是一种简单的排序算法,它的基本思想是将待排序的元素逐个与已排序的序列进行比较,找到合适的位置并插入。下面是一个使用C++实现插入排序的示例代码:
#include <iostream> // 数组的长度 const int LENGTH = 6; // 插入排序函数,将数组arr升序排序 void insertionSort(int arr[]) { // 外层循环控制排序轮数 for (int i = 1; i < LENGTH; i++) { // // 内层循环查找插入位置 int temp = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } // 插入到合适的位置 arr[j + 1] = temp; } } int main() { int arr[] = { 3, 0, 4, -9, 5, 9 }; // 调用插入排序函数对数组进行排序 insertionSort(arr); // 输出排序后的数组 for (int i = 0; i < LENGTH; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }
输出结果如下:
输出结果
4、快速排序是一种分治策略的排序算法,其核心思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。下面是一个使用C++实现快速排序的示例代码:
#include <iostream> #include <algorithm> using namespace std; // 快速排序的递归函数 void quickSort(int arr[], int left, int right) { // 如果左边界大于右边界,则退出递归 if (left >= right) { return; } // 设置左边界和右边界 int i = left; int j = right; // 设置基准值为数组的第一个元素 int pivot = arr[left]; // 循环条件为左边界小于右边界 while (i < j) { // 从右边界开始查找小于基准值的元素 while (i < j && arr[j] >= pivot) { j--; } // 将小于基准值的元素移动到左边界的位置 arr[i] = arr[j]; // 从左边界开始查找大于基准值的元素 while (i < j && arr[i] <= pivot) { i++; } // 将大于基准值的元素移动到右边界的位置 arr[j] = arr[i]; } // 将基准值放到中间位置 arr[i] = pivot; // 对基准值左边的数组进行快速排序 quickSort(arr, left, i - 1); // 对基准值右边的数组进行快速排序 quickSort(arr, i + 1, right); } int main() { // 定义一个数组 int arr[] = { 3, 5, 1, 2, 4, 9, 6, 12 }; // 获取数组的长度 int n = sizeof(arr) / sizeof(arr[0]); // 快速排序 quickSort(arr, 0, n - 1); // 输出排序后的数组 cout << "排序后的数组: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; return 0; }
输出结果如下:
输出结果
5、此外,C++还提供了一些高级的排序函数,例如std::sort和std::stable_sort,它们可以对数组或容器中的元素进行排序。这些函数使用了更快的排序算法,并且可以使用自定义的比较函数来定义排序的顺序。
下面是一个使用std::sort函数对数组进行升序排序的示例代码:
#include <algorithm> #include <iostream> int main() { int arr[] = { 2, 7, 3, 2, 5 }; // 对数组进行升序排序 std::sort(arr, arr + 5); // 输出排序后的数组 for (int i = 0; i < 5; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }
输出结果如下:
输出结果
需要注意的是,C++的标准库中的排序函数均为模板函数,因此可以用于各种类型的数据。但是,如果要对自定义类型的数据进行排序,则需要自定义比较函数,并传递给排序函数。例如,下面是一个使用自定义比较函数对自定义类型进行排序的示例代码:
#include <algorithm> #include <iostream> #include <string> struct Person { std::string name; int age; }; // 自定义比较函数,按照年龄从小到大排序 bool compare(const Person& a, const Person& b) { return a.age < b.age; } int main() { Person arr[] = { {"Alice", 20}, {"Bob", 25}, {"Charlie", 15} }; // 使用自定义比较函数对数组进行排序 std::sort(arr, arr + 3, compare); // 输出排序后的数组 for (int i = 0; i < 3; i++) { std::cout << arr[i].name << " " << arr[i].age << std::endl; } return 0; }
输出结果如下:
输出结果
以上是C++中几种常见的排序算法,它们各有优缺点,在实际应用中可选择排序算法时,应考虑输入数据的规模以及排序所需的时间和空间。
如果输入数据较大,则可以使用时间复杂度较低的排序算法,例如归并排序或快速排序。如果输入数据较小,则可以使用时间复杂度较高但空间复杂度较低的排序算法,例如冒泡排序或选择排序。
总之,选择合适的排序算法可以帮助我们更有效地对数据进行排序,为后续的数据处理和分析提供便利。

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。
更多推荐
所有评论(0)