循环排序是一种比较排序算法, 它强制将数组分解为循环数, 其中每个循环都可以旋转以生成排序数组。从理论上讲, 它是最佳的, 因为它减少了对原始数组的写入次数。
算法
考虑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 :12223491045Java程序
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 :12223491045C＃程序
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 :12223491045
