快速排序思想_快速排序能排三元组偏序吗

快速排序是一个基础算法，记得以前看一篇文章，里面说作为一个程序员，基础排序，通用算法，数据结构应该是随手拈来，一气呵成。也有人说在社招面试中这些都是默认你都会，一般都不会问，其实不然，如果随口问问的话，会有很多同学讲不清楚，更有甚者连原理都不知道的，这里贴出快排的思想以及我见过的一些实现方式，也告诫自己基础就得烂熟于胸，时常温习，叫温故知新，如有错误之处也请指正。

一、快排思想：快排是采用分治递归的思想去进行排序数据

1、分治：从待排序数组中选取一个pivot（支点），遍历其他数据与pivot比较，大于pivot的放一边，小于pivot放在另一边，将数组分成了2个部分

      1，3，4，2，8，9，10，16，11

2、递归：对这二个部分递归的进行相同的第1步分治操作

3、结束：当待排序子数组大小小于等于1时，递归返回，最终数组全部有序

二、有几种方法进行第一步分治的操作，这是影响快排算法的时间复杂度的地方

1、选取第一个元素作为pivot

方式一：2个位置点从左右两端开始往中间进行（最常介绍）

int partion1(int a[], int left, int right)
{
    int pivot = a[left];
    int i = left;
    int j = right;
    while (i<j){
        while(i<j && a[j]>=pivot) j--;
        while(i<j && a[i]<=pivot) i++;
        if (i < j){
            swap(&a[i],&a[j]);
        }
    }
    swap(&a[left], &a[j]);
    return j;
}

方式二：2个位置点，从开始端同时往后进行

int partion2(int a[], int left, int right)
{
    int pivot = a[left];
    int i = left;
    for (int j = i+1; j <= right; j++) {
        if (a[j] < pivot) {
            i = i + 1;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[left], &a[i]);
    return i;
}

仔细看看这2种方式，个人觉得第二种方式2个位置都往后面遍历，一个for就搞定，不容易写错，边界控制较简洁。

2、三元组法选择pivot

主程原理：当数组元素个数较少时，使用插入排序，元素较多时（大于等于3），才使用快速排序，这也是三元组法的命名由来。

快排选取pivot原理：由于元素个数大于3，故比较左，中，右三个元素，将他们按顺序调整好，然后将中间元素（3个元素值的中值）调换到最右边-1的位置，并这个位置的元素作为pivot

将这3个元素这么放置的好处是非常有利于游走位置的边界控制，看代码：

int median3(int a[], int left, int right)
{

    //调换3个元素到相应位置
    int mid = left + (right - left) / 2;
    if (a[left] > a[mid]) swap(&a[left], &a[mid]);
    if (a[mid] > a[right]) swap(&a[mid], &a[right]);
    if (a[left] > a[mid]) swap(&a[left], &a[mid]);
    swap(&a[mid], &a[right - 1]);
    return a[right-1];
}
int partion3(int a[], int left, int right)
{
    int pivot = median3(a, left, right);
    int i = left;//左边边界点，一定小于等于pivot
    int j = right - 1;//右边边界点，一定大于等于pivot
    while (i < j)
    {
        while (a[++i] < pivot) {}//一开始就++走位置也不会越界最右边
        while (a[--j] > pivot) {}//一开始就--走位置也不会越界最左边
        if (i < j)
        {
            swap(&a[i], &a[j]);
        }
        else break;
    }
    swap(&a[i],&a[right-1]);
    return i;
}

与最开始的那种方式比较，少写一些判断，更精炼，不过要仔细想想才行。