快速排序及其优化

快速排序是不稳定的排序方法，原因在于pivot元素移位的时候可能会造成相等元素之间位置发生变化。

快排的时间复杂度是O(nlogn)，最差情况时间复杂度是O(n^2)

一般语言内置的排序函数都是通过快速排序实现的，其中js的sort函数就是快速排序和插入排序实现的。

原始的快速排序算法(双路快排)

    // 升序排序
    void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                    j--;  
                if(i < j) 
                    s[i++] = s[j];
                
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                    i++;  
                if(i < j) 
                    s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用 
            quick_sort(s, i + 1, r);
        }
    }

插入排序的优化

因为当数组规模较小时采用插入排序的效率高于快速排序，尤其是当数组是经过快速排序处理之后，所以可以在快排时设置一个阈值，当分治得到的数组长度小于该阈值时使用插入排序，这样可以有一定的优化。

随机选取pivot

三数取中法进行优化

如果原始的数列近似一个排好的升序数列或者降序数列，再用原始的快排对它进行升序排序时，就会出现性能问题，因为每次选择的pivot都是第一个数，分治的时候分得的两个子数组极不平衡，此时的时间复杂度是n的平方。所以需要进行优化，优化的方法就是三数取中法，取arr[left], arr[mid],arr[right]三个数的中位数作为pivot来进行快排。

当然，三数取中的方法还有很多种，也不一定仅仅是对三个数取中

    // 优化后的快排比原始的多一个三数取中的过程
    void dealPivot(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if (arr[left] > arr[mid]) {
            swap(arr, left, mid);
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[right] < arr[mid]) {
            swap(arr, right, mid);
        }
        swap(arr, left, mid);
        // 将三个数的中位数放置到左边的位置作为pivot
    }

三路快排优化

虽然三数取中可以优化数组基本排序好的情况，但是对于出现很多相同数据的数列，还是无法优化，譬如一个数列全是由1组成的，对这个数列进行排序时时间复杂度就是n的平方，因为原始的快排对于大量重复的数据束手无策，这时就需要进行三路快排，在遍历的过程中把与pivot相同的数收集在数组的两侧，在pivot放置到正确的位置后再将数组两侧收集好的这些相同的数放在pivot的两边，再对除了pivot及相同数据以外的数组进行分治快排。当然在进行三路快排的同时还可以继续使用三数取中，同时优化。

具体过程：在处理过程中，会有两个步骤

第一步，在划分过程中，把与key相等元素放入数组的两端

第二步，划分结束后，把与key相等的元素移到枢轴周围

    void QSort(int arr[],int low,int high)
    {
        // high,low作为移动的游标，first,last则是保存左右节点，用于分治
        int first = low;
        int last = high;

        // 这是用来记录与pivot相等的数据的游标
        int left = low;
        int right = high;

        // 用来记录聚集在两端的和pivot相等的数据的数量
        int leftLen = 0;
        int rightLen = 0;
        // 插入排序的优化
        if (high - low + 1 < 10)
        {
            InsertSort(arr,low,high);
            return;
        }
        
        //一次分割
        int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴
            
        while(low < high)
        {
            while(high > low && arr[high] >= key)
            {
                if (arr[high] == key)//处理相等元素
                {
                    swap(arr[right],arr[high]);
                    right--;
                    rightLen++;
                }
                high--;
            }
            while(high > low && arr[low] <= key)
            {
                if (arr[low] == key)
                {
                    swap(arr[left],arr[low]);
                    left++;
                    leftLen++;
                }
                low++;
            }
            if(low < high) {
                swap(arr[low], arr[high]);
            }
        }
        arr[low] = key;
    
        //一次快排结束
        //把与枢轴key相同的元素移到枢轴最终位置周围
        int i = low - 1;
        int j = first;
        // 如果arr[i] == key了说明右边的数都已经和pivot相同了，没必要再继续交换下去了，继续的交换只是无用功
        while(j < left && arr[i] != key)
        {
            swap(arr[i],arr[j]);
            i--;
            j++;
        }
        i = low + 1;
        j = last;
        while(j > right && arr[i] != key)
        {
            swap(arr[i],arr[j]);
            i++;
            j--;
        }
        // leftLen和rightLen的使用地方
        QSort(arr,first,low - 1 - leftLen);
        QSort(arr,low + 1 + rightLen,last);
    }