快速排序总结
1.定义
通过比较来确定输入序列<a1,a2,..,an>的元素间相对次序的排序算法称为比较排序算法。
2.算法解释
(1) 选择排序:
选择排序的基本思想是对待排序的记录序列进行 n-1 遍的处理,第 i 遍处理是将 L[i..n]中
最小者与 L[i]交换位置。这样,经过 i 遍处理之后,前 i 个记录的位置已经是正确的了。
(2): 冒泡排序
最简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着
排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我 们要对这个“气
泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相
邻的元素的顺序是否正确。如果发现两个相邻元素的顺序 不对,即“轻”的元素在下面,就
交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,
“次轻”的元素就浮到了次高位置。 在作第二遍处理时,由于最高位置上的元素已是“最轻”
元素,所以不必检查。一般地,第 i 遍处理时,不必检查第 i 高位置以上的元素,因为经过
前面 i-1 遍的 处理,它们已正确地排好序
(3) 插入排序
插入排序的基本思想是,经过 i-1 遍处理后,L[1..i-1]己排好序。第 i 遍处理仅将 L[i]插入
L[1..i-1]的适当位置,使得 L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比
较的方法。首先比较 L[i]和 L[i-1],如果 L[i-1]≤ L[i],则 L[1..i]已排好序,第 i 遍处理就结束
了;否则交换 L[i]与 L[i-1]的位置,继续比较 L[i-1]和 L[i-2],直到找到某一个位置 j(1≤j≤i-
1),使得 L[j] ≤L[j+1]时为止
(4) 快速排序
快速排序的基本思想是基于分治策略的。对于输入的子序列 L[p..r],如果规模足够小
则直接进行排序,否则分三步处理:
分解(Divide):将输入的序列 L[p..r]划分成两个非空子序列 L[p..q]和 L[q+1..r],使 L[p..q]中
任一元素的值不大于 L[q+1..r]中任一元素的值。
递归求解(Conquer):通过递归调用快速排序算法分别对 L[p..q]和 L[q+1..r]进行排序。
合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在 L[p..q]和 L[q+1..r]
都排好序后不需要执行任何计算 L[p..r]就已排好序。
public class Sort ...{
/**//*
* 交换算法