快速排序

递归实现

快速排序方式1

/**
 * 快速排序入口。
 * @param array 待排序的数组
 */
public static void quickSort(int[] array) {
	quickSort(array, 0, array.length - 1);
}

/**
 * 对数组中从left到right的区域进行快速排序
 * @param array 待排序的数组
 * @param left 本次待排序序列的起始位置
 * @param right 本次待排序序列的结束位置
 */
private static void quickSort(int[] array, int left, int right) {
	if (left < right) {
		int index = quickSortOne(array, left, right);
		quickSort(array, left, index - 1);
		quickSort(array, index + 1, right);
	}
}

/**
 * 进行一趟快速排序
 * @param array 待排序的数组
 * @param left 待排序的序列的起始位置
 * @param right 待排序序列的结束位置
 * @return 分割的位置
 */
private static int quickSortOne(int[] array, int left, int right) {
	int pivot = array[left];
	int start = left;
	int end = right;
	while (start < end) {
		// 从右向左查找查找第一个比基准数小的元素
		// 如果a[j]大于等于基准数，继续查找
		while (array[end] >= pivot && start < end) {
			end--;
		}
		// 从左向右查找第一个比基准数大的元素
		// 也就是当a[i]小于等于基准数的时候，还得继续查找
		while (array[start] <= pivot && start < end) {
			start++;
		}
		// 交换大于基准数的元素和小于基准数的元素的位置
		swap(array, start, end);
	}
	// 把基准数放到中间
	swap(array, left, start);
	// 返回分割点的下标
	return start;
}

/**
 * 交换数字中的两个元素的位置
 * @param array 数组
 * @param left 数字前面的元素
 * @param right 数组后面的元素
 */
private static void swap(int[] array, int left, int right) {
	int temp = array[left];
	array[left] = array[right];
	array[right] = temp;
}

快速排序改进型：省略swap函数的情况

上面的算法为：

• 使用一个变量，记录下基准数的值，从后向前查找比基准数小的数，
• 然后从前向后查找大的数，
• 然后把比基准数小的和比基准数大的进行交换。这样需要使用一个交换方法来实现。

那么这个方法能不能省略掉呢？
是可以的，

• 使用一个变量，记录下基准数的值，从后向前查找比基准数小的数，
• 找到以后直接把这个小的数，放到原来基准数的位置上。(因为我们已经记下了基准数的位置，所以不用担心这个数被覆盖掉)
• 然后从前往后查找比基准数大的数，然后把这个数放到上一步找到的比基准数小的数的位置上。

/**
 * 对整个数组执行快速排序。
 * @param array 待排序的数组
 */
public static void quickSort(int array[]) {
    // 合法性判断
    if (array == null)
        return;
    // 对从第一个元素到最后一个元素的数组序列执行快速排序
    quickSort(array, 0, array.length - 1);
}

/**
 * 对数组中的一段连续的序列执行快速排序。
 * @param array 待排序的数组
 * @param left 数组中被分割的序列的开始位置
 * @param right 数组中被分割的序列的结束位置
 */
private static void quickSort(int array[], int left, int right) {
    // 执行一趟快速排序，并返回分割点
    int mid = quickOne(array, left, right);
    if (left < mid - 1) {
        // 对分割点左侧的序列执行快速排序
        quickSort(array, left, mid - 1);
    }
    if (mid + 1 < right) {
        // 对分割点右侧的序列执行快速排序
        quickSort(array, mid + 1, right);
    }
}

/**
 * 执行一趟快速排序
 * @param array 待排序的数组
 * @param left 被分割的序列的开始位置
 * @param right 被分割的序列的结束位置
 * @return 当前序列的分割点的位置
 */
private static int quickOne(int[] array, int left, int right) {
    // 保存基准数
    int pivot = array[left];
    while (left < right) {
        // 从右向左移动右指针，查找比基准数小的数
        while (left < right && array[right] >= pivot) {
            right--;
        }
        // 把比基准数小的放到基准数的位置
        array[left] = array[right];
        // 从左向右移动左指针，查找比基准数大的数
        while (left < right && array[left] <= pivot) {
            left++;
        }
        // 把基准数大的数放到后面
        array[right] = array[left];
    }
    // 基准数放到分割点的位置
    array[left] = pivot;
    // 返回分割点的下标
    return left;
}