八大排序算法 之 快速排序（填坑法）

排序思想：

1，将第一个数字作为基准数字，将数组分为左右两部分，左边是比它小的数字，右边是比它大的数字；

2，将左部分按照上面的思想再次进行划分成两部分，依次类推；

3，将右部分按照上面的思想再次进行划分成两部分，依次类推；

排序趟数：

不确定

排序原理：

填坑法：

1，将第一个数字作为基准数字拿出，留下一个坑，从数组的最后开始往前循环，发现比基准数字小的就把它填到之前留下的坑里，从而在右侧得到一个新坑；

2，再从数组的头部开始循环查找，发现比基准数字大的，就将它填到之前后面数字被拿走留下的坑里，从而在左侧得到一个新坑；

3，如此往复，知道中间部位，将基准数字放到中间，完成一轮循环

参考图片：

代码实现如下：

//快速排序主方法public static void quickSort(int[] array, int low, int high){if (low < high) {int mid = findMid(array, low, high);//将第一个数作为基准，将数组分成前后两部分quickSort(array, low, mid - 1);//递归调用将左半部分再一次往下分，直至左半部分完成排序quickSort(array, mid + 1, high);//递归调用将右半部分再一次往下分，直至右半部分完成排序}}

	//将第一个数作为基准，将数组分成前后两部分--填坑法public static int findMid(int[] array, int low, int high){int temp = array[low];//将第一个数作为基准拿出,拿出留下一个坑while (low < high) {while (low < high && temp <= array[high]) {//从右开始找high --;}if (low < high) {//发现比基准数字小的，就把它填到之前基准数字留下的坑里array[low ++] = array[high];}while (low < high && temp >= array[low]) {//从左开始找low ++;}if (low < high) {//发现比基准数字大的，就把它填到之前被拿出数字留下的坑里array[high --] = array[low];}}array[low] = temp;//将基准数字放到中间将左右分成两部分return low;//返回基准数字的下标}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！