搜狗做题网快排算法是怎样排序的呢
来源：学生作业帮 编辑：搜狗做题网作业帮 分类：数学作业 时间：2024/07/03 04:29:17
快排算法是怎样排序的呢
若是以第一个元素为基准,21 25 5 17 9 23 30这个序列的第一遍排序后的结果是什么呢
若是以第一个元素为基准,21 25 5 17 9 23 30这个序列的第一遍排序后的结果是什么呢
快排的一趟称为一次划分,原因是一趟排序后,数组以基准元素X为界,左边的元素都小于等于X,右边的元素都大于等于X.
要做到这点：先刨去21,再设俩指针,一个指向最左边,一个指向最右边.左边指针的往右走,找一个大于等于21的元素,右边的指针往左走,找一个小于等于21的元素,然后俩指针的值交换.继续循环上面的过程.直到俩指针相遇或擦肩而过.把21交换到俩指针相遇的地方就可以了.
第一次交换25和9,然后俩指针相遇,把21和界限处的17交换,得到：
结果：17 9 5 21 25 23 30
再问： 请问这个快排算法是不是有不同的实现方法啊，我的理解和你一样；但是百度百科中，第一次交换后应该为9 25 5 17 9 23 30 基准变量K的值为21
再答： 你算是问对人了，只要是每一趟走下来能够达成划分的效果，都算是快速排序，所以快排有很多种划分的实现方式。
我举得栗子是Hoare最一开始提出的一种划分方式。理解上最为容易。百科上的是另外一种，对这个方式做了一点小改进，但是方式也还是双向遍历。算法导论上还有一种更为先进的实现，这种实现甚至可以一次单向遍历就可以完成划分，这意味着对某些只能单向遍历的数据结构（比如链表）可以进行快排。
其实上面几种，只要掌握一种就可以了，效率都差不多。
要做到这点：先刨去21,再设俩指针,一个指向最左边,一个指向最右边.左边指针的往右走,找一个大于等于21的元素,右边的指针往左走,找一个小于等于21的元素,然后俩指针的值交换.继续循环上面的过程.直到俩指针相遇或擦肩而过.把21交换到俩指针相遇的地方就可以了.
第一次交换25和9,然后俩指针相遇,把21和界限处的17交换,得到：
结果：17 9 5 21 25 23 30
再问： 请问这个快排算法是不是有不同的实现方法啊，我的理解和你一样；但是百度百科中，第一次交换后应该为9 25 5 17 9 23 30 基准变量K的值为21
再答： 你算是问对人了，只要是每一趟走下来能够达成划分的效果，都算是快速排序，所以快排有很多种划分的实现方式。
我举得栗子是Hoare最一开始提出的一种划分方式。理解上最为容易。百科上的是另外一种，对这个方式做了一点小改进，但是方式也还是双向遍历。算法导论上还有一种更为先进的实现，这种实现甚至可以一次单向遍历就可以完成划分，这意味着对某些只能单向遍历的数据结构（比如链表）可以进行快排。
其实上面几种，只要掌握一种就可以了，效率都差不多。