排序

冒泡排序
快速排序
堆排序
桶排序

1. 快速排序

1.选择数组第一个数array[low]为基准元素，其值为基准值pivot，基准指针为p_pos
2.把比基准值小的都放左边    if(array[i]<pivot)
    遍历，通过一个基准指针来移动，比基准值小则指针+1并交换位置    fori、p_pos++、array[p_pos] <-> array[i]
    遍历结束，把基准元素和指针所指的元素交换    array[low] <-> array[p_pos]
3.分治，使用递归把基准元素左、右分别快排    [low, p_pos-1]、[low+1, high]

public void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int p_pos = low, pivot = array[p_pos], temp;
        for (int i = low+1; i <= high; i++) {
            if (array[i] < pivot) {
                p_pos++;
                temp = array[p_pos];
                array[p_pos] = array[i];
                array[i] = temp;
            }
        }
        temp = array[low];
        array[low] = array[p_pos];
        array[p_pos] = temp;
        quickSort(array, low, p_pos-1);
        quickSort(array, p_pos+1, high);
    }
}

2. 排序算法稳定性和复杂度