做救助流浪动物网站的产生背景,局域网视频网站建设,crm客户管理系统免费软件,购物网站开发小结目录
一 概念
二 快速排序的实现
1. hoare版本
(1)代码实现
(2)单趟排序图解
(3) 递归实现图解
(4)细节控制
(5)时间复杂度
(6)三数取中优化
2 挖坑法
(1)代码实现
(2)单趟图解
3 前后指针法
(1) 代码实现
(2) 单趟图解
4 优化子区间
5 非递归快速排序 …目录
一 概念
二 快速排序的实现
1. hoare版本
(1)代码实现
(2)单趟排序图解
(3) 递归实现图解
(4)细节控制
(5)时间复杂度
(6)三数取中优化
2 挖坑法
(1)代码实现
(2)单趟图解
3 前后指针法
(1) 代码实现
(2) 单趟图解
4 优化子区间
5 非递归快速排序
三 快速排序的特性总结 一 概念
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止
二 快速排序的实现
上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像
1. hoare版本
(1)代码实现 #includestdio.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)三数取中优化
那针对有序 的情况 我们可以采取三数取中的方式解决
#includestdio.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)代码实现 #includestdio.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 非递归快速排序
需要有对栈的基础 不会的可以看前面的博客
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.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 [keyi1, 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. 稳定性不稳定 本节难度还是不低, 但是我觉得大家根据图解和代码慢慢吃透还是不难的,这节我画的图解很多, 对重点和难点进行了很细致的划分和讲解, 希望大家可以窥探到快速排序的妙处
继续加油!
