冒泡排序

import java.util.*;

// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass

int[] sort(int[] arr) {
    int len = arr.length;
    int[] items = Arrays.copyOf(arr, len);
    for (int end = len; end > 1; end--) {
        boolean swapped = false;
        for (int j = 1; j < end; j++) {
            if (items[j] < items[j - 1]) {
                int tmp = items[j];
                items[j] = items[j - 1];
                items[j - 1] = tmp;
                swapped = true;
            }
        }           
        if (!swapped) {
            break;
        }
    } 
    return items; 
}

int[] items = { 4, 1, 5, 3, 2 };

int[] sortItems = sort(items);
// sortItems is {1, 2, 3, 4, 5}
System.out.println(Arrays.toString(sortItems));

// *** simplified speed test ***
items = new int[200];
for (int i = 0; i < items.length; i++) {
    items[i] = items.length - 1 - i;
}
int count = 10000;
Date start = new Date();

for (int i = 0; i < count; i++)
    sort(items);

long milliseconds = (new Date()).getTime() - start.getTime();

System.out.println(milliseconds + " milliseconds");
// about 221 milliseconds