排序算法——圆形排序（Circle Sort）【代码实现】

伪代码

function circlesort (index lo, index hi, swaps){if lo == hi return (swaps)high := hilow := lomid := int((hi-lo)/2)while lo < hi {if  (value at lo) > (value at hi) {swap.values (lo,hi)swaps++}lo++hi--}if lo == hiif (value at lo) > (value at hi+1) {swap.values (lo,hi+1)swaps++}swaps := circlesort(low,low+mid,swaps)swaps := circlesort(low+mid+1,high,swaps)return(swaps)}while circlesort (0, sizeof(array)-1, 0)

C

#include <stdio.h>int circle_sort_inner(int *start, int *end)
{
    int *p, *q, t, swapped;if (start == end) return 0;// funny "||" on next line is for the center element of odd-lengthed arrayfor (swapped = 0, p = start, q = end; p<q || (p==q && ++q); p++, q--)if (*p > *q)t = *p, *p = *q, *q = t, swapped = 1;// q == p-1 at this pointreturn swapped | circle_sort_inner(start, q) | circle_sort_inner(p, end);
}//helper function to show arrays before each call
void circle_sort(int *x, int n)
{
    do {
    int i;for (i = 0; i < n; i++) printf("%d ", x[i]);putchar('\n');} while (circle_sort_inner(x, x + (n - 1)));
}int main(void)
{
    int x[] = {
    5, -1, 101, -4, 0, 1, 8, 6, 2, 3};circle_sort(x, sizeof(x) / sizeof(*x));return 0;
}

C++

#include <iostream>int circlesort(int* arr, int lo, int hi, int swaps) {
    if(lo == hi) {
    return swaps;}int high = hi;int low = lo;int mid = (high - low) / 2;while(lo < hi) {
    if(arr[lo] > arr[hi]) {
    int temp = arr[lo];arr[lo] = arr[hi];arr[hi] = temp;swaps++;}lo++;hi--;}if(lo == hi) {
    if(arr[lo] > arr[hi+1]) {
    int temp = arr[lo];arr[lo] = arr[hi+1];arr[hi+1] = temp;swaps++;}}swaps = circlesort(arr, low, low+mid, swaps);swaps = circlesort(arr, low+mid+1, high, swaps);return swaps;
}void circlesortDriver(int* arr, int n) {
    do {
    for(int i = 0; i < n; i++) {
    std::cout << arr[i] << ' ';}std::cout << std::endl;} while(circlesort(arr, 0, n-1, 0));
}int main() {
    int arr[] = {
     6, 7, 8, 9, 2, 5, 3, 4, 1 };circlesortDriver(arr, sizeof(arr)/sizeof(int));return 0;
}

Go

