快速排序非递归实现

一、排序过程排序的思路是不变的这里采用挖坑法不用递归实现用栈实现前面的步骤省略当left与right相遇的时候依次将0 、4 、6、9入栈因为栈的性质以及入栈的顺序弹出的时候从右往左start为6 end为9再次排序即可排序后如图将6、7入栈后面就是重复的过程。。。二、代码实现public static void quickSort(int[] arr){ quickNor(arr,0,arr.length - 1); } private static void quickNor(int[] arr, int start, int end) { DequeInteger deque new ArrayDeque(); int pivot partitionHole(arr, start, end); if(pivot start 1){ deque.push(start); deque.push(pivot - 1); } if(pivot end - 1){ deque.push(pivot 1); deque.push(end); } while(!deque.isEmpty()){ end deque.pop(); start deque.pop(); pivot partitionHole(arr, start, end); if(pivot start 1){ deque.push(start); deque.push(pivot - 1); } if(pivot end - 1){ deque.push(pivot 1); deque.push(end); } } } private static int partitionHole(int[] arr, int left, int right) { int tmp arr[left]; while(left right) { while(left right arr[right] tmp){ right--; } arr[left] arr[right]; while(left right arr[left] tmp){ left; } arr[right] arr[left]; } arr[left] tmp; return left; }时间复杂度为 O( N *log N)