冒泡排序：

基本思想：通过对待排序序列从后向前（从下标较大的元素开始） ， 依次比较相邻元素的值， 若发现逆序则交换， 使值较大的元素逐渐从前移向后部， 就象水底下的气泡一样逐渐向上冒。

public static void bubbleSort1(int [] a){
    int n = a.length - 1;
    for(int i = 0; i < n; i++){
        //表示n次排序过程。
        for(int j = 1; j < n - i; j++){
            if(a[j-1] > a[j]){
                   //前面的数字大于后面的数字就交换
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}

复杂度分析：

时间复杂度：。两个for（n）循环。
空间复杂度：最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
平均的空间复杂度为：O(1)；

快速排序法

过程如下：

class Solution {

    public int[] sortArray(int[] nums) {
        randomizedQuicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
    }

    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }    
}

复杂度分析：

时间复杂度：，其中 n 为数组长度。
空间复杂度：， 其中 h 为快速排序递归调用的层数。需要额外的的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 的空间，最优情况下每次都平衡，此时整个递归树高度为 logn，空间复杂度为 。