排序算法总结

稳定性：如果一个排序算法能够保留数组中重复元素的相对位置，则可以被称为稳定的。有很多办法能够将任意排序算法变为稳定的，但一般只有在稳定性要求是必要的情况下才会去实现。

快速排序是最快的通用排序算法。

java系统库中主要的的排序算法java.util.Arrays.sort()实际上代表了一系列排序算法：

• 每种原始数据类型有一种不同的排序算法
• 一个适用于所有实现了Comparable接口的数据类型的排序算法
• 一个适用于实现了比较器Comparator的数据类型的排序算法

Java系统选择对原始数据类型使用（三向切分的）快速排序，对引用类型使用归并排序。

使用排序算法解决其他问题的思想是算法设计领域的基本技巧----归约的一个例子。规约是指为了解决某个问题而发明出来的一个算法正好可以用来解决另一个问题。

下面是排序算法解决一些其他问题的例子：

找出重复元素

对大数组，平方级别的算法将元素互相比较一遍不太合适。我们可以先将数组排序，然后记录连续出现的重复元素即可。

Quick.sort(a);
int count = 1;
for(int i=1;i<a.length;i++){
    if(a[i].compareTo(a[i-1])!=0)
        count++;
//统计a[]数组中不重复元素个数

排列

一组排列就是一组N个整数的数组，其中0到N-1每个数都只出现一次。两个排列之间的Kendall tau距离就是两组排列中顺序不同的数对的数目。如0 3 1 6 2 5 4和1 0 3 6 4 2 5之间的Kendall tau距离是4。因为0-1，3-1，2-4，5-4这4对数字在两组数列中相对顺序不同。可以根据插入排序算法设计一个算法计算Kendall tau距离。

选取第k小元素

下面的select()方法可以在线性时间内解决这个问题，它用两个变量lo和hi限制含有k元素的子数组，并用快速排序的切分法来缩小子数组范围。

切分法将数组分为a[lo...j], a[j], a[j+1...hi]三个数组。如果j=k，问题解决。如果k<j,我们就需要切分左子数组，否则切分右子数组。不断切分直到子数组只含第k个元素，此时a[0...k-1]都小于a[k], a[k+1...hi]都大于k,算法完成。

public static select(Comparable[] a,int k){
    int lo = 0, hi = a.length;
    while(hi>lo){
        int j = partition(a,lo,hi);//调用快速排序的切分方法
        if(j == k)return a[k];
        else if(j>k) hi = j-1;
        else if(j<k) lo = j+1;
    {
    return a[k];
}