C++经典排序算法实现

C++常用算法经典代码详解 本文将对C++中常用的排序算法进行详细的介绍和分析，包括快速排序、冒泡排序和桶排序 三种经典算法的实现代码和原理分析。 一、快速排序 快速排序是一种高效的排序算法，时间复杂度为O(n log n)，是基于分治策略的排序算法。其基本思想是选择一个pivot元素，将数组分成两个部分，小于pivot的元素和大于pivot的元素，然后递归地对两个部分进行排序。 快速排序的实现代码如下： ```c void qsort(int x, int y) { int h = x, r = y; int m = a[(x + y) >> 1]; // 取中间的那个位置的值 while (h < r) { while (a[h] < m) h++; // 比中间那个位置的值小，循环直到找一个比中间那个值大的 while (a[r] > m) r--; // 比中间那个位置的值大，循环直到找一个比中间那个值小的 if (h <= r) { int temp = a[h]; // 如果此时h<=r，交换a[h]和a[r] a[h] = a[r]; a[r] = temp; h++; r--; } } if (r > x) qsort(x, r); // 注意此处，尾指针跑到前半部分了 if (h < y) qsort(h, y); // 注意此处，头指针跑到后半部分了 } ``` 快速排序的时间复杂度为O(n log n)，是高效的排序算法，适用于大规模的数据排序。 二、冒泡排序 冒泡排序是一种简单的排序算法，时间复杂度为O(n^2)，是基于比较和交换的排序算法。其基本思想是通过不断地比较相邻的元素，并交换它们，以达到排序的目的。 冒泡排序的实现代码如下： ```c void paopao(void) { for (int i = 1; i < n; i++) { // 控制循环（冒泡）的次数，n个数，需要n-1次冒泡 for (int j = 1; j <= n - i; j++) { // 相邻的两两比较 if (a[j] < a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } ``` 冒泡排序的时间复杂度为O(n^2)，是低效的排序算法，适用于小规模的数据排序。 三、桶排序 桶排序是一种高效的排序算法，时间复杂度为O(n + k)，是基于计数的排序算法。其基本思想是将元素分配到不同的桶中，然后对每个桶进行排序。 桶排序的实现代码如下： ```c void bucketsort(void) { memset(tong, 0, sizeof(tong)); // 桶初始化 for (int i = 1; i <= n; i++) { // 读入n个数 int a; cin >> a; tong[a]++; // 相应的桶号计数器加1 } for (int i = 1; i <= cmax; i++) { if (tong[i] > 0) { // 当桶中装的树大于0，说明i出现过tong // ... } } } ``` 桶排序的时间复杂度为O(n + k)，是高效的排序算法，适用于大规模的数据排序。 本文对C++中常用的排序算法进行了详细的介绍和分析，包括快速排序、冒泡排序和桶排序三种经典算法的实现代码和原理分析。