一、排序过程
排序的思路是不变的，这里采用挖坑法，不用递归实现，用栈实现
前面的步骤省略，当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) { Deque<Integer> 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)
