秒懂快排--------Java实现
快速排序(Java----实现)
快排的定义
使用分治法，将一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列·
快排的步骤
1.·挑选基准值 从数列中挑出一个元素 成为基准数
2.·分割 重新排列数列 所有比基准数小的元素，放在基准数的左边。比基准数大的元素放在基准数的右边。（与基准数相同的数放在左边 和右边都可以），在这个分割分割结束之后，对基准值的排序已经完成，这一过程称为一趟排序
3.·递归排序子序列递归地将小于基准数值元素的子序列和大于基准值元素的子序列排序
——————————————————————————————————————————————-
重点是 如何把比pivot大的数放在 pivot的右边，比pivot小的数放在pivot的左边？
定义 left 和 right 变量，left=0,right=arr.length-1; 如果取数组左边第一个元素为 基准位pivot 的话
因为基准元素在左边，所以让 right 往 左移动 当在移动的过程中，如果发现arr[right]<pivot 的话 就交换arr[right]元素 和 pivot的值，放到未来pivot的左边; 然后再去看 left这边，如果发现在移动的过程中有arr[left]>pivot的话 就交换arr[left]元素 和 pivot的值，放到未来pivot的右边边
注意 这里right 和 left 是交替进行的
这里是一趟快速排序 在一趟快速排序结束之后 pivot的位置就会更新 就会根据pivot的位置做 子列划分
划分得到的子列们 在递归调用快速排序 在分子列，在递归快排，在分子列。。。。
package com.itheima.homeworkQuickSort;
import sun.applet.Main;
/**
* @author ChenY@itheima.com
* @date 2022/7/9 17:45
*/
public class Test {
/**
* 定义快速排序方法
*/
public static void quickSort(int[] arr, int left, int right) {
//int left = 0, right = arr.length - 1;
if(left>right){
return; /** return 用于截止 和 返回*/
}
/** 涉及到排序 不仅仅是 交换那么简单了*/
int i = left, j = right; /** i和j用来访问数组中的元素*/
int pivot = arr[left]; /** 定义基准位*/
while (i < j) {
while (arr[j] > pivot && j > i) {/** 基准数从左边开始 故指针移动从右边开始*/
j--; /** 当右边数组元素的值比 基准元素大的时候 不交换*/
}
while (arr[i] < pivot && i < j) { /** 上面的循环结束的时候 意味着 arr[j}<pivot 或者 j<+i了 */
i++; /** 前者就要改变方向 排序 因为 在算法中 left和right是交替进行的*/
/** 后者意味着一趟快排结束 交替另外一边*/
}
/** s首先搞懂上面两个循环都结束了 在执行下面的语句*/
/** 这就意味着 排除&&后面的条件 ，在right 移动的过程中 出现了 比基准数小的数 arr[j]*/
/** 在left这边 移动的过程中 出现了 比 基准元素要大的数 arr[i]*/
/** 如果是&&前面的问题 就要交换*/
if (i < j) {
pivot = arr[j]; /** j是比pivot 的值要小*/
arr[j] = arr[i];
arr[i] = pivot;
}
}
/** 至此 一趟快排 结束 划分子列*/
arr[left] = arr[i];
arr[i] = pivot;
/** 子列递归调用快排*/
quickSort(arr, left, j- 1); /** 左子列*/
/** i=pivot */
quickSort(arr, j + 1, right); /** 右子列*/
}
/**
* Drive Main
*/
public static void main(String[] args) {
int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
System.out.print("排序前：");
for (int m = 0; m < arr.length; m++) {
System.out.print(arr[m]+" ");
}
/** 调用快速排序*/
quickSort(arr,0,arr.length-1);
System.out.println();
System.out.print("排序后: ");
for (int n = 0; n < arr.length; n++) {
System.out.print(arr[n]+" ");
}
}
}
