微页制作网站模板下载,动漫设计工作室网站建设公司,传媒网站如何设计,app界面怎么制作的目录
1.Hoare单趟排序思想
2.单趟排序代码
初次写的代码 运行结果
查找问题原因
尝试解决问题
初次修正后代码
运行结果 正确的单趟排序代码
3.将单趟排序嵌入
如何递归?
递归结束的条件
1.较容易分析的结束条件:leftright
2.以{2,1}为例分析另一个结束条件
完整…目录
1.Hoare单趟排序思想
2.单趟排序代码
初次写的代码 运行结果
查找问题原因
尝试解决问题
初次修正后代码
运行结果 正确的单趟排序代码
3.将单趟排序嵌入
如何递归?
递归结束的条件
1.较容易分析的结束条件:leftright
2.以{2,1}为例分析另一个结束条件
完整代码
运行结果 1.Hoare单趟排序思想
例如对于无序数组arr{6,1,2,7,9,3,4,5,10,8},排升序
① 选一个基准值(又叫关键值)key,一般来说key选arr[0](其实key也可以取其他值,下篇会详细介绍)
② 如果数组一共n个数,两个指针left和right分别从数组的左侧arr[0]和右侧arr[n-1]出发,其中right先走
③ left找到arr[left]比key小的就停止right需要找到arr[right]比key大的,之后arr[left]和arr[right]交换,left和right继续寻找,直到leftright或leftright退出
④ 最后将arr[key_i]和arr[left]交换,完成一次单趟排序
{6,1,2,7,9,3,4,5,10,8} -- {3,1,2,5,4,6,9,7,10,8}(比6小的都在6的左边.比6大的都在6的右边)
2.单趟排序代码
初次写的代码
//单趟快速排序
int key_i left;
while (left right)
{//由于key_ileft,因此right指针先走//右边找小while (arr[right] arr[key_i]){right--;}//左边找大while (arr[left] arr[key_i]){left;}Swap(arr[left], arr[right]);
}Swap(arr[key_i], arr[left]); 运行结果
实际上运行结果不正确,6左侧有9,9比6大 查找问题原因
可以在while (arr[right] arr[key_i])处下断点调试 发现问题:left0不符合要求
尝试解决问题
可在循环前让left1跳过arr[0] int key_i left;left;while (left right){//......}
执行结果:实际上运行结果不正确,6左侧有9,9比6大 尝试寻找原因
下断点调试, 上图说明:到目前为止都没有什么问题
执行到下图时,问题出现:leftright还没有退出! 因此要在两个内循环中都加入条件: leftright,确保不越界!
初次修正后代码
//单趟快速排序
int key_i left;
left;
while (left right)
{//由于key_ileft,因此right指针先走//右边找小while (left right arr[right] arr[key_i]){right--;}//左边找大while (left right arr[left] arr[key_i]){left;}Swap(arr[left], arr[right]);
}Swap(arr[key_i], arr[left]);
运行结果
没有问题了,与设想的结果相同 其实修正后的代码还有巨大的问题!!
对{1,2,3,4,5}排序,执行结果反而将升序数组的顺序打乱了,问题在哪里? 执行到Swap(arr[key_i], arr[left]);时,key_i0,left1,导致错误互换,应该将left删除
执行结果:没有问题了,与设想的结果相同 其实修正后的代码还有巨大的问题!!
对这个数组排序{6,1,2,7,9,3,4,5,10,6}会死循环 arr[right] arr[key_i] 和 arr[left] arr[key_i]时right没有变化,导致一直在while (leftright)里执行无法退出
改成while (left right arr[right] arr[key_i])和while (left right arr[left] arr[key_i])即可让left和right指针继续查找,而且避免了在while (leftright)执行前让left的情况 正确的单趟排序代码 //单趟快速排序int key_i left;while (left right){//由于key_ileft,因此right指针先走//右边找小while (left right arr[right] arr[key_i]){right--;}//左边找大while (left right arr[left] arr[key_i]){left;}Swap(arr[left], arr[right]);}Swap(arr[key_i], arr[left]);
3.将单趟排序嵌入
如何递归?
第一次单趟排序后的数组{3,1,2,5,4,6,9,7,10,8},接下来分别对6的左侧数据和右侧数据排序
左侧数据表示的区间为[begin,key_i-1] ,右侧数据表示的区间为[key_i1,end],直接递归调用即可 int begin left;int end right;//循环省略QuickSort(arr, begin, key_i - 1);QuickSort(arr, key_i 1,end);
考虑到循环执行时,left和right的值会改变,因此需要先保存left和right的值至begin和end中
画图为(极像二叉树的递归) 递归结束的条件
何时从递推到回归?(注意返回的条件写在QuickSort函数的最前面)
1.较容易分析的结束条件:leftright 2.以{2,1}为例分析另一个结束条件 则另一个结束条件为leftright
综上:递推结束的条件为leftright
(其实从区间也能看出递推结束的条件:左区间 [begin,key_i-1]推出当beginkey_i-1时区间成立,begin对应形参left,key_i-1对应形参right,因此leftright;右区间 [key_i1,end]推出当key_i1end时区间成立,key_i1对应形参left,end对应形参right,因此leftright)
**注意:递归函数先写递归的结束条件再写递推的具体内容**
完整代码
void QuickSort(int* arr, int left, int right)
{if (left right)return;//单趟快速排序int begin left;int end right;int key_i left;while (left right){//由于key_ileft,因此right指针先走//右边找小while (left right arr[right] arr[key_i]){right--;}//左边找大while (left right arr[left] arr[key_i]){left;}Swap(arr[left], arr[right]);}Swap(arr[key_i], arr[left]);key_i left;//arr[key_i]和arr[left]交换后下标要改变,否则会对下次递归产生不利结果QuickSort(arr, begin, key_i - 1);QuickSort(arr, key_i 1,end);
}
运行结果 注:有关Hoare排序为什么key_ileft要让right先走的原因和Hoare排序的优化见下篇文章
