# 圈排序

#### 演算法

• 如果找到元素處於正確的位置，只需保持原樣。
• 否則，通過計算小於`a`的元素總數來找到`a`的正確位置。 它必須出現在排序陣列中。 被替換的另一個元素`b`將被移動到其正確的位置。 這個過程一直持續到在`a`的原始位置得到一個元素。

``````#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
``````

``````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
``````

``````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
``````