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

快排

快排的思想：

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

快排和归并排序的是互补的（算法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;
}

private static int partition2(Comparable[] a , int lo , int hi){
    Comparable v = a[lo];
      int i = lo;
     int j = hi;
    while(i < j) {
        while(i < j && a[j] >= v) --j;
        a[i] = a[j]; // 找到一个小于的, 或者就是i
        while(i < j && a[i] <=  v) ++i;
        a[j] = a[i];
    }
   a[i] = v
  return v;
}

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;
    }

}

优化

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

改进

切换插入
对于小数组，插入排序比快排更快，建议在hi - lo <= M的时候切换为插入排序，M通常去5~15。
三取样切分
去数组中随机三个数的中位数作为枢轴值
三向切分
在数组中含有大量重复数值的情况下，普通快排会多很多次交换，而采用三向切分使得包含大量重复数值的快排更快，但是降低了包含不多重复值的数组的排序速度。然而，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实现保存的下标，一次放两个，一次弹出两个，我只是喜欢将它们分别放在前后