做网站需要哪些语言,wordpress个人,.net手机网站源码下载,wix建站是免费的吗目录
1. hoare法
方法与步骤
代码实现
2. 挖坑法
方法与步骤
代码实现
3. 前后指针法
方法与步骤
代码实现
4. 快速排序的缺点与优化
1.快速排序的缺点
2.快速排序的优化
① 三数取中法选 key
代码实现
② 小区间优化
代码实现
5. 快速排序的非递归实现
附录…
目录
1. hoare法
方法与步骤
代码实现
2. 挖坑法
方法与步骤
代码实现
3. 前后指针法
方法与步骤
代码实现
4. 快速排序的缺点与优化
1.快速排序的缺点
2.快速排序的优化
① 三数取中法选 key
代码实现
② 小区间优化
代码实现
5. 快速排序的非递归实现
附录完整源码
快速排序递归实现
快速排序非递归实现 快速排序是霍尔大佬在1962年提出的排序方法因其出色的排序效率使得它成为使用最广泛的排序算法。快速排序之所以敢叫做快速排序自然是有一定的道理今天我们就来看看快速排序是如何凌驾于其它算法之上的。
快速排序的基本思想是任取待排序数列中的一个数作为 key 值通过某种方法使得 key 的左边所有的数都比它小右边的数都比它大以 key 为中心将 key 左边的数列与右边的数列取出做同样的操作取 key 值分割左右区间直至所有的数都到了正确的位置。
上述所提到的某种方法可以有很多种例如hoare法、挖坑法、前后指针法。它们虽然做法不相同但做的都是同一件事——分割出 key 的左右区间左边的数比 key 小右边的数比 key 大。
我们首先来看看霍尔大佬所用的方法——hoare法。
1. hoare法
方法与步骤
以数列 61279345810 为例
1.取最左边为 key 分别有 left 和 right 指向数列的最左端与最右端 2. right 先走找到比 key 小的数就停下来 3. left 开始走找到比 key 大的数就停下来 4. 交换 left 与 right 所在位置的数 5.重复上述操作right 找小left 找大进行交换 6. right 继续找小 7. left 继续找大若与 right 就停下来
8.交换二者相遇位置与 key 处的值 此时一趟排序就完成了此时的数列有两个特点
1. key 所指向的值6已经到了正确的位置
2. key 左边的数字都比 key 要小右边的都比 key 要大
接下来就是递归的过程了分别对左右区间进行同样的操作 代码实现
知道了详解步骤用代码来实现并不困难但是有很多很多的细节需要注意。这里的代码未经优化当前的代码有几种极端的情况不能适应
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}void QuickSort(int* a, int begin, int end)
{//数列只有一个数或无数列则返回if (begin end){return;}int left begin;int right end;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]);QuickSort(a, begin, left - 1);QuickSort(a, left 1, end);
}
2. 挖坑法
挖坑法相比于hoare法思路上更为简单易懂。
方法与步骤
还是以同样的数列 61279345810 为例 1. 先将第一个数存放到 key 中形成一个坑位分别有 left 和 right 指向数列的最左端与最右端 2. right 先走找到比 key 小的数将该数丢到坑里同时又形成了一个新的坑 3. left 开始走找到比 key 大的数将该数丢到坑里同时形成一个新的坑 4. right继续找小进行重复的操作 5. left 找大
6. right 找小
7. left 找大
8.若二者相遇就停下来将 key 值放入坑 至此一趟排序已经完成我们发现此时的数列与hoare具有相同的特点
1. key 所指向的值6已经到了正确的位置
2. key 左边的数字都比 key 要小右边的都比 key 要大
挖坑法、hoare、前后指针法完成一趟排序后都具有相同的特点所以不同版本的快速排序不一样的只有单趟排序的实现总体思路都是相同的。
代码实现
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int left begin;int right end;int key a[left];int hole left;//坑位while (left right){while (left right a[right] key){right--;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;QuickSort(a, begin, hole - 1);QuickSort(a, hole 1, end);
}
3. 前后指针法
方法与步骤
以同样的数列为例
1. 取第一个值为 key 有 prev 和 cur 分别指向数列开头和 prev 的下一个数
2. cur 先走找到比 key 小的数就停下来
3. prev 交换 prev 与 cur 位置的数前两次无需交换因为自己与自己换没有意义
4. 重复此步骤
5. 直到 cur 走完整个数列交换 prev 与 key 处的值 至此第一趟排序就结束了又是与前两种方法相同的结果
代码实现
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int prev begin;int cur prev 1;int keyi begin;while (cur end){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[keyi], a[prev]);keyi prev;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
4. 快速排序的缺点与优化
1.快速排序的缺点
我们用三种方式实现了快速排序其实这三种方式并无明显的优劣之分。但是我们前面设计的快速排序其实是有两个缺点的
1.在最坏情况下它的的效率极慢
2.在数据量太大时会造成栈溢出。
那么什么情况是最坏情况呢答案是当数据本身就是有序的时候无论是逆序还是顺序。在最坏情况下每次我们的 key 值都是最大或者最小这样就会使 key 与数列的每个数都比较一次它的时间复杂度为 O(n^2);
为什么会发生栈溢出呢因为我们的快速排序是利用递归实现的有递归调用就要建立函数栈帧并且随着递归的深度越深所要建立的函数栈帧的消耗就越大 。如这幅图所示 2.快速排序的优化
① 三数取中法选 key
为了应对最坏情况会出现时间复杂度为 O(N^2) 的情况有人提出了三数取中的方法。
旧方法中我们每次选 key 都是数列的第一个元素。三数取中的做法是分别取数列的第一个元素、最后一个元素和最中间的元素选出三个数中不是最大也不是最小的那个数当作 key 值。
有了三数取中之前的最坏情况立马变成了最好情况。
代码实现
由于hoare法、挖坑法、前后指针法最终的效果都相同且效率差异很小所以就任意选取一个为例其余两者都类似。
//三数取中的函数
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}else // a[begin] a[mid]{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}
//hoare法
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int mid GetMidIndex(a, begin, end);Swap(a[mid], a[begin]);int left begin;int right end;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]);QuickSort(a, begin, left - 1);QuickSort(a, left 1, end);
}② 小区间优化
随着递归的调用越深入此时有个很大的缺点就是函数栈帧的消耗很大。但是同时又有一个好处就是越往下数列就越接近有序且此时每个小区间的数据个数特别少。
那么有什么办法可以取其长处避其短处呢不知道你是否还记得插入排序的特点——数据越接近有序效率就越高。并且在数据量极少的情况下时间复杂度为 O(N^2) 的插入排序与时间复杂度为 O(N*log N) 的快速排序基本没有什么区别。所以我们干脆就在排序数据量少的数列时采用插入排序代替。
代码实现
//三数取中的函数
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}else // a[begin] a[mid]{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}//插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp) //大于tmp往后挪一个{a[end 1] a[end];end--;}else{break;}}a[end 1] tmp; //把tmp插入空隙}
}//hoare法
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}if ((end - begin 1) 15){// 小区间用直接插入替代减少递归调用次数InsertSort(abegin, end - begin 1);}else{int mid GetMidIndex(a, begin, end);Swap(a[mid], a[begin]);int left begin;int right end;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]);QuickSort(a, begin, left - 1);QuickSort(a, left 1, end);}
}两外两种方法的代码实现已打包完成可在文末直接取用。
5. 快速排序的非递归实现
快速排序的非递归思路与递归相差无几唯一不同的是非递归用栈或队列模拟函数递归建立栈帧的过程。
void QuickSortNonR(int* a, int begin, int end)
{Stack st;StackInit(st);StackPush(st, begin);StackPush(st, end);while (!StackEmpty(st)){int right StackTop(st);StackPop(st);int left StackTop(st);StackPop(st);int keyi PartSort1(a, left, right);//三种方法任选其一//int keyi PartSort2(a, left, right);//int keyi PartSort3(a, left, right);if (keyi 1 right){StackPush(st, keyi 1);StackPush(st, right);}if (left keyi - 1){StackPush(st, left);StackPush(st, keyi - 1);}}StackDestroy(st);
}
附录完整源码
快速排序递归实现
//交换函数
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}//三数取中
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}else // a[begin] a[mid]{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}//插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp) //大于tmp往后挪一个{a[end 1] a[end];end--;}else{break;}}a[end 1] tmp; //把tmp插入空隙}
}// Hoare法
int PartSort1(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int left begin, right end;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[left], a[keyi]);keyi left;return keyi;
}// 挖坑法
int PartSort2(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int left begin, right end;int key a[left];int hole left;while (left right){while (left right a[right] key){--right;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}//前后指针法
int PartSort3(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int keyi begin;int prev begin, cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}//快速排序递归
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}if ((end - begin 1) 15){// 小区间用直接插入替代减少递归调用次数InsertSort(a begin, end - begin 1);}else{int keyi PartSort1(a, begin, end);//int keyi PartSort2(a, begin, end);//int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}
}
快速排序非递归实现
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{STDataType* a; //动态开辟数组int capacity; //记录栈的容量大小int top; //记录栈顶的位置
}Stack;//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);// Hoare法
int PartSort1(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int left begin, right end;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[left], a[keyi]);keyi left;return keyi;
}// 挖坑法
int PartSort2(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int left begin, right end;int key a[left];int hole left;while (left right){while (left right a[right] key){--right;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}int PartSort3(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int keyi begin;int prev begin, cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}
void QuickSortNonR(int* a, int begin, int end)
{Stack st;StackInit(st);StackPush(st, begin);StackPush(st, end);while (!StackEmpty(st)){int right StackTop(st);StackPop(st);int left StackTop(st);StackPop(st);int keyi PartSort1(a, left, right);//三种方法任选其一//int keyi PartSort2(a, left, right);//int keyi PartSort3(a, left, right);if (keyi 1 right){StackPush(st, keyi 1);StackPush(st, right);}if (left keyi - 1){StackPush(st, left);StackPush(st, keyi - 1);}}StackDestroy(st);
}//栈的实现_函数定义void StackInit(Stack* ps)
{assert(ps);//初始化时可附初值也可置空ps-a NULL;ps-capacity 0;ps-top 0;
}void StackDestroy(Stack* ps)
{assert(ps);//若并未对ps-a申请内存则无需释放if (ps-capacity 0)return;//释放free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}void StackPush(Stack* ps,STDataType data)
{assert(ps);//若容量大小等于数据个数则说明栈已满需扩容if (ps-capacity ps-top){//若为第一次扩容则大小为4否则每次扩大2倍int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}//压栈ps-a[ps-top] data;ps-top;
}void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//出栈ps-top--;
}STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//返回栈顶的数据return ps-a[ps-top - 1];
}bool StackEmpty(Stack* ps)
{assert(ps);//返回topreturn ps-top 0;
}
