/**
 * 快速排序算法
 */
public static void quickSort(int[] list, int left, int right) {
    if (left < right) {
        // 分割数组，找到分割点
        int point = partition(list, left, right);

        // 递归调用，对左子数组进行快速排序
        quickSort(list, left, point - 1);
        // 递归调用，对右子数组进行快速排序
        quickSort(list, point + 1, right);
    }
}

/**
 * 分割数组，找到分割点
 */
public static int partition(int[] list, int left, int right) {
    // 用数组的第一个元素作为基准数
    int first = list[left];
    while (left < right) {
        while (left < right && list[right] >= first) {
            right--;
        }
        // 交换
        swap(list, left, right);

        while (left < right && list[left] <= first) {
            left++;
        }
        // 交换
        swap(list, left, right);
    }
    // 返回分割点所在的位置
    return left;
}

/**
 * 交换数组中两个位置的元素
 */
public static void swap(int[] list, int left, int right) {
    int temp;
    if (list != null && list.length > 0) {
        temp = list[left];
        list[left] = list[right];
        list[right] = temp;
    }
}

/**
 * 希尔排序算法
 */
public static void shellSort(int[] list) {
	int len = list.length ;
    // 取增量
    int gap = len / 2;

    while (gap >= 1) {
        // 无序序列
        for (int i = gap; i < len; i++) {
            int temp = list[i];
            int j;

            // 有序序列
            for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
        
        // 缩小增量
        gap = gap / 2;
    }
}

/**
 * 堆排序算法
 */
public static void heapSort(int[] list) {
    // 将无序堆构造成一个大根堆，大根堆有length/2个父节点
    for (int i = list.length / 2 - 1; i >= 0; i--) {
        headAdjust(list, i, list.length);
    }

    // 逐步将每个最大值的根节点与末尾元素交换，并且再调整其为大根堆
    for (int i = list.length - 1; i > 0; i--) {
        // 将堆顶节点和当前未经排序的子序列的最后一个元素交换位置
        swap(list, 0, i);
        headAdjust(list, 0, i);
    }
}

/**
 * 构造大根堆
 */
public static void headAdjust(int[] list, int parent, int length) {
    // 保存当前父节点
    int temp = list[parent];

    // 得到左孩子节点
    int leftChild = 2 * parent + 1;

    while (leftChild < length) {
        // 如果parent有右孩子，则要判断左孩子是否小于右孩子
        if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
            leftChild++;
        }
        // 父亲节点大于子节点，就不用做交换
        if (temp >= list[leftChild]) {
            break;
        }
        // 将较大子节点的值赋给父亲节点
        list[parent] = list[leftChild];
        // 然后将子节点做为父亲节点
        parent = leftChild;
        // 找到该父亲节点较小的左孩子节点
        leftChild = 2 * parent + 1;
    }
    // 最后将temp值赋给较大的子节点，以形成两值交换
    list[parent] = temp;
}

/**
 * 交换数组中两个位置的元素
 */
public static void swap(int[] list, int top, int last) {
    int temp = list[top];
    list[top] = list[last];
    list[last] = temp;
}

/**
 * 归并排序算法
 * @param list     待排序的列表
 * @param tempList 临时列表
 * @param head     列表开始位置
 * @param rear     列表结束位置
 */
public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
    if (head < rear) {
        // 取分割位置
        int middle = (head + rear) / 2;
        // 递归划分列表的左序列
        mergeSort(list, tempList, head, middle);
        // 递归划分列表的右序列
        mergeSort(list, tempList, middle + 1, rear);
        // 列表的合并操作
        merge(list, tempList, head, middle + 1, rear);
    }
}

/**
 * 合并操作(列表的两两合并)
 * @param list
 * @param tempList
 * @param head
 * @param middle
 * @param rear
 */
public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
    // 左指针尾
    int headEnd = middle - 1;
    // 右指针头
    int rearStart = middle;
    // 临时列表的下标
    int tempIndex = head;
    // 列表合并后的长度
    int tempLength = rear - head + 1;

    // 先循环两个区间段都没有结束的情况
    while ((headEnd >= head) && (rearStart <= rear)) {
        // 如果发现右序列大，则将此数放入临时列表
        if (list[head] < list[rearStart]) {
            tempList[tempIndex++] = list[head++];
        } else {
            tempList[tempIndex++] = list[rearStart++];
        }
    }

    // 判断左序列是否结束
    while (head <= headEnd) {
        tempList[tempIndex++] = list[head++];
    }

    // 判断右序列是否结束
    while (rearStart <= rear) {
        tempList[tempIndex++] = list[rearStart++];
    }

    // 交换数据
    for (int i = 0; i < tempLength; i++) {
        list[rear] = tempList[rear];
        rear--;
    }
}

/**
 * 直接选择排序算法
 */
public static void selectionSort(int[] list) {
	int len = list.length ;
    // 要遍历的次数（length-1次）
    for (int i = 0; i < len - 1; i++) {
        // 将当前下标定义为最小值下标
        int min = i;

        // 遍历min后面的数据
        for (int j = i + 1; j <= len - 1; j++) {
            // 如果有小于当前最小值的元素，将它的下标赋值给min
            if (list[j] < list[min]) {
                min = j;
            }
        }
        // 如果min不等于i，说明找到真正的最小值
        if (min != i) {
            swap(list, min, i);
        }
    }
}

/**
 * 交换数组中两个位置的元素
 */
public static void swap(int[] list, int min, int i) {
    int temp = list[min];
    list[min] = list[i];
    list[i] = temp;
}

/**
 * 直接插入排序算法
 */
public static void insertSort(int[] list) {
	int len = list.length ;
    // 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的)
    for (int i = 1; i < len; i++) {
        int temp = list[i];
        int j;
        // 遍历有序序列
        // 如果有序序列中的元素比临时元素大，则将有序序列中比临时元素大的元素依次后移
        for (j = i - 1; j >= 0 && list[j] > temp; j--) {
            list[j + 1] = list[j];
        }
        // 将临时元素插入到腾出的位置中
        list[j + 1] = temp;
    }
}

/**
 * 冒泡排序算法
 */
public static void bubbleSort(int[] list) {
	int len = list.length ;
    // 做多少轮排序（最多length-1轮）
    for (int i = 0; i < len - 1; i++) {
        // 每一轮比较多少个
        for (int j = 0; j < len - 1 - i; j++) {
            if (list[j] > list[j + 1]) {
                // 交换次序
            	int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}