【数据结构】排序--快速排序

目录

一 概念

二 快速排序的实现

1. hoare版本

(1)代码实现

(2)单趟排序图解

(3) 递归实现图解

(4)细节控制

(5)时间复杂度

(6)三数取中优化

2 挖坑法

(1)代码实现

(2)单趟图解 

3 前后指针法 

(1) 代码实现 

(2) 单趟图解

​4 优化子区间 

5 非递归快速排序

​ 三 快速排序的特性总结

---

一 概念

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

二 快速排序的实现

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像

1. hoare版本

(1)代码实现

#include<stdio.h>
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int PartSort1(int* a, int left, int right)
{int keyi = left;while (left < right){//找小while (left < right && a[right] >= a[keyi]){right--;}//找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int key = PartSort1(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
int main()
{int arr[] = {6,1,2,7,9,3,4,5,10,8};QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

(2)单趟排序图解

我们看看单趟排序怎么排的

 

(3) 递归实现图解

再来看看递归怎么实现的

 

(4)细节控制

对细节控制上 我要做一下解释

 那这里相遇位置一定比a[keyi]小呢?  右边先走导致的

(5)时间复杂度

我们来算一下快速排序的时间复杂度(需要对二叉树的基本性质熟悉)

 

(6)三数取中优化

那针对有序 的情况 我们可以采取三数取中的方式解决

#include<stdio.h>
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else// a[left] > a[mid]{if (a[left] < a[right]){return left;}else if (a[mid] > a[right]){return mid;}else{return right;}}
}int PartSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[midi], &a[left]);int keyi = left;while (left < right){//找小while (left < right && a[right] >= a[keyi]){right--;}//找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int key = PartSort1(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
int main()
{int arr[] = {6,1,2,7,9,3,4,5,10,8};QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

 2 挖坑法

  (1)代码实现

#include<stdio.h>
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else// a[left] > a[mid]{if (a[left] < a[right]){return left;}else if (a[mid] > a[right]){return mid;}else{return right;}}
}int PartSort2(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];//保存key值以后 左边形成第一个坑位int hole = left;while (left < right){//右边先走，找小，填到左边的坑，右边形成新的坑位if (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;//左边再走，找大，填到右边的坑，左边形成新的坑位if (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int key = PartSort2(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
int main()
{int arr[] = {6,1,2,7,9,3,4,5,10,8};QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

(2)单趟图解 

3 前后指针法 

(1) 代码实现 

int PartSort3(int* a, int left, int right)
{int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int key = PartSort3(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
int main()
{int arr[] = {6,1,2,7,9,3,4,5,10,8};QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

(2) 单趟图解

4 优化子区间 

递归到小的子区间时, 不在递归分割排序,可以考虑使用插入排序

因为区间比较小的时候节点数开的很多  特别是最后一层 节点数占了整个数大致百分之五十

 

int PartSort(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}if ((end - begin + 1) > 10){int keyi = PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}else{//插入排序InsertSort(a + begin, end - begin + 1);}
}

5 非递归快速排序

需要有对栈的基础  不会的可以看前面的博客

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef struct STList
{int* a;int size;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->size = ps->capacity = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}
void STPush(ST* ps, int x)
{assert(ps);if (ps->size == ps->capacity){int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;
}void STPop(ST* ps)
{assert(ps);assert(ps->size > 0);ps->size--;
}bool STEmpty(ST* ps)
{assert(ps);return ps->size == 0;
}int STTop(ST* ps)
{assert(ps);assert(ps->size > 0);return ps->a[ps->size - 1];
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else// a[left] > a[mid]{if (a[left] < a[right]){return left;}else if (a[mid] > a[right]){return mid;}else{return right;}}
}int PartSort(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);return prev;
}void QuickSortNonR(int* a, int begin, int end)
{ST st;//创建一个栈 STInit(&st);//初始化STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = PartSort(a, left, right);// [lefy,keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1){STPush(&st, keyi - 1);STPush(&st, left);}}STDestroy(&st);
}int main()
{int arr[] = {6,1,2,7,9,3,4,5,10,8};QuickSortNonR(arr, 0, (sizeof(arr) / sizeof(int)) - 1);for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

 三 快速排序的特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

本节难度还是不低, 但是我觉得大家根据图解和代码慢慢吃透还是不难的,这节我画的图解很多, 对重点和难点进行了很细致的划分和讲解, 希望大家可以窥探到快速排序的妙处

继续加油!