宁波网站制作首推蓉胜网络好,网站地图+wordpress,做网站怎么在图片里面插字,企业年报系统官网快速排序一#xff1a;给定一个数组#xff0c;进行排序#xff0c;要求排序完成之后#xff0c;小于数组最后一个元素的数据全部在它的左边#xff0c;大于它的全部在它的右边#xff0c;左右两边内部不要求有序#xff0c;比如原数组是[5, 6, 3, 1, 2, 3]排序完之后:[…快速排序一给定一个数组进行排序要求排序完成之后小于数组最后一个元素的数据全部在它的左边大于它的全部在它的右边左右两边内部不要求有序比如原数组是[5, 6, 3, 1, 2, 3]排序完之后:[3,1,2,3,5,6 ]也就是原数组最后一个数是3排序完之后小于等于3的全部在3的左边大于3的全部在3的右边
解题思路
1、我们定义一个小于目标数据的区域它的初始位置在数组第一个元素的前面也就是下标为-1的位置取名为lessEquals
2、定义一个移动的指针初始值为指向数组的第一个元素取名为cur初始值为0
3、循环判断当cur小于数组长度的时候将cur指向的数据与数组最后一个元素对比如果小于等于最后一个元素那么将lessEquals的下一个数据与cur指向的数据交换否则cur移动到数组下一个为止
代码实现
private void printArray(int[] arr) {for (int i : arr) {System.err.print(i );}}private void swap(int[] arr, int a, int b) {int tmp arr[a];arr[a] arr[b];arr[b] tmp;}public void quickSort(int[] arr) {int lessEquals -1;int cur 0;int last arr.length - 1;while (cur last) {if (arr[cur] arr[last]) {lessEquals;swap(arr, lessEquals, cur);cur;} else {cur;}}}Testpublic void testQuickSort() {int arr[] new int[]{5, 6, 3, 1, 2, 3};quickSort(arr);printArray(arr);}
快速排序二给定一个数组进行排序要求排序完成之后小于数组最后一个元素的数据全部在它的左边大于它的全部在它的右边等于的全部在中间左右两边内部不要求有序比如原数组是[5, 6, 3, 1, 2, 3]排序完之后:[1,2,3,3,5,6 ]也就是原数组最后一个数是3排序完之后小于等于3的全部在3的左边大于3的全部在3的右边等于3的全部在中间
解题思路同上面的快速排序1类似只是在前面的基础之上增加了一个大于目标数的区域假设变量命名为greater初始值指向数组最后一个元素同时在循环的时候判断条件有所增加小于的逻辑与前面快速排序1一样如果cur指向的数据大于数组最后一个元素那么那么将greater前面的元素与cur指向的元素交换同时greater往数组的前面移动直到cur碰上last的时候退出循环
代码实现 public void quickSort1(int[] arr) {int lessEquals -1;int cur 0;int greater arr.length - 1;while (cur greater) {if (arr[cur] arr[arr.length - 1]) {lessEquals;swap(arr, lessEquals, cur);cur;} else if (arr[cur] arr[arr.length - 1]) {greater--;swap(arr, greater, cur);} else {cur;}}swap(arr, greater, arr.length - 1);}Testpublic void testQuickSort1() {int arr[] new int[]{5, 6, 3, 1, 2, 3};quickSort1(arr);printArray(arr);}
快速排序三在快速排序二的基础之上要求排序完成之后整个数组有序也就是说要求左右两边的子数组都有序实现思路就是基于快速排序二做递归迭代对左右两边的子数组继续做快排
public int[] quickSort1V2(int[] arr, int left, int right) {int cur left;int greater right;while (cur greater) {if (arr[cur] arr[right]) {swap(arr, left, cur);left;cur;} else if (arr[cur] arr[right]) {greater--;swap(arr, greater, cur);} else {cur;}}swap(arr, greater, right);return new int[]{left, greater};}public void quickSort2(int arr[], int l, int r) {if (arr null || arr.length 2) {return;}if (l r) {return;}int index[] quickSort1V2(arr, l, r);quickSort2(arr, l, index[0] - 1);quickSort2(arr, index[1] 1, r);}Testpublic void testQuickSort2() {int arr[] new int[]{5, 6, 3, 1, 2, 3};quickSort2(arr, 0, arr.length - 1);printArray(arr);}
