算法课件全121301ADA07分治法快速排序
41页1、2019/6/21,2,2012-2013-01 Design and Analysis of Algorithm SCUN,Review of last class,Divide and Conquer technique Master theorem The merge sort algorithm and its best-case, worst-case and average-case analysis,Divide And Conquer (II),Chapter 4,Application to sorting problem Quick sort,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Master the idea of quick sort algorithm Master the best-case, worst-case and average-case an
2、alysis of quick sort algorithm Master the difference between merge sort and quick sort,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,Quicksort,Another sort algorithm example to reveal the essence of divide-and-conquer technique Its idea can be described as follows: Divide: Partition the array Apr into two sub arrays Apq and Aq+1r Invariant: All elements in Apq are less than all elements in Aq+1r Conquer: Sort the two sub arrays recursively Merge: Unlike merge sort, no combining
3、step, two sub arrays form an already-sorted array,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Quicksort Algorithm,ALGORITHM QuickSort(A, l, r) /Sorts a subarray by quicksort /Input: A subarray Alr of A0n-1, defined by its / left and right indices l and r /Output: Subarray Alr sorted in nondecreasing order if l r s Partition(A, l, r) /s is a split position QuickSort(A, l, s-1) QuickSort(A, s+1, r) end if,2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Clearly, al
4、l the action takes place in the divide step should be the followings: Select a pivot and rearranges the array in place End result: Two sub arrays been separated by the pivot The elements in one sub array are smaller than the pivot The elements in another are larger than the pivot Returns the index of the “pivot” element separating the two sub arrays How do you suppose we implement this?,Partition,2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Partition In Words,Given an array A0,
《算法课件全121301ADA07分治法快速排序》由会员E****分享,可在线阅读,更多相关《算法课件全121301ADA07分治法快速排序》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-05-07 48页
2024-05-07 41页
2024-05-07 36页
2024-05-07 33页
2024-05-07 43页
2024-05-07 30页
2024-05-07 27页
2024-05-07 31页
2024-05-07 44页
2024-05-07 39页