快速排序

核心思想：分治—辅助函数partition（）

普通的快速排序

首先选择数组中的一个元素，比如用 l 索引指向最左边的元素v，逐渐遍历数组所有位于l左边的元素，在遍历的过程中，我们将逐渐整理出小于v的元素和大于v的元素，当然我们继续用一个索引j来记录小于v和大于v的分界点，然后我们当前访问的元素索引为i。

那么i怎么处理呢？很简单当i指向的元素e大于v的时候，直接包含进大于v的部分中，像这样：

然后我们继续讨论下一个元素，此时i++，如图：

如果元素e小于v的时候怎么做呢？只需要把元素e（arr[i]）和橙色部分之后的一个元素（arr[j+1]）交换就可以了，交换后索引j++。或者是先进行j++，后交换arr[i]和arr[j]。如图：

最后i继续往后走，到最后的时候就直接将数组分成了等于v，小于v，大于v的三部分。

最后将l位置和j位置交换，就实现了快速排序的子过程，如图：

import java.util.*;

public class QuickSort {

    // 我们的算法类不允许产生任何实例
    private QuickSort(){}

    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(Comparable[] arr, int l, int r){

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );

        Comparable v = arr[l];

        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
                swap(arr, j+1, i);
                j ++;
            }

        swap(arr, l, j); //最后在把pivot交换到分界点

        return j;   //此时j所指的就是pivot，返回pivot所在的index
    }
    

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){
        
        int p = partition(arr, l, r); //通过调用partition函数使数组分为
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 测试 QuickSort
    public static void main(String[] args) {

        // Quick Sort也是一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("bobo.algo.QuickSort", arr);

        return;
    }
}

Python代码

import random
def QuickSort(arr):
    n = len(arr)
    QuickSortHelper(arr, 0, n-1)
    return arr


def QuickSortHelper(arr, l, r):
    if l<r:  
        p = partition(arr, l, r)
        QuickSortHelper(arr, l, p - 1)
        QuickSortHelper(arr, p + 1, r)


def partition(arr, l, r):
    ran = random.randint(l, r)  # 在数组中选择一个随机数作为pivot
    arr[ran], arr[l] = arr[l], arr[ran]
    v = arr[l] #pivotvalue
    j = l
    for i in range(l + 1, r+1, 1): #i从l+1移动到r
        if (arr[i] < v):
            arr[i], arr[j + 1] = arr[j + 1], arr[i]
            j += 1
    arr[l], arr[j] = arr[j], arr[l]
    return j

快速排序虽然高效，但并不稳定，当数组中存在大量重复元素时，比如举个例子，我用模板测试归并排序和快速排序的时间，设置一个1000000的数组，数组元素在0-10之间随机取值，那么用归并需要花费0.290727s而快排需要花费171.151s，对，你没有看错。当快速排序最优的时候是o（nlgn），而此时显然退化到了o（n^2）的级别。这是为什么？

还记得上面我写的快排的子过程么，考虑到了e>v,e<v，而e=v的情况没有考虑对吧。看了代码理解了的同学应该清楚，其实我是把等于v这种情况包含进了大于v的情况里面了，那么会出现什么问题？不管是当条件是大于等于还是小于等于v，当数组中重复元素非常多的时候，等于v的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于v的部分总是集中在数组的某一边。

双路快排–处理很多重复元素

思路：和快排不同的是，此时我们将小于v和大于v的元素放在数组的两端，那么我们将引用新的索引j的记录大于v的边界位置。

如图：把数组分为arr[l+1…i-1]<v和arr[j…r] >v两部分。

i索引不断向后扫描，当i的元素小于v的时候继续向后扫描，直到碰到了某个元素大于等于v。j同理，直到碰到某个元素小于等于v。如图：

然后绿色的部分便归并到了一起，而此时只要交换i和j的位置就可以了，然后i++，j–就行了。如图：

直到i和j遍历完毕，整个数组排序完成。

这种优化当它遇到重复元素的时候，也能近乎将他们平分开来。

代码实现思路：

在sort函数中进行partition函数操作，返回pivot。后进行sort(arr,l,p-1)和sort(arr,p+1,r)的递归调用。（关键是partition函数的构造。）

partition函数的构造

1，先随机选取一个index，并将其对应的元素于arr[l]进行交换，使其成为v

2，i的初始值从l+1开始，j从r开始。目的是：开始时arr[l+1…i)和arr（j…r]数组为空。

3，进行while（true）循环且其中有两个子while循环：只要arr[i]<v,循环继续，i++;只要arr[j]>v，循环继续，j–。

(为什么不挂等号？当 i 和 j 所指向的元素都==v时，两个元素仍然需要交换位置，这样一来不会有大量==v的元素集中在一边。而使得算法时间复杂度降低。)

当不满足两个子while循环的条件时，（意味着a[i]>=v;a[j]<=v）需要交换i,j对应两个元素

如果 i>j 则跳出循环。

4，当全部循环结束后，由于i >j ，j对应元素<v,所以a[l]与a[j]交换

5，返回j（pivot所在的index）

