C++ 中的循环排序
c++server side programmingprogramming
循环排序是一种有趣的排序算法，用于对给定的元素数组进行排序。该算法对数组的元素进行直径比较，一旦对一部分中的元素进行排序，则继续对数组的另一端进行直径排序。
示例
让我们直观地了解数组的循环排序。假设我们有一个包含 6 个元素的数组。
输入:
N = 6
arr [ ] = { 2, 1, 5, 8, 7, 9
当我们为每个数组元素绘制同心圆时，它将如下所示
输出:
1 2 5 7 8 9
解释: 使用对数组中的元素进行排序后循环排序，它将是 1、2、5、7、8、9。
循环排序算法
- 将数组的第一个元素与最后一个元素进行比较，将第二个元素与数组的倒数第二个元素进行比较。
- 现在将数组分成两半，然后再次使用循环排序将第一半的第一个元素与其最后一个元素进行比较。
- 递归调用步骤 1 和步骤 2，直到数组排序完成。
C++ 程序实现循环排序
示例
#include <bits/stdc++.h>
using namespace std;
bool circle_sort_rec(int * arr, int n) {
bool swaped = false;
if (n <= 2) {
if (arr[0] > arr[n - 1]) {
swap(arr[0], arr[n - 1]);
swaped = true;
}
return swaped;
}
int mid = (n + 1) / 2;
for (int i = 0; i < mid; i++) {
if (i == n - i - 1) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swaped = true;
}
} else {
if (arr[i] > arr[n - i - 1]) {
swap(arr[i], arr[n - i - 1]);
swaped = true;
}
}
}
if (circle_sort_rec(arr, mid))
swaped = true;
if (circle_sort_rec(arr + mid, n - mid))
swaped = true;
return swaped;
}
void circle_sort(int * arr, int size) {
while (circle_sort_rec(arr, size)) {
;
}
return;
}
int main() {
int size = 5;
int arr[size] = {2,1,7,4,5,9};
circle_sort(arr, size);
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
return 0;
}
输出
1 2 4 5 7
