基本思想
通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
算法实现
package cn.caojiantao.tutorials.sort;
/**
* @author caojiantao
*/
public class Fast implements ISort {
@Override
public void sort(int[] data) {
sort(data, 0, data.length - 1);
}
private void sort(int[] data, int start, int end) {
if (start < end) {
int i = start, j = end, key = data[i];
while (i < j) {
while (i < j && data[j] >= key) j--;
ArrayUtils.swap(data, i, j);
while (i < j && data[i] < key) i++;
ArrayUtils.swap(data, i, j);
}
sort(data, start, i - 1);
sort(data, j + 1, end);
}
}
}
复杂度
- 时间复杂度 O(nlog2n)
- 空间复杂度 O(1)
稳定性
不稳定
网友评论