public class QuickSort2Way{
    //定义交换元素的方法
    private static void swap(arr[i],arr[j]){
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //双路快速排序的partition
    //将数组分为>=v和<=v两部分并返回pivot所对应的index，
    private static int partion(Comparable[] arr,int l,int r){
        //随机在arr[l..r]的范围中，选择一个index对应的数值作为标定点pivot，避免arr[l]就是最小值
        swap(arr[l],arr[(int)(Math.random()*(r-l+1)+l)]);
        //把v设置为最左端的元素
        Comparable v = arr[l];
        
        //为了把数组分为arr[l+1...i)<=v和arr(j...r]>=v两部分
        int i = l+1,j = r;
        while(true){
            //这里的边界不能挂等号
            while(i <= r && arr[i].compareTo(v) < 0)
                i++;  
            while(j >= l+1 && arr[j].compareTo(v) > 0 )
                j--;
            if(i>j)  //如果i超过了j的循环结束
                break; 
            swap(arr[i],arr[j]); // i，j都不移动了，证明a[i]>=v;a[j]<=v，就交换i,j对应两个元素
            i++;                 //交换后，i，j继续移动
            j--;
        }
        swap(arr[l],arr[j]);     //全部循环结束后，由于j已经小于i，j对应的是<v的元素，因此
        return j;
    }
    //递归使用快速排序，对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr,int l,int r){
        
        // 对于小规模数组, 使用插入排序
        if( r - l <= 15 ){
            InsertionSort.sort(arr, l, r);
            return;
        }
        
        //传入数组，左边界和右边界
        int p = partition(arr,l,r); //p为pivot左边<=v;右边>=v
        sort(arr,l,p-1); //继续递归调用直到将数组分为一个元素，则返回它自身
        sort(arr,p+1,r);
    }
    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr,0,n-1);
    }
}

Python代码

import random

def QuickSort2Way(arr):
    n = len(arr)
    QuickSortHealper(arr,0,n-1)
    return arr

def QuickSortHealper(arr,l,r):
    if l<r: #没写这个一直报bug
        p = partition(arr, l, r)
        QuickSortHealper(arr, l, p - 1)
        QuickSortHealper(arr, p + 1, r)


def partition(arr,l,r):
    rand = randint(l,r)  # 优化，随机取标定点，以解决近乎有序的列表
    arr[l], arr[rand] = arr[rand], arr[l]

    #设置两个指针l和r
    i = l+1
    j = r
    #设置pivotvalue
    v = arr[l]

    while True:
        while(arr[i]<arr[l] and i<=r): #当arr[i]>=v时停止前进
            i+=1
        while(arr[j]>arr[l] and j>=l+1):
            j-=1
        if(i>j):
            break
        else:
            # i，j都停止前进时，进行交换
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    #跳出循环后
    arr[l],arr[j]=arr[j],arr[l]
    return j

三路快排

思路：把数组分为arr[l+1…lt]<v; arr[lt+1…i) == v; arr[gt…r]>v三部分。

此时不需要partition函数。直接在sort函数中分情况讨论，后进行递归调用。

1，先随机选取一个index，并将其对应的元素于arr[l]进行交换，使其成为v

2，由于是闭区间，因此设 lt 初始值为l；gt的初始值为r+1。即开始时arr[l+1…lt]和arr[gt…r]中不存在元素。

3，开始while循环,循环条件是 i<gt 。==v的数组范围没有和>v的数组范围对撞。

4，在while循环中，如果arr[i]<v，则与（arr[lt+1…i)==v数组左边界的）arr[lt+1]进行交换，由于换过来的元素等于v，因此i直接向前移动；（且arr[l+1…lt] <v 的数组范围扩容）lt+1对应的是 <v 的元素因此lt需要向前移动一个位置。如果arr[i]>v, 则直接与arr[gt-1]进行交换，此时gt-1对应的是 >v 的元素，因此gt需要向前移动一位，但是由于交换过来的元素是未知的所以 i 不能向前移动。如果arr[i] == v 则 i 直接向前移动。

因为i是紧挨左边界的所以左边界交换来的元素已知，而右边界交换来的元素未知。

5,最后进行arr[l]与(arr[l+1…lt]<v的右边界)arr[lt]的交换。

6，最后进行sort(arr, l, lt-1)和sort(arr, gt, r)的递归调用。

LeetCode真题—75.Sort Colors

Sort Colors

Medium

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1 2	Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

本题：只有三个元素0，1，2三个元素。适合使用三路快排。arr[i] ==0排到左边，arr[i]==2排到右边，最后中间剩下的是1

class Solution {
    public void sortColors(int[] nums) {
       int l = -1, r = nums.length , i = 0;
        while (i < r) {
            if (nums[i] == 0) {
                int tmp = nums[i] ;
                nums[i] = nums[l+1];
                nums[l+1] = tmp;
                l++;
            }
            if (nums[i] == 2) {
            	int tmp = nums[i] ;
                nums[i] = nums[r-1];
                nums[r-1] = tmp;
                r--;
                i--; //由与交换过来的元素未知也许还是2，所以i还要检查一遍
            }
            i++;
        }
}

Python版本

def sortColors(nums):
    l,r,i = -1,len(nums),0
    while(i<r):
        if nums[i] ==0:
            nums[i],nums[l+1]=nums[l+1],nums[i]
            l+=1
        if nums[i] ==2:
            nums[i],nums[r-1]=nums[r-1],nums[i]
            r-=1
            i-=1
        i+=1
    return nums

MyNote

Quick Sort快速排序