Sort

基本的冒泡（O(n^2)）：

public static void bubbleSort(int[] arrays, int begin, int end)
    {
        assert arrays != null;
        for (int i = begin; i < end; i++)
        {
            for (int j = begin; j < end; j++)
            {
                if (arrays[i] > arrays[j])
                {
                    swap(arrays, i, j);
                }
            }
        }
    }

    private static void swap(int[] arrays, int a, int b)
    {
        int t = arrays[a];
        arrays[a] = arrays[b];
        arrays[b] = t;
    }

常用的qsort(平均O(nlogn)，最差情况下时间复杂度为冒泡法复杂度)：

   public static void qsort(int[] arrays, int begin, int end)
    {
        if (end > begin)
        {
            int index = cmpAndSwap(arrays, begin, end);
            qsort(arrays, begin, index - 1);
            qsort(arrays, index + 1, end);
        }
    }

    private static int cmpAndSwap(int[] arrays, int l, int r)
    {
        int privot = arrays[r];
        int swapIndex = l;
        for (int i = l; i < r; i++)
        {
            if (arrays[i] > privot)
            {
                swap(arrays, i, swapIndex);
                swapIndex++;
            }
        }
        swap(arrays, swapIndex, r);
        return swapIndex;
    }
    private static void swap(int[] arrays, int a, int b)
    {
        int t = arrays[a];
        arrays[a] = arrays[b];
        arrays[b] = t;
    }

如果还知道更多的信息的排序，比如已经知道数组最大值，并且不介意浪费空间的，可以来桶排序（或者hash排序）

public static int[] mapSort(int[] arrays, int max)
    {
        int[] map = new int[max + 1];
        for (int i = 0; i < max + 1; i++)
        {
            map[i] = -1;
        }
        for (int a : arrays)
        {
            map[a]++;
        }
        return map;
    }

还有排序复杂度最好和最差相等最优解是堆排序（堆操作忘了。。手撸无能。。复杂度稳定(O(nlogn))）