排序算法

发表于 | 分类于

通用方法

为了使排序算法更有适用性，所以不是简单的使用Int数组，而是使用Comparable。Java中的String，Integer，Byte类都实现了Comparable接口，所有这些类都可以使用这些排序算法。

交换数组的i，j索引位置的元素

1
2
3
4
5
private static void exch(Comparable[] a,int i,int j){
    Comparable temp = a[i];
    a[i] = a[j];
    a[j] = a[i]
}

判断一个元素是否小于另一个元素

1
2
3
private static boolean less(Comparable v,Comparable w){
    return v.compareTo(w) < 0;
}

展示排序的结果

1
2
3
4
5
6
private static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }

选择排序

选择排序的算法就是每次选择数组中的最小（最大）的元素放在数组的最开始（最末端）。

1
2
3
4
5
6
7
8
9
10
11
12
public static void selection(Comparable[] a){
    for (int i = 0;i < a.length;i++){
        int min = i;
        //寻找当前最小的元素
        for	(int j = i+1;j < a.length();j++){
            if	(less(a[j],a[min]))
                min = j;
        }
        //将当前最小的元素交换放在数组的前列
        exch(a,i,min);
    }
}

插入排序

插入排序算法是从索引0开始，将每个索引的元素放在左侧合适的位置，使得当前索引的左侧永远是有序的。

1
2
3
4
5
6
7
8
9
public static void insertion(Comparable[] a){
    //i索引的左侧都是有序的
    for	(int i = 0;i < a.length;i++){
        //先判断j索引是否大于0，再判断当前j索引的元素是否小于j左侧的元素，成立就交换这两个元素
        for	(int j = i;j > 0 && less(a[j],a[j-1]);j--){
            exch(a,j,j-1);
        }
    }
}

希尔排序

希尔排序是按照一定的步长，将数组的元素分成若干组，将这若干组中的元素排序，再取比上一个步长小的步长再一次排序，直到步长为1。在对分组元素排序的时候相当于是一个简化的插入排序。

步长的选择对希尔排序的性能影响很大。

时间复杂度小，没有使用额外的空间，排序算法的优先考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void shell(Comparable[] a){
   //设置步长
    int n = 1;
    while (n < a.length/3)  n = n*3+1;
    //按照步长分组进行插入排序，直到步长为1；
    while(n >= 1){
        for	(int i = 0;i < a.length;i++){
            for (int j = i;j >= n && less(a[j],a[j-n]);j -= n){
                exch(a,j,j-n);
            }
        }
        n = n/3;
    }
}

和普通的插入排序相比，希尔排序在步长为1的时候整个数组已经趋近于有序的了，在移动交换元素的时候使用的时间会比插入排序更少。但是希尔排序也是不稳定的。

归并排序

归并排序的思想就是把一个数组分为左右两个部分，分别对这两个部分进行排序，再对这两个有序的左右部分合并。而利用递归的思想，可以把数组一直划分为左右两个部分，直到左右两个部分都只包含了一个元素（这个时候，左右两个部分都是有序的）再依次合并左右两个部分的数组。

利用递归思想划分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//定义一个额外的数组，在合并左右两个数组的辅助
private static Comparable[] aux;

//外部调用的入口
public static void sort (Comparable[] a){
    //初始化aux
   	aux = new Comparable[a.length];
    sort(a,0,a.length-1);
}

//用递归的思想划分数组
private static void sort(Comparable[] a,int lo,int hi){
    //递归结束的条件
    if	(lo >= hi) return;
    int mid = lo + (hi-lo)/2;
    //将左半部分排序
    sort(a,lo,mid);
    //将右半部分排序
    sort(a,mid+1,hi);
    //合并左右两个部分
    merge(a,lo,mid,hi);
}

合并两个有序的数组(合并a[lo..mid]和a[mid+1,hi])

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void merge(Comparable[] a,int lo,int mid,int hi){
    int i = lo,j = mid + 1;//i为左半部分起始索引，j为右半部分起始索引
    //复制数组
    for (int k = 0;k < a.length;k++){
        aux[k] = a[k];
    }
    for	(int k = lo;k < hi;k++){
        if (i > mid) a[k] = aux[j++];//左半部分用完，取右半部分
        else if (j > lo)  a[k] = aux[i++];//右半部分用完，取左半部分
        else if (less(a[j],a[i])) a[k] = aux[j++]; //右半部分小于左半部分的数，取右半部分
        else a[k] = aux[i++]; //左半部分小于右半部分，取左半部分
    }
}

归并排序就是通过递归不断把数组分为左右两个部分，直到左右两个部分都只包含一个元素的时候，合并两个数组。算法的关键部分就是掌握合并数组是可能出现的4种情况。

快速排序

快速排序是一种对随机数组排序较优的算法。

主要思路：先随机选取一个元素j，在数组的开始和结尾都各有一个指针（双指针）,在遍历到左边有一个元素lo大于j，右边有一个元素hi小于j，将这两个lo和hi交换位置。直到左右两个指针相遇。这个时候数组有一下的性质：

1.元素j已经处于排序以后的位置

2.元素j左边的元素都小于j

3.元素j右边的元素都大于j

采用递归的思想，对左右两边的元素进行上述操作。

递归操作

1
2
3
4
5
6
7
8
9
10
11
public static void sort(Comparable[] a){
    sort(a,0,a.length);
}

private static void sort(Comparable[] a,int lo,int hi){
    //递归结束的条件
    if (lo >= hi) return; 
    int j = partition(a,lo,hi);
    sort(a,lo,j-1);
    sort(a,j+1,hi);
}

选取元素，划分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int partition(Comparable[] a,int lo,int hi){
    int i = lo,j = hi+1;
    //选取的随机元素
    Comparable random = a[lo];
    while(true){
        //通过左指针寻找左边大于random的元素
        while(less(a[++i],random)) if(i == hi) break;//找不到就结束循环
        //通过右指针寻找右边小于random的元素
        while(less(random,a[--j])) if(j == lo) break;//找不到就结束循环
        //如果左右两个指针已经相遇过了就不交换左右两边的元素。
        if (i >= j) break;
        //找到了左右两边的元素，进行交换
        exch(a,i,j);
    }
    //交换选取的随机元素到合适的位置
    exch(a,j,lo);
    //返回已经排序好的元素的位置
    return j;
}

快速排序算法的优化：

1、在切分到比较小的数组的时候，切换为插入排序，节省时间。

2、在一开始选取元素的时候，通过计算中位数，来确保划分数组时左右两边数组大小是接近的。

3、在对于有很多重复元素的数组的时候，划分数组分为大于、小于、等于这三个部分，而不只是换分为大于、小于两个部分，就可以减少对重复数据递排序的时间。