package mainimport "fmt"func circleSort(a []int, lo, hi, swaps int) int {
    if lo == hi {
    return swaps}high, low := hi, lomid := (hi - lo) / 2for lo < hi {
    if a[lo] > a[hi] {
    a[lo], a[hi] = a[hi], a[lo]swaps++}lo++hi--}if lo == hi {
    if a[lo] > a[hi+1] {
    a[lo], a[hi+1] = a[hi+1], a[lo]swaps++}}swaps = circleSort(a, low, low+mid, swaps)swaps = circleSort(a, low+mid+1, high, swaps)return swaps
}func main() {
    aa := [][]int{
    {
    6, 7, 8, 9, 2, 5, 3, 4, 1},{
    2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1},}for _, a := range aa {
    fmt.Printf("Original: %v\n", a)for circleSort(a, 0, len(a)-1, 0) != 0 {
    // empty block}fmt.Printf("Sorted : %v\n\n", a)}
}

Java

import java.util.Arrays;public class CircleSort {
    public static void main(String[] args) {
    circleSort(new int[]{
    2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1});}public static void circleSort(int[] arr) {
    if (arr.length > 0)do {
    System.out.println(Arrays.toString(arr));} while (circleSortR(arr, 0, arr.length - 1, 0) != 0);}private static int circleSortR(int[] arr, int lo, int hi, int numSwaps) {
    if (lo == hi)return numSwaps;int high = hi;int low = lo;int mid = (hi - lo) / 2;while (lo < hi) {
    if (arr[lo] > arr[hi]) {
    swap(arr, lo, hi);numSwaps++;}lo++;hi--;}if (lo == hi && arr[lo] > arr[hi + 1]) {
    swap(arr, lo, hi + 1);numSwaps++;}numSwaps = circleSortR(arr, low, low + mid, numSwaps);numSwaps = circleSortR(arr, low + mid + 1, high, numSwaps);return numSwaps;}private static void swap(int[] arr, int idx1, int idx2) {
    int tmp = arr[idx1];arr[idx1] = arr[idx2];arr[idx2] = tmp;}
}

Kotlin

// version 1.1.0fun<T: Comparable<T>> circleSort(array: Array<T>, lo: Int, hi: Int, nSwaps: Int): Int {
    if (lo == hi) return nSwapsfun swap(array: Array<T>, i: Int, j: Int) {
    val temp  = array[i]array[i]  = array[j]array[j]  = temp}var high  = hivar low   = loval mid   = (hi - lo) / 2var swaps = nSwapswhile (low < high) {
    if (array[low] > array[high]) {
    swap(array, low, high)swaps++}low++high--}if (low == high)if (array[low] > array[high + 1]) {
    swap(array, low, high + 1)swaps++}swaps = circleSort(array, lo, lo + mid, swaps)swaps = circleSort(array, lo + mid + 1, hi, swaps)return swaps
}fun main(args: Array<String>) {
    val array = arrayOf(6, 7, 8, 9, 2, 5, 3, 4, 1)println("Original: ${
      array.asList()}")while (circleSort(array, 0, array.size - 1, 0) != 0) ; // empty statementprintln("Sorted : ${
      array.asList()}")println()val array2 = arrayOf("the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog")println("Original: ${
      array2.asList()}")while (circleSort(array2, 0, array2.size - 1, 0) != 0) ;println("Sorted : ${
      array2.asList()}")    
}

Perl

sub circlesort {
    our @x; local *x = shift;my($beg,$end) = @_;my $swaps = 0;if ($beg < $end) {
    my $lo = $beg;my $hi = $end;while ($lo < $hi) {
    if ($x[$lo] > $x[$hi]) {
     # 'gt' here for string comparison@x[$lo,$hi] = @x[$hi,$lo];++$swaps;}++$hi if --$hi == ++$lo}$swaps += circlesort(\@x, $beg, $hi);$swaps += circlesort(\@x, $lo, $end);}$swaps;
}my @a = <16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88>;
while (circlesort(\@a, 0, $#a)) {
     print join(' ', @a), "\n" }

Perl 6

sub circlesort (@x, $beg, $end) {
    my $swaps = 0;if $beg < $end {
    my ($lo, $hi) = $beg, $end;repeat {
    if @x[$lo] after @x[$hi] {
    @x[$lo,$hi] .= reverse;++$swaps;}++$hi if --$hi == ++$lo} while $lo < $hi;$swaps += circlesort(@x, $beg, $hi);$swaps += circlesort(@x, $lo, $end);}$swaps;
}say my @x = (-100..100).roll(20);
say @x while circlesort(@x, 0, @x.end);say @x = <The quick brown fox jumps over the lazy dog.>;
say @x while circlesort(@x, 0, @x.end);

Python

#python3
#tests: expect no output.
#doctest with python3 -m doctest thisfile.py
#additional tests: python3 thisfile.pydef circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps':'''>>> L = [3, 2, 8, 28, 2,]>>> circle_sort(L)3>>> print(L)[2, 2, 3, 8, 28]>>> L = [3, 2, 8, 28,]>>> circle_sort(L)1>>> print(L)[2, 3, 8, 28]'''n = R-Lif n < 2:return 0swaps = 0m = n//2for i in range(m):if A[R-(i+1)] < A[L+i]:(A[R-(i+1)], A[L+i],) = (A[L+i], A[R-(i+1)],)swaps += 1if (n & 1) and (A[L+m] < A[L+m-1]):(A[L+m-1], A[L+m],) = (A[L+m], A[L+m-1],)swaps += 1return swaps + circle_sort_backend(A, L, L+m) + circle_sort_backend(A, L+m, R)def circle_sort(L:list)->'sort A in place, returning the number of swaps':swaps = 0s = 1while s:s = circle_sort_backend(L, 0, len(L))swaps += sreturn swaps# more tests!
if __name__ == '__main__':from random import shufflefor i in range(309):L = list(range(i))M = L[:]shuffle(L)N = L[:]circle_sort(L)if L != M:print(len(L))print(N)print(L)

Ruby

class Arraydef circle_sort!while _circle_sort!(0, size-1) > 0endselfendprivatedef _circle_sort!(lo, hi, swaps=0)return swaps if lo == hilow, high = lo, himid = (lo + hi) / 2while lo < hiif self[lo] > self[hi]self[lo], self[hi] = self[hi], self[lo]swaps += 1endlo += 1hi -= 1endif lo == hi && self[lo] > self[hi+1]self[lo], self[hi+1] = self[hi+1], self[lo]swaps += 1endswaps + _circle_sort!(low, mid) + _circle_sort!(mid+1, high)end
endary = [6, 7, 8, 9, 2, 5, 3, 4, 1]
puts "before sort: #{
      ary}"
puts " after sort: #{
      ary.circle_sort!}"

更多代码，持续更新！
整理自网络。