快速排序Java实现

客官°小女子只卖身不卖艺 2022-03-12 03:28 248阅读 0赞

public class QuickSort {
    
    	public static void main(String[] args) {
    		int arr[] = { 3, 1, 5, 7, 22, 11, 77, 34, 65 };
    		quickSort(arr, 0, arr.length - 1);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.println(arr[i]);
    		}
    	}
    
    	// 定义一个划分方法，把一个数组小于num（基准数）的放左边，等于num的放中间，大于num的放右边
    	public static int[] partition(int arr[], int l, int r, int num) {
    		int less = l - 1; // less代表小于区域左边界，more代表大于区域右边界
    		int more = r + 1;
    		while (l < more) {// l相当于用来对数组遍历的下标，终止条件l<more;
    			if (arr[l] < num) {// 当l所指数值小于num
    				less++;// less右移
    				int temp = arr[l];// l和less下标数进行交换
    				arr[l] = arr[less];
    				arr[less] = temp;
    				l++;// l下边右移
    			} else if (arr[l] > num) {// 当l指向的数值大于num
    				more--; // 大于区域的边界左移
    				int temp = arr[l];
    				arr[l] = arr[more];
    				arr[more] = temp;// l下标数值发生变化，需要再次判断新数值，因此l下标停一步
    			} else {
    				l++;// 当l下标数值等于num，l右移继续遍历
    			}
    		}
    		return new int[] { less + 1, more - 1 };// 返回等于num区域的左右边界下标
    	}
    
    	public static void quickSort(int[] arr, int l, int r) {
    		if (l < r) {
    			int[] a = partition(arr, l, r, arr[r]);// 以arr[r]作为基准数，获得划分下标
    			quickSort(arr, l, a[0] - 1);// 进而分别对左右两边进行递归排序
    			quickSort(arr, a[1] + 1, r);
    		}
    	}
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，248人围观）

还没有评论，来说两句吧...

相关阅读

相关快速排序的java_快速排序的Java实现

快速排序的思想： 1、先找一个枢轴，使得整个数组的右边的数都大于等于这个数，数组左边的数都小于等于这个数 2、然后采用分治法对这个数两边的两段数组采用上述相同的方法进行排序

偏执的太偏执、/ 2022年10月23日 14:27/ 0 赞/ 143 阅读

相关 Java实现快速排序

快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则再分别对这两部分记录继续进行排序，以达到整个序列有序 p

迈不过友情╰/ 2022年06月17日 04:44/ 0 赞/ 203 阅读

相关 java实现快速排序

java实现快排 > 快速排序： public class Test01 { public static void main(String[] ar

矫情吗；*/ 2022年06月08日 04:49/ 0 赞/ 309 阅读

相关快速排序（java实现）

一、前言快速排序，听这个名字也知道这是一个性能比较好的排序算法。最坏情况下时间复杂度为O(n²），虽然最坏时间复杂度很差，但是快速排序通常是实际排序中最好的选择，因为它

客官°小女子只卖身不卖艺/ 2022年05月31日 07:23/ 0 赞/ 235 阅读

相关快速排序（java实现）

在大多数情况下，快速排序都是最快的，时间复杂度为0（n\logN）级。快速排序算法本质上就是把数组划分为2个子数组，然后递归地调用自身为每一个子数组进行快速排序来实现的。

布满荆棘的人生/ 2022年05月30日 23:25/ 0 赞/ 222 阅读

相关快速排序Java实现

public class QuickSort { public static void main(String[] args) { in

客官°小女子只卖身不卖艺/ 2022年03月12日 03:28/ 0 赞/ 249 阅读

相关 java实现快速排序

public class QuickSort{ public static void sort(int arr[],int left

向右看齐/ 2022年03月01日 14:24/ 0 赞/ 236 阅读

相关【Java】快速排序实现

交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之。在这类排序方法中最常见的是冒泡排序和快速排序。上一篇简单写了冒泡排序，这次简单写一写快速排序。

忘是亡心i/ 2022年01月06日 11:03/ 0 赞/ 237 阅读

相关 Java实现快速排序

快速排序思想快速排序是一种交换排序，所谓交换排序就是利用交换元素位置进行排序的方法。另一个交换排序是冒泡排序。快速排序是Hoare于1962年提出的一种二叉

偏执的太偏执、/ 2021年12月24日 06:01/ 0 赞/ 307 阅读

相关快速排序 java 实现

public class QuickSort { public static void quickSort(int[] arr, int front, int

╰半夏微凉°/ 2021年09月28日 13:20/ 0 赞/ 405 阅读