快排，递归，非递归，三向切分，去掉边界条件

快排

快排的思想：

典型的分治，将数组分成两个子数组，并且分别对子数组排序，且子数组的排序也是分治。

快排和归并排序的是互补的（算法4）：都是分而治之的思想，快排是当两个子数组都有序的时候，数组自然就有序了，归并则是对两个已排序的数组再排序，之后有序。

java版本

算法四中：

private static void sort(Comparable[] a , int lo , int hi){
    if( hi <= lo ) {
          return;
      }
    int j = partition( a , lo ,hi);
    sort(a , lo , j - 1);
    sort(a , j + 1, hi);
}

private static int partition(Comparable[] a , int lo , int hi){

    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while(true){
        //扫描左边，若结束，则当前元素大于或者等于了切分元素，或者已经到了边界
        while(less(a[++i], v)){
            if (i == hi){
                break;
            }
        }
        //扫描右边，若结束，则当前元素小于或者等于了切分元素，或者已经到了边界
        while(less(v, a[--j])){
            if (j == lo){
                break;
            }
        }        
        //运行到这里 如果i == j 则说明 a[i] 也就是a[j]  等于切分元素
        //如果i > j ,说明a[i] > 元素v  a[j] < v
        //两种情况下，直接跳出循环，并且置换lo j 的元素，不然就是还没相遇，那么交换i j
        if(i >= j){
            break;
        }
        exch(a , i , j);
    }
    exch(a , lo , j);
    return j;
}

python版本

def sort_quick(arr,low,high):
    if low >= high :
        return
    j = sort_partition(arr,low,high)
    sort_quick(arr,low,j-1)
    sort_quick(arr,j+1,high)



def sort_partition(arr,low,high):
    l = low
    h = high
    comparable = arr[low]
    while l < h:
        #将列表中 小于等于枢轴值的，移动到左边
       # 下面的两个while中大小判断加 = 都是可以通过的 
        while arr[h] > comparable and l < h:
            h -= 1
        # 跳出此循环，则arr[h] <= compareble,
        arr[l] = arr[h]
      #将列表中 大于枢轴值的，移动到右边
        while arr[l] <= comparable and l < h:
            l += 1
         # 跳出此循环，则arr[l] > compareble,
        arr[h] = arr[l]
    # 跳出此循环，则 l >= h, 其实是l == h ，
    # 下面的是arr[l]  return l 也可以 
    if(l > h):
        print("l > h")
    arr[h] = comparable
    return h

去掉边界检查 算法4课后2.3.18

在排序前，便利一遍数组，找到最大值，并将最后一个与它交换，即保证最后一个元素最大，并且不再改变值，成为哨兵。于是numbers[++i] < key第一次可能会在最后一个最大元素处跳出循环，之后会以右子数组的最左，或者是partition的返回值作为哨兵。

class Solution {
    public int[] sortArray(int[] nums) {
// 最后一个元素最大
        int maximum = -1;
        int index = -1;
        for(int i  = 0 ; i < nums.length ;  ++ i){
            if(nums[i] >= maximum){
                maximum = nums[i];
                index = i;
            }
        }
        nums[index] = nums[nums.length - 1];
        nums[nums.length - 1] = maximum;
        
        sort(nums, 0 , nums.length - 1);
        return nums;
        
    }
    
    private void  sort(int [] numbers, int lo, int hi){
        if(hi <= lo) return;
        int p = partition2(numbers, lo , hi);
        sort(numbers, lo, p -1);
        sort(numbers, p + 1, hi);

    }
    
    int partition2(int[] numbers, int lo , int hi){
        int key = numbers[lo];
        int i = lo;
        int j = hi + 1;

        while(true){
// 去掉边界检查
            while(numbers[ ++ i] < key);
            while(numbers[ -- j] > key);

            if(i >= j){
                break;
            }
            int exchange = numbers[j];
            numbers[j] = numbers[i];
            numbers[i] = exchange;
        }
        numbers[lo] = numbers[j];
        numbers[j] = key;
        return j;
    }

}

优化

1. 将数组打乱
   排序的性能还取决于数组的有序度，快排是第一批偏爱随机性的算法，若有序，则最坏的复杂度是n^2
2. 考虑切分元素有重复
   考虑在遇到和枢轴值一样大小的元素的时候停下，避免不必要的交换

改进

1. 切换插入
   对于小数组，插入排序比快排更快，建议在hi - lo <= M的时候切换为插入排序，M通常去5~15。
2. 三取样切分
   去数组中随机三个数的中位数作为枢轴值
3. 三向切分
   在数组中含有大量重复数值的情况下，普通快排会多很多次交换，而采用三向切分使得包含大量重复数值的快排更快，但是降低了包含不多重复值的数组的排序速度。然而，J和D找到了更优的三向方法，可以比归并和其他排序算法更快排序包含大量重复元素的数组。
   三向切分思想：
     维护指针 lt,i,gt :
   a[ lo...lt - 1 ] 存放比枢轴值小的数
   a[ lt...i - 1 ] 存放和枢轴值一样大
   a[ i...gt ] 存放还未比较大小的数
   a[ gt + 1...hi ] 存放比枢轴值大的数

java版

