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

一时失言乱红尘 2023-01-16 09:43 152阅读 0赞

## 双向递归 ##

### python版 ###

def quick(start_index,end_index,arr):
        # 递归
        if start_index >= end_index:
            return
        base = getBase(start_index,end_index,arr)
        quick(start_index,base-1,arr)
        quick(base+1,end_index,arr)
    
    def getBase(start_index,end_index,arr):
        # 双边循环
        # 必须从右边开始，为了保证指针重合点小于基准元素
        basic = start_index
        while start_index != end_index:
            while start_index < end_index and arr[end_index] > arr[basic]:
                end_index -= 1
            while start_index < end_index and arr[start_index] <= arr[basic]:
                start_index += 1
            if start_index < end_index:
                arr[start_index],arr[end_index] = arr[end_index],arr[start_index]
        arr[basic],arr[start_index] = arr[start_index], arr[basic]
        return start_index
    
    list = [3,4,14,1,5,6,7,8,-1,0,3,1,3,9,11]
    
    quick(0,len(list)-1,list)
    print(list)

### java版 ###

import java.util.Arrays;
    //双向递归
    public class Quick { 
        public static void quick(int startIndex,int endIndex,int[] arr ){ 
            if(startIndex >= endIndex){ 
                return;
            }
            int base = getBase(startIndex,endIndex,arr);
            quick(startIndex,base-1,arr);
            quick(base+1,endIndex,arr);
        }
        public static int getBase(int startIndex,int endIndex,int[] arr){ 
            int startIndexCopy = startIndex;
            while (startIndex != endIndex){ 
                while (startIndex < endIndex && arr[endIndex] > arr[startIndexCopy]){ 
                    endIndex--;
                }
                while (startIndex < endIndex && arr[startIndex] <= arr[startIndexCopy]){ 
                    startIndex++;
                }
                if(startIndex < endIndex){ 
                    int tmp = arr[startIndex];
                    arr[startIndex] = arr[endIndex];
                    arr[endIndex] = tmp;
                }
            }
            int tmp = arr[startIndexCopy];
            arr[startIndexCopy] = arr[startIndex];
            arr[startIndex] = tmp;
    
            return startIndex;
        }
        public static void main(String[] args){ 
            int[] arr = new int[]{ 3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11};
            quick(0,arr.length-1,arr);
            System.out.println(Arrays.toString(arr));
        }
    }

### javascript版 ###

## 双向非递归 ##

### python版 ###

def quick(start_index,end_index,arr):
        # 非递归
        stack = []
        initIndex = { 'start_index':start_index,'end_index':end_index}
        stack.append(initIndex)
        
        while len(stack):
            index = stack.pop()
            start_index = index.get('start_index')
            end_index = index.get('end_index')
            base = getBase(start_index,end_index,arr)
            if start_index < base-1:
                left = { 'start_index':start_index,'end_index':base-1}
                stack.append(left)
            if base + 1 < end_index:
                right = { 'start_index':base+1,'end_index':end_index}
                stack.append(right)
    
    def getBase(start_index,end_index,arr):
        # 双边循环
        # 必须从右边开始，为了保证指针重合点小于基准元素
        basic = start_index
        while start_index != end_index:
            while start_index < end_index and arr[end_index] > arr[basic]:
                end_index -= 1
            while start_index < end_index and arr[start_index] <= arr[basic]:
                start_index += 1
            if start_index < end_index:
                arr[start_index],arr[end_index] = arr[end_index],arr[start_index]
        arr[basic],arr[start_index] = arr[start_index], arr[basic]
        return start_index
    
    list = [3,4,14,1,5,6,7,8,-1,0,3,1,3,9,11]
    
    quick(0,len(list)-1,list)
    print(list)

### java版 ###

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    //双向非递归
    public class StackQuick { 
        public static void stackQuick(int startIndex,int endIndex,int[] arr) { 
            Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();
            Map indexMap = new HashMap();
            indexMap.put("startIndex", startIndex);
            indexMap.put("endIndex", endIndex);
            quickSortStack.push(indexMap);
    
            while (!quickSortStack.isEmpty()) { 
                Map<String, Integer> index = quickSortStack.pop();
                int baseIndex = findBase(index.get("startIndex"), index.get("endIndex"), arr);
                if (index.get("startIndex") < baseIndex - 1) { 
                    Map<String, Integer> leftIndex = new HashMap<String, Integer>();
                    leftIndex.put("startIndex", index.get("startIndex"));
                    leftIndex.put("endIndex", baseIndex - 1);
                    quickSortStack.push(leftIndex);
                }
                if (baseIndex + 1 < index.get("endIndex")) { 
                    Map<String, Integer> rightIndex = new HashMap<String, Integer>();
                    rightIndex.put("startIndex", baseIndex + 1);
                    rightIndex.put("endIndex", endIndex);
                    quickSortStack.push(rightIndex);
                }
            }
        }
        public static int findBase(int startIndex,int endIndex,int[] arr){ 
            int baseNumber = arr[startIndex];
            int mark = startIndex;
    
            for (int i = startIndex+1;i <= endIndex;i++){ 
                if(arr[i] < baseNumber){ 
                    mark++;
                    int tmp = arr[mark];
                    arr[mark] = arr[i];
                    arr[i] = tmp;
                }
            }
            arr[startIndex] = arr[mark];
            arr[mark] = baseNumber;
            return mark;
        }
        public static void main(String[] args){ 
            int[] arr = new int[]{ 3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11};
            stackQuick(0,arr.length-1,arr);
            System.out.println(Arrays.toString(arr));
        }
    }

