java非递归快速排序

柔情只为你懂 2022-03-22 03:19 242阅读 0赞

## java非递归 快速排序 ##

public static void quickSort(int[] a) {
    	//创建类保存开始结束索引
    
    	//创建list 模拟栈，先入后出
    	LinkedList<int[]> stack = new LinkedList<>();
    	//加入初始数据，第一次执行
    	stack.addFirst(new int[]{0, a.length - 1});
    	//循环执行栈内的数据，直至排序完成
    	while (!stack.isEmpty()) {
    		int[] tuple = stack.removeFirst();
    		int start = tuple[0], end = tuple[1], i = tuple[0], j = tuple[1];
    
    		while (j > i) {
    			//从右边开始找到一个大于第0 位数的数，也可能找不到
    			while (j > i && a[j] > a[start]) {
    				j--;
    			}
    			//从左边查找第一个小于第 0 位的数，也可能找不到
    			while (j > i && a[i] <= a[start]) {
    				i++;
    			}
    			//i j 不是同一个数就交换，找不到的情况下 i j 是一样的，这是就不用交换了
    			if (j > i) {
    				int temp = a[j];
    				a[j] = a[i];
    				a[i] = temp;
    				System.out.println("排序中" + Arrays.toString(a));
    			}
    		}
    		if (start != i) {
    			int temp = a[start];
    			a[start] = a[i];
    			a[i] = temp;
    			System.out.println("排序中" + Arrays.toString(a));
    		}
    
    		if (i - 1 > start) {
    			stack.addFirst(new int[]{0, i - 1});
    		}
    		if (j + 1 < end) {
    			stack.addFirst(new int[]{j + 1, end});
    		}
    
    	}
    
    }

发表评论取消回复

表情：

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

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

相关阅读

相关非递归算法——快速排序、归并排序

![30adcf5df8b44dc8bc660f667cada2c4.jpeg][] 哈喽大家好，我是保护小周ღ，本期为大家带来的是常见[排序算法][Link 1]中的快

古城微笑少年丶/ 2023年10月03日 19:34/ 0 赞/ 15 阅读

相关快速排序的双指针递归与非递归、单指针递归与非递归实现

双向递归 python版 def quick(start_index,end_index,arr): 递归 if star

一时失言乱红尘/ 2023年01月16日 09:43/ 0 赞/ 170 阅读

相关 238-快速排序算法(递归，非递归，随机取）

快速排序算法（递归）的实现 int Parition(int ar, int left,int right) { assert

Love The Way You Lie/ 2022年11月12日 01:44/ 0 赞/ 207 阅读

相关【Java】非递归实现快速排序(LinkedHashMap)

package edu.xlead; import java.util.Arrays; import java.util.Iterator;

野性酷女/ 2022年10月02日 12:47/ 0 赞/ 172 阅读

相关 C#实现(递归和非递归)快速排序和简单排序

本人因为最近工作用到了一些排序算法，就把几个简单的排序算法，想冒泡排序，选择排序，插入排序，奇偶排序和快速排序等整理了出来，代码用C\代码实现，并且通过了测试。希望能给大家提供

Myth丶恋晨/ 2022年09月19日 00:26/ 0 赞/ 249 阅读

相关快速排序递归与非递归

递归法快排的思想设当前需要排序的数组为int A\[bt...ed\] 分解：在A\[\]中任选一个记录作为基准（pivot

素颜马尾好姑娘i/ 2022年09月18日 01:59/ 0 赞/ 243 阅读

相关快速排序的递归与非递归实现

import java.util.Arrays; import java.util.Stack; class QuickSort {

╰半夏微凉°/ 2022年06月09日 00:42/ 0 赞/ 255 阅读

相关快速排序非递归算法

define MaxN 1000 typedef int keytype; void QUICKSORT(keytype K[],int n){

柔光的暖阳◎/ 2022年04月13日 04:09/ 0 赞/ 238 阅读

相关 java非递归快速排序

java非递归快速排序 public static void quickSort(int[] a) { //创建类保存开始结束索引

柔情只为你懂/ 2022年03月22日 03:19/ 0 赞/ 243 阅读

相关非递归的快速排序

一般的快速排序是用递归来实现的，如何将快速排序改写为迭代而不是递归？由于递归函数需要保护现场（在栈中），所以可以认为的构建一个栈。由于快速排序中处理排序是partition

骑猪看日落/ 2022年02月24日 13:58/ 0 赞/ 266 阅读