圈排序是一种比较排序算法，它强制将数组分解为圈数，其中每个圈可以旋转以生成排序数组。 理论上它在理论上是最优的，它减少了对原始数组的写入次数。
算法
考虑一组n个不同的元素。 给出元素a，可以通过计算小于a的元素的数量来计算a的索引。
- 如果找到元素处于正确的位置，只需保持原样。
- 否则，通过计算小于
a的元素总数来找到a的正确位置。 它必须出现在排序数组中。 被替换的另一个元素b将被移动到其正确的位置。 这个过程一直持续到在a的原始位置得到一个元素。
所示过程构成一个循环圈，为列表的每个元素重复此循环。 结果列表将被排序。
使用C语言实现圈排序的示例代码如下所示 -
#include<stdio.h>
void sort(int a[], int n)
{
int writes = 0,start,element,pos,temp,i;
for (start = 0; start <= n - 2; start++) {
element = a[start];
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos++;
if (pos == start)
continue;
while (element == a[pos])
pos += 1;
if (pos != start) {
//swap(element, a[pos]);
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
while (pos != start) {
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos += 1;
while (element == a[pos])
pos += 1;
if (element != a[pos]) {
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
}
}
}
int main()
{
int a[] = {1, 9, 2, 4, 2, 10, 45, 3, 2};
int n = sizeof(a) / sizeof(a[0]),i;
sort(a, n);
printf("After sort, array : ");
for (i = 0; i < n; i++)
printf("%d ",a[i]);
return 0;
}
执行上面示例代码，得到以下结果：
After sort, array :
1
2
2
2
3
4
9
10
45
使用Java语言实现圈排序的示例代码如下所示 -
public class CycleSort
{
static void sort(int a[], int n)
{
int writes = 0,start,element,pos,temp,i;
for (start = 0; start <= n - 2; start++) {
element = a[start];
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos++;
if (pos == start)
continue;
while (element == a[pos])
pos += 1;
if (pos != start) {
//swap(element, a[pos]);
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
while (pos != start) {
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos += 1;
while (element == a[pos])
pos += 1;
if (element != a[pos]) {
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
}
}
}
public static void main(String[] args)
{
int a[] = { 1, 9, 2, 4, 2, 10, 45, 3, 2 };
int n = a.length,i;
sort(a, n);
System.out.println("After sort, array : ");
for (i = 0; i < n; i++)
System.out.println(a[i]);
}
}
执行上面示例代码，得到以下结果：
After sort, array :
1
2
2
2
3
4
9
10
45
使用C#语言实现圈排序的示例代码如下所示 -
using System;
public class CycleSort
{
static void sort(int[] a, int n)
{
int writes = 0,start,element,pos,temp,i;
for (start = 0; start <= n - 2; start++) {
element = a[start];
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos++;
if (pos == start)
continue;
while (element == a[pos])
pos += 1;
if (pos != start) {
//swap(element, a[pos]);
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
while (pos != start) {
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos += 1;
while (element == a[pos])
pos += 1;
if (element != a[pos]) {
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
}
}
}
public void Main()
{
int[] a = { 1, 9, 2, 4, 2, 10, 45, 3, 2 };
int n = a.Length,i;
sort(a, n);
Console.WriteLine("After sort, array : ");
for (i = 0; i < n; i++)
Console.WriteLine(a[i]);
}
}
执行上面示例代码，得到以下结果：
After sort, array :
1
2
2
2
3
4
9
10
45
