简介:
创新互联公司于2013年开始,是专业互联网技术服务公司,拥有项目成都网站制作、成都网站设计、外贸营销网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元婺源做网站,已为上家服务,为婺源各地企业和个人服务,联系电话:028-86922220快速排序是个“综合素质”较好的排序,比如javaSE中的Arrays.sort()实现原理,也是用的是快速排序思想。下面就看看一种快速排序的递归实现方式
要点:
1,分治思想,把问题划分成可以与本问题处理方式相同的若干子问题,使用递归来解决。
如排序问题,可以
(1)把原数组A[p,q](原问题)划分成三个部分 :较小部分A[p,m-1] 中间元素x=A[m] 较大部分A[m+1,q]
这样把部分当做一个整体看待是有序的A[p,m-1] < A[m] < A[m+1,q]
(2)同理,无论是较小部分还是较大部分都可以继续按(1)操作继续划分得更细,直到每个部分的元素
被划分得只有单个元素,原数组之间每个元素就有序了
特征:
1,快速排序是原址排序,子问题解决的时候,不需要整体再次合并排序结果
2,递归调用在非常的数据的时候可能会发生栈溢出(递归深度太大)
难点:
如何划分成相对有序的三个部分?
思路:
(1)在原数组的某个好识别的位置取出一个数做中间元素x(部分2)。(一般取数组末元素,如x=A[q])
(2)采取一个位置变量i来左划分界线,保证i上和i的左边都是小部分元素(部分1)。
(i的初始位置应当在问题范围的前一个位置,因为此时还没开始划分)
(3)除了x元素,循环取出原数组中的每个元素A[j]与x做比较
遇到不大于中间元素x要收集到界线上:
原界线i右移一个,此时i指向的元素是不确定性质的元素,
不确定元素和已经遇到的确定的小部分元素A[j]交换位置。(不确定换确定)
遇到大于中间元素的,界线i不动,j继续向右扫描(i和j之间的定是大部分元素,部分3)
(4)让中间元素交换到真正位置。一遍循环后,可以分出 小部分 和 大部分,
此时只要在界线的右一个(即大部分中的某个元素)与中间元素交换即可让划分的三个部分满足排序关系。
图片描述:
代码描述:
void quicklySort(int *arr , int start , int last){
int mid;
if(start mid = partition(arr, start, last);//划分子问题 quicklySort(arr, start , mid-1);//解决左边部分 quicklySort(arr, mid+1, last);//解决右边部分 } } int
partition(int *arr, int start, int last){ int x = arr[last];//取本段数组最后一个元素,稍后使其成为划分好的中间元素 int i=0,j=0; i=start-1;//使用i来控制两个部分的分界,初始值在子问题范围的前一个 for(j=start;j<= last-1; j++){ if(arr[j]<= x){//如果j走过的值是属于较小部分 ++i;//较小部分分界线多收集一个空间 swap(arr[i],arr[j]);//把属于较小部分的值交换到这个空间(原址排序) } //如果是较大部分,让j继续向后滑行 } swap(arr[i+1],arr[last]);//把选择参照的值交换到小部分和大部分之间 return i+1;//返回划分好的中间位置 } 另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章名称:一种递归实现的快速排序精讲-创新互联
文章链接:http://njwzjz.com/article/cdscde.html