原理
快速排序（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);
}