### javascript版 ###

## 单向递归 ##

### python版 ###

### java版 ###

import java.util.Arrays;
    //单向递归
    public class UnilateralQuick { 
        public static void unilateralQuick(int startIndex,int endIndex,int[] arr){ 
            if(startIndex >= endIndex){ 
                return;
            }
            int base = findBase(startIndex,endIndex,arr);
            unilateralQuick(startIndex,base-1,arr);
            unilateralQuick(base+1,endIndex,arr);
        }
        public static int findBase(int startIndex,int endIndex,int[] arr){ 
            int baseNumber = arr[startIndex];
            int mark = startIndex;
    
            for (int i = startIndex+1;i <= endIndex;i++){ 
                if(arr[i] < baseNumber){ 
                    mark++;
                    int tmp = arr[mark];
                    arr[mark] = arr[i];
                    arr[i] = tmp;
                }
            }
            arr[startIndex] = arr[mark];
            arr[mark] = baseNumber;
            return mark;
        }
        public static void main(String[] args){ 
            int[] arr = new int[]{ 3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11};
            unilateralQuick(0,arr.length-1,arr);
            System.out.println(Arrays.toString(arr));
        }
    }

### javascript版 ###

## 单向非递归 ##

### python版 ###

def quick(start_index,end_index,arr):
        # 非递归
        stack = []
        initIndex = { 'start_index':start_index,'end_index':end_index}
        stack.append(initIndex)
        
        while len(stack):
            index = stack.pop()
            start_index = index.get('start_index')
            end_index = index.get('end_index')
            base = getBase(start_index,end_index,arr)
            if start_index < base-1:
                left = { 'start_index':start_index,'end_index':base-1}
                stack.append(left)
            if base + 1 < end_index:
                right = { 'start_index':base+1,'end_index':end_index}
                stack.append(right)
    
    def getBase(start_index,end_index,arr):
        # 单边循环
        mark = start_index
        for i in range(start_index+1,end_index+1):
            if arr[i] < arr[start_index]:
                mark+=1
                arr[i],arr[mark] = arr[mark],arr[i]
        arr[start_index], arr[mark] = arr[mark], arr[start_index]
        return mark
    
    list = [3,4,14,1,5,6,7,8,-1,0,3,1,3,9,11]
    
    quick(0,len(list)-1,list)
    print(list)

### java版 ###

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    //单向非递归
    public class StackUnilateralQuick { 
        public static void stackUnilateralQuick(int startIndex,int endIndex,int[] arr){ 
            Stack<Map<String,Integer>> quickSortStack = new Stack<Map<String, Integer>>();
            Map indexMap = new HashMap();
            indexMap.put("startIndex",startIndex);
            indexMap.put("endIndex",endIndex);
            quickSortStack.push(indexMap);
    
            while(!quickSortStack.isEmpty()){ 
                Map<String,Integer> index = quickSortStack.pop();
                int baseIndex = findBase(index.get("startIndex"),index.get("endIndex"),arr);
                if (index.get("startIndex") < baseIndex - 1){ 
                    Map<String ,Integer> leftIndex = new HashMap<String, Integer>();
                    leftIndex.put("startIndex",index.get("startIndex"));
                    leftIndex.put("endIndex",baseIndex - 1);
                    quickSortStack.push(leftIndex);
                }
                if (baseIndex + 1 < index.get("endIndex") ){ 
                    Map<String,Integer> rightIndex = new HashMap<String, Integer>();
                    rightIndex.put("startIndex",baseIndex + 1);
                    rightIndex.put("endIndex",endIndex);
                    quickSortStack.push(rightIndex);
                }
            }
    
        }
        public static int findBase(int startIndex,int endIndex,int[] arr){ 
            int mark = startIndex;
            int baseNumber = arr[startIndex];
    
            for (int i = startIndex + 1; i <= endIndex; i++){ 
                if(arr[i] < baseNumber){ 
                    mark ++;
                    int tmp = arr[i];
                    arr[i] = arr[mark];
                    arr[mark] = tmp;
                }
            }
    
            arr[startIndex] = arr[mark];
            arr[mark] = baseNumber;
    
            return mark;
        }
    
        public static void main(String[] args){ 
            int[] arr = new int[]{ 4,7,6,5,3,2,8,1};
            stackUnilateralQuick(0,arr.length-1,arr);
            System.out.println(Arrays.toString(arr));
        }
    }

### javascript版 ###