自助建站软件公司,邮箱163企业邮箱,asp企业营销型网站建设,济南做网站的公司哪家好【八大经典排序算法】快速排序 一、概述二、思路实现2.1 hoare版本2.2 挖坑法2.3 前后指针版本 三、优化3.1 三数取中3.1.1 最终代码3.1.2 快速排序的特性总结 四、非递归实现快排 一、概述
说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代#xff0c;计算机科学… 【八大经典排序算法】快速排序 一、概述二、思路实现2.1 hoare版本2.2 挖坑法2.3 前后指针版本 三、优化3.1 三数取中3.1.1 最终代码3.1.2 快速排序的特性总结 四、非递归实现快排 一、概述
说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代计算机科学家们开始研究如何对数据进行排序以提高计算机程序的效率。当时常用的排序算法包括冒泡排序、插入排序和选择排序等。
然而这些算法的效率都相对较低特别是在处理大量数据时。于是人们开始寻找更快速的排序算法。Tony Hoare 在研究中发现了一种基于分治思想的排序方法即快速排序。
二、思路实现
快速排序的思想是任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
代码如下
// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int* a, int begin, int end)
{if (begin end)return;// 按照基准值对数组的 [left, right)区间中的元素进行划分int keyi PartSort(a, begin, end);//分成[begin,keyi-1] keyi [keyi1,end]// 递归排[left, div)QuickSort(a, begin, keyi - 1);// 递归排[div1, right)QuickSort(a, keyi 1, end);
}上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像接下来只需分析如何按照基准值来对区间中数据进行划分的方式即可。 待排序集合分割时将区间按照基准值划分为左右两半部分的常见方式有以下3种。
2.1 hoare版本
思路
选择一个基准元素key可以是最左边也可以是最右边。定义两个指针一个指向数组的第一个元素左指针一个指向数组的最后一个元素右指针。需要注意的是若选择最左边的数据作为key则需要right先走若选择最右边的数据作为key则需要left先走移动左指针,直到找到一个大于等于基准元素key的元素移动右指针直到找到一个小于等于基准元素key的元素。之后交换交换左右指针所指向的元素。然后不断重复上述步骤直到左指针大于右指针最后将基准元素与右指针所指向的元素交换位置此时基准元素位于正确的位置。此时左边元素key右边元素key。 Tips博主在这里解释一下为什么“若选择最左边的数据作为key则需要right先走若选择最右边的数据作为key则需要left先走”后续其他方法同理。 ① :左边作key右边先走保证了相遇位置的值小于key或就是key的位置。 ②右边作key左边先走保证了相遇位置的值大于key或就是key的位置。 以①为例L和R相遇无非就两种情况L遇RR遇L。 情况一L遇R。在R停下来后L还在走。由于R先走R停下来的位置一定小于Key。相遇位置为R停下来的位置一定比key小。 情况二R遇L。再相遇的这一轮L就不动了R在移动。相遇位置即为L的位置。而L的位置就是key的位置 or 已经交换过一些轮次了此时相遇位置一定比key小。 【动画演示】 代码如下 //[left, right]--采用左闭右闭
int PartSort(int* a, int left, int right)
{int keyi left;while (left right){//找到右边比key小的数while (left right a[right] a[keyi]){right--;}//找到左边比key大的数while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}2.2 挖坑法
思路
.选出一个数据一般是最左边或是最右边的存放在key变量中同时该数据位置形成一个坑。还是左右指针left和rightleft从左向右走right从右向左走。若在最左边挖坑则需要R先走若在最右边挖坑则需要L先走移动右指针找到第一个比key小的数并填到坑位此时右指针所在位置变成新的坑。然后移动左指针找到第一个比key大的数并填到坑位此时左指针所在位置变成新的坑。然后和hoare版本一样不断重复上述步骤即可 【动画演示】 代码如下
//挖坑法
int PartSort(int* a, int left, int right)
{int key a[left];int hole left;while (left right){//找到右边比key小的值while (left right a[right] key){right--;}a[hole] a[right];hole right;//左边比key大的值while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}2.3 前后指针版本
思路
选出一个key一般是最左边或是最右边的。起始时prev指针指向序列开头cur指针指向prev1。若cur指向的内容小于key则prev先向后移动一位然后交换prev和cur指针指向的内容然后cur指针若cur指向的内容大于key则cur指针直接。如此进行下去直到cur到达end位置此时将key和prev指针指向的内容交换即可。 【动画演示】 代码如下
//前后指针法
int PartSort(int* a, int left, int right)
{int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}三、优化
虽然已经可以解决问题了但还有一个问题 当选取的key每次都是中位数时效率最好时间复杂度为O(N*logN)但当数组有序时变成最坏时间复杂度变为O(N^2) 对于上述情况这里有两种优化方式
三数取中法选key递归到小的子区间时可以考虑使用插入排序
3.1 三数取中
这里博主给出一直最简单的方法
int GetMidIndix(int* a, int left, int right)
{int mid left (right - left) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[mid] a[right])return right;elsereturn left;}else//a[left]a[mid]{if (a[mid] a[right])return mid;else if (a[mid] a[right])return right;elsereturn left;}
}3.1.1 最终代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}int GetMidIndix(int* a, int left, int right)
{int mid left (right - left) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[mid] a[right])return right;elsereturn left;}else//a[left]a[mid]{if (a[mid] a[right])return mid;else if (a[mid] a[right])return right;elsereturn left;}
}// hoare
// [left, right]
//int PartSort(int* a, int left, int right)
//{
// int midi GetMidIndix(a, left, right);
// Swap(a[left], a[midi]);
//
// int keyi left;
// while (left right)
// {
// //找到右边比key小的数
// while (left right a[right] a[keyi])
// {
// right--;
// }
//
// //找到左边比key大的数
// while (left right a[left] a[keyi])
// {
// left;
// }
// Swap(a[left], a[right]);
// }
// Swap(a[keyi], a[left]);
// return left;
//}//挖坑法
//int PartSort(int* a, int left, int right)
//{
// int midi GetMidIndix(a, left, right);
// Swap(a[left], a[midi]);
//
// int key a[left];
// int hole left;
// while (left right)
// {
// //找到右边比key小的值
// while (left right a[right] key)
// {
// right--;
// }
// a[hole] a[right];
// hole right;
//
// //左边比key大的值
// while (left right a[left] key)
// {
// left;
// }
// a[hole] a[left];
// hole left;
// }
// a[hole] key;
// return hole;
//}//前后指针法
int PartSort(int* a, int left, int right)
{int midi GetMidIndix(a, left, right);Swap(a[left], a[midi]);int keyi left;int prev left;int cur left 1;while (cur right){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;int keyi PartSort(a, begin, end);//分成[begin,keyi-1] keyi [keyi1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}3.1.2 快速排序的特性总结
时间复杂度O(N*logN) 空间复杂度O(logN)稳定性不稳定 四、非递归实现快排
思路
定义一个栈然后将待排序的数组的起始索引和结束索引入栈。通过前面将的三种分割区间的方法将数组的起始索引和结束索引之间的元素分成两部分左边部分小于等于基准元素右边部分大于等于基准元素。由于非递归实现时我们是通过从栈中两两取出维护待排序数组的下标所以接下来就是如果左边部分的长度大于1则将左边部分的起始索引和结束索引入栈如果右边部分的长度大于1则将右边部分的起始索引和结束索引入栈。最后循环此操作直到栈为空。
代码如下
//前后指针法
int PartSort(int* a, int left, int right)
{int midi GetMidIndix(a, left, right);Swap(a[left], a[midi]);int keyi left;int prev left;int cur left 1;while (cur right){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)
{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);//[left,keyi-1] keyi [keyi1,right]if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}if (keyi - 1 left){STPush(st, keyi - 1);STPush(st, left);}}STDestroy(st);
}