private static void sort(Comparable[] a , int lo, int hi){
    if(hi <= lo){
        return;
    }
    int lt = lo, i = lo + 1, gt = hi;
    Comparable v = a[lo];
    while(i <= gt){
        int cmp = a[i].compareTo(v)
        if (cmp > 0){
            exch(a , i , gt--);
        }else if (com < 0){
            exch(a , lt++ , i++);
        }else{
            i ++;
        }

    }
    sort( a , lo , lt -1);
    sort(a , gt + 1 , hi);
}

python版

def  three_quick_sort(nums,lo,hi):
    #维持三个指针 lt i gt
    if lo >= hi:
        return
    lt = lo
    i = lo + 1
    gt = hi
    v = nums[lo]
    # [lo,lt - 1] 小于v
    # [lt,i - 1] 等于v
    # [i, gt] 未知
    # [gt + 1 , hi] 大于
    while( i <= gt):
        # i位置大于v,把它移到后面，和gt位置交换 此时的gt是未知大小
        if  v < nums[i]:
            nums[i],nums[gt] = nums[gt], nums[i]
            #这个时候 gt 上是大于v的值，i不知，所以i不能更新
            gt -= 1
        # i 位置的值小于等于 v
        elif  nums[i] < v:
            # 将 i,lt位置上的值调换
            nums[i] , nums[lt] = nums[lt] ,nums[i]
            #此时 i ,lt位置上的值都是确定大小的
            lt += 1
            i +=1
        else:
        # 最后一种可能，i位置的值 == v
            i += 1
    three_quick_sort(nums,lo,lt - 1)
    three_quick_sort(nums , gt + 1 ,hi)

a = [5,2,6,9,3,1,3,2,4,5,6,8,9]
three_quick_sort(a,0,len(a) - 1)
print(a)

不要忘记了跳出递归的条件

if lo >= hi:
        return

对于三向切分的优化

非递归的快排思想和实现

所有的递归程序 == 循环 + 栈
将递归的调用栈保存到栈中，保存的是数组的元素的下标：low 和 high，且相互对应，既可以头(low)尾(high)呼应，也可以一次弹出两个分别是low和high。

具体实现如下：

应该用stack实现保存的下标，一次放两个，一次弹出两个，我只是喜欢将它们分别放在前后

java版

class Solution {

    private void  nonCurSort(int [] numbers){
        if(numbers.length <= 1) return;
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(0);
        arr.add(numbers.length - 1);

        while( !arr.isEmpty()){

            int lo = arr.get(0);
            arr.remove(0);
            int hi = arr.get(arr.size() - 1);
            arr.remove(arr.size() - 1);
            int mid = partition2(numbers, lo , hi);
            if(mid - 1 > lo){
                arr.add(0, lo );
                arr.add(mid - 1);

            }
            if(mid + 1 < hi){
                arr.add(0, mid + 1);
                arr.add(hi);
            }
        }

    }
    

// partition函数一样
        private int partition(int[] numbers , int low , int high){
        int i = low;
        int j = high + 1;
        int key = numbers[low];
        while(true){
            while(numbers[++ i] < key){
                if( i == high){
                    break;
                }
            }
            while(numbers[ -- j] > key){
                if( j == low){
                    break;
                }
            }
            if( i >= j){
                if( i== j){
                    System.out.println(i + " " + numbers[i] );
                }
                break;
            }
            int exchange = numbers[j];
            numbers[j] = numbers[i];
            numbers[i] = exchange;
        }
        numbers[low] = numbers[j];
        numbers[j] = key;
        return j;
}

python版

'''
非递归的快排的实现
'''
import sys
def quick_sort(length, nums):
    stack = []
    stack.append(0)
    stack.append(length - 1)
    while(len(stack) != 0):
        hi = stack.pop(-1)
        lo = stack.pop(0)
        mid = sort_partition(nums,lo,hi)
# 将左边子数组放入待排
        if mid - 1 > lo:
            stack.insert(0,lo)
            stack.append(mid - 1)
# 将右边子数组放入待排
        if mid + 1 < hi: 
            stack.insert(0,mid + 1)
            stack.append(hi)
    return nums

def sort_partition(arr,low,high):
    l = low
    h = high
    comparable = arr[low]
    while l < h:
       #将列表中 小于等于枢轴值的，移动到左边
       #下面的两个while中大小判断加 = 都是可以通过的 
        while arr[h] > comparable and l < h:
            h -= 1
        # 跳出此循环，则arr[h] <= compareble,
        arr[l] = arr[h]
      #将列表中 大于枢轴值的，移动到右边
        while arr[l] <= comparable and l < h:
            l += 1
         # 跳出此循环，则arr[l] > compareble,
        arr[h] = arr[l]
    # 跳出此循环，则 l >= h, 
    # 下面的是arr[l]  return l 也可以 其实是l == h 
#    if(l > h):
 #       print("l > h")
    arr[h] = comparable
    return h



if __name__ == "__main__":
    for x in sys.stdin:
        tmp = [int(i) for i in x.strip().split(" ")]
        tmp = quick_sort(tmp[0], tmp[1:])
        ans = ""
        for i in tmp:
            ans = ans + str(i) + " "
        print(ans.strip())