【《漫画算法》笔记】快速排序

非递归实现

使用集合栈代替递归的函数栈

public static void main(String[] args) {int[] arr=new int[]{4,4,6,4,3,2,8,1};
//        int[] arr=new int[]{3,2};
//        quickSort1(arr,0,arr.length-1); // recursive, double sides
//        quickSort2(arr,0,arr.length-1);// recursive, one sidequickSort3(arr,0,arr.length-1);// not recursive,System.out.println(Arrays.toString(arr));}private static void quickSort3(int[] arr, int startIdx, int endIdx) {Stack<Map<String,Integer>> quickSortStack=new Stack<Map<String, Integer>>();Map<String,Integer> rootParam=new HashMap<>(); // 整个数列的起止下标rootParam.put("startIdx",startIdx);rootParam.put("endIdx",endIdx);quickSortStack.push(rootParam);//while(!quickSortStack.isEmpty()){Map<String,Integer> param=quickSortStack.pop();int pivotIdx=partition3(arr,param.get("startIdx"),param.get("endIdx"));System.out.println(String.valueOf(param.get("startIdx"))+","+String.valueOf(param.get("endIdx")));if(param.get("startIdx")<pivotIdx-1){Map<String,Integer> leftParam=new HashMap<>();leftParam.put("startIdx",startIdx);leftParam.put("endIdx",pivotIdx-1);quickSortStack.push(leftParam);}if(param.get("endIdx")>pivotIdx+1){Map<String,Integer> rightParam=new HashMap<>();rightParam.put("startIdx",pivotIdx+1);rightParam.put("endIdx",endIdx);quickSortStack.push(rightParam);}}}private static int partition3(int[] arr, int startIdx, int endIdx) {// System.out.println(Arrays.toString(arr));int pivot=arr[startIdx];int mark=startIdx;for (int i = startIdx; i <=endIdx ; i++) {if(pivot>arr[i]){mark++;int temp=arr[mark];arr[mark]=arr[i];arr[i]=temp;}}arr[startIdx]=arr[mark];arr[mark]=pivot;return mark;}

注：这个地方有一个很tricky的点是，if (pivot>arr[i])不能写成if(pivot>=arr[i]) (即便是把for循环修正到从startIdx+1开始，也不行，这仍然会造成无限循环，我目前还在找原因)

单边循环的递归写法

if(pivot>=arr[i]) + for(int i=startIdx+1;....)这个搭配出来的partition()函数本身是对的，见下面的“单边循环”递归版快速排序的代码

  public static void main(String[] args) {int[] arr=new int[]{4,4,6,4,3,2,8,1};
//        int[] arr=new int[]{3,2};
//        quickSort1(arr,0,arr.length-1); // recursive, double sidesquickSort2(arr,0,arr.length-1);// recursive, one sideSystem.out.println(Arrays.toString(arr));}private static void quickSort2(int[] arr, int startIdx, int endIdx) {if(startIdx>=endIdx){return;}int pivotIdx=partition2(arr,startIdx,endIdx);quickSort2(arr,startIdx,pivotIdx-1);quickSort2(arr,pivotIdx+1,endIdx);}private static int partition2(int[] arr, int startIdx, int endIdx) {int mark=startIdx;int pivot=arr[mark];for (int i = startIdx+1; i <= endIdx; i++) {if(arr[i]<=pivot){mark++;int tmp=arr[i];arr[i]=arr[mark];arr[mark]=tmp;}}arr[startIdx]=arr[mark];arr[mark]=pivot;System.out.println(String.valueOf(startIdx)+","+String.valueOf(endIdx));System.out.println(Arrays.toString(arr));System.out.println();return mark;}

双边循环的递归写法

public static void main(String[] args) {int[] arr=new int[]{4,4,6,4,3,2,8,1};
//        int[] arr=new int[]{3,2};quickSort1(arr,0,arr.length-1); // recursive, double sides
//        quickSort2(arr,0,arr.length-1);// recursive, one side
//        quickSort3(arr,0,arr.length-1);// not recursive,System.out.println(Arrays.toString(arr));}private static void quickSort1(int[] arr, int startIdx, int endIdx) {if(startIdx>=endIdx){return;}int pivot=partition1(arr,startIdx,endIdx);quickSort1(arr,startIdx,pivot-1);quickSort1(arr,pivot+1,endIdx);}private static int partition1(int[] arr, int startIdx, int endIdx) {int right=endIdx;int left=startIdx;int pivot=arr[startIdx];while (right!=left){while (right>left&&arr[right]>pivot){right--;}while(left<right&&arr[left]<=pivot){left++;}int temp=arr[right];arr[right]=arr[left];arr[left]=temp;}arr[startIdx]=arr[left];arr[left]=pivot;return left;}