Java
sort
algorithm

QuickSortのプログラムを書いてみました。
再帰を使うと便利ですね。

クイックソートは、
1. データ列からPivotを選ぶ
2. Pivotより大きいものと小さいものに分ける
3. 分けたそれぞれを整列
というようにソートしていきます。

Pivotが、データ列の中央に位置するような場合は、ソートのなかで計算量が最も少ないアルゴリズムで、計算量はO(nlogn)で済みます。
Pivotが一番端に来るような場合はO(n^2)かかってしまいます。

QuickSort.java
import java.util.*;
public class QuickSort {
    public static boolean debug = false;
    private static int partition(int[] a,int l,int r){
    if(debug)System.out.print("partition l="+l+", r="+r);
    int pivot = a[r];
    int i = l;
    int j = r-1;
    for (;;) {
        while (a[i] < pivot) ++i;
        while (i<j && a[j] >= pivot) --j;
        if(debug) System.out.println("check i="+i+" ,j="+j+" ,pivot="+pivot);
        if(i>=j) break;
        if(debug) System.out.println("change i="+i+" ,j="+j);
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    int tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;
    return i;
    }
    private static void quickSort(int[] a,int l,int r){
    if(l >= r) return;
    int v = partition(a,l,r);
    if(debug) System.out.println("l="+l+", r="+r+", v"+v+": "+toString(a));
    quickSort(a,l,v-1);
    quickSort(a,v+1,r);
    }
    public static void sort(int[] a){
    quickSort(a,0,a.length-1);
    }
    public static String toString(int[] a){
    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < a.length; i++) sb.append(a[i]+" ");
    return sb.toString();
    }
    public static void main(String[] args) {
    if(args.length > 0 && args[0].equals("-d")) debug = true;
    Scanner sc = new Scanner(System.in);
    System.out.print("データの個数を入力してください ");
    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = sc.nextInt();
    sort(a);
    System.out.println(toString(a));
    }
}