数据结构-快速排序-单路快排、双路快排、三路快排

原理

快速排序（Quicksort）是对冒泡排序的一种改进。

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1路快排

• 取区间 [l+1 j] < v
  • 区间 [j+1 i-1] > v

• 一直遍历i 把取值放到对应的空间，最后把V和arr[j] 交换

  
  1路快排示意图

#pragma mark -- 单路快排

int quick_simple_pivot(int arr[], int l, int r) {
    
        int p = arr[l];
        int i = l + 1;
        int k ;
        int temp;
        for (k = l + 1; k <= r && i<=r; k++) {
            if (arr[k] > p) {
                
            }
            if (arr[k] < p) {
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
                i ++;
            }
        }
        arr[l] = arr[i - 1];
        arr[i - 1] = p;
   
        return i - 1;
    
}

void quick_simple_sortPai(int arr[], int l, int r) {
    if (l < r) {
        int p = quick_simple_pivot(arr, l, r);
        quick_simple_sortPai(arr, l, p - 1);
        quick_simple_sortPai(arr, p + 1, r);
        
    }
}
void quick_simple_sort(int arr[], int r) {
    quick_simple_sortPai(arr, 0, r - 1);
}

双路快排

当待排序数组是一个数值重复率非常高的序列时，容易产生最坏O(n^2)的时间复杂度。

产生左右子树不均衡

将小于v的部分放到指针i（i为遍历用指针）的左边，将大于v的部分都放到指针j的右边，延用随机选base的思路。等于v时使用交换的方式处理。

双路快排- 赋值

排序演示

原数据
5    6    3    4    7    8    9
  
取出第一个数据5 放到一边
然后从右往左找到一个比  5数据小的数  放到5的位置
4    6    3    4    7    8    9

然后从左往右找  找一个比5 大的数据   放到刚从右边取到的4的位置
4    6    3    6    7    8    9
从右往左找   找一个比5 小的数据  3   放到刚从左边取到的6的位置
4    3    3    6    7    8    9
此时两边往中间挤 数据全部找完， 然后把第一个去出的5 放到3的原位置
4    3    5    6    7    8    9
第一次排序完  后的数据

####二
5 左边的数据 按同样的原理进行排序
取出 4 放到一边
从右往左查找比4 小的数据
3    3
把4放到 原3的位置
3    4

这样原数据为
3    4    5    6    7    8    9

####三
然后取6右边的数据 同样的原理进行排序
比6小的数据没有
然后比较比6大的数据

没有 
 
然后比较 7 
然后比较  8

代码

#pragma mark --快速排序
void quick_sort(int a[], int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[I];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; // 从右向左找第一个小于x的数
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; // 从左向右找第一个大于x的数
            if(i < j)
                a[j--] = a[I];
        }
        a[i] = x;
        quick_sort(a, l, i-1); /* 递归调用 */
        quick_sort(a, i+1, r); /* 递归调用 */
    }
}

void quick_sortyuan(int *array, int length) {
    quick_sort(array, 0, length - 1);
}

双路快排- 交换

• 区间 [l + 1 i-1] < v
• 区间 [j r] > v j空间取 这个比较好
• 从左找到一个比 基准大的
• 从右找到一个比 基准小的
• 然后交换

• 当i > j时，比较完整个数组 然后把l 与i- 1交换

  
  双路快排- 交换

int quick_change(int *arr, int l, int r) {
    int p = arr[l];
    int i = l + 1;
    int j = r;
    int temp;
    while (l < r) {
        while (i <= r && arr[i] < p) {
            I++;
        }
        while (j >= l+ 1 && arr[j] > p) {
            j--;
        }
        if (i > j) {
            break;
        }else {
//            交换
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            I++;
            j--;
        }
    }
    temp = arr[i - 1];
    arr[i- 1] = p;
    arr[l] = temp;
    return i -1;
}
void quick_sort_change(int *arr, int l, int r) {
    if (l < r) {
        int point = quick_change(arr, l, r);
        quick_sort_change(arr, l, point - 1);
        quick_sort_change(arr, point + 1, r);
        
    }
}
void quick_sort_changeStart(int *arr, int length) {
    quick_sort_change(arr, 0, length - 1);
}

三路快排

将小于v的部分放到指针lt左边，将大于v的部分放到指针gt右边。考虑到v有重复值的情况，遇到等于v的情况，将i指针右移

思想：遍历i 然后对i进行区间分类。类似一路快排

三路快排-示意图

#pragma mark -- 三路快排
void swapArray(int *arr, int l, int r) {
    int temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
}
//r 为右侧 开区间  num = length
void threeQuick_sort (int *arr, int l, int r) {
    if (l >= r) {
        return;
    }
    
    int jt = r;
    int lt = l;
    int i = l + 1;
    int povnt = arr[l];
    while (i < jt) {
        if (arr[i] > povnt) {
            swapArray(arr, i, jt - 1);
            jt--;
        } else if (arr[i] < povnt) {
            swapArray(arr, i, lt + 1);
            lt++;
            i++;
        }else {
            i++;
        }
    }
    swapArray(arr, l, lt);
    threeQuick_sort(arr, l, lt);
    threeQuick_sort(arr, jt, r);
}

void three_Quick_start(int *arr, int r) {
    threeQuick_sort(arr, 0, r);
}