算法：排序算法

发表于 更新于 分类于 阅读次数： 本文字数： 3.6k 阅读时长 ≈ 3 分钟

选择排序 (Selection sort)

Selection Sort是一种最基本的排序方法。这种排序方法的基本想法就是：第一次找到最小的数与第一位进行交换，第二次找到第二小的数与第二位进行交换，第三次找到第三小的数与第三位进行交换……以此类推。由于找第i小的数时，前面i-1个数已经是前i-1个最小的数了，所以只要在后N-i+1个数中找到最小的数和第i个数进行交换就好了。也就是说，这个方法需要嵌套两个for循环，时间复杂度很明显也就是\(O(N^2)\)了。Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SelectionSort{
    public static void sort(double[] a){
        int length = a.length;
        for(int i = 0; i < lengh; i++){
            int min = i
            for(int j = i; j < length; j++){
                if (a[j] < a[min]){
                	min = j;
                }
            }
            a[min] = a[i] + a[min];
            a[i] = a[min] - a[i];
            a[min] = a[min] - a[i];
        }
    }
}

插入排序 (Insertion sort)

Insertion Sort是另一种基本的排序方法，它会比Selection Sort更有效率一些，因为这种排序方法的效率和原本数组的混乱度有关，如果说这个数组本身就已经排序十分整齐的话，这个时候这种算法的效率就会很高了。这种算法的基本想法就和我们打扑克的时候理牌的方法是一样的。我们打牌的时候，会对我们想要进行移动的那张牌进行大小判断，将那张牌插入到我们已经整理好的一堆牌里的对应的位置。这种算法就是这样，我们假设我们想要移动第i个数，并且前i-1张牌都已经进行好了排序，那么我们只需要对这个数与前一个数进行大小的比较，如果这个数更小，那么就进行交换，直到我们找到了前一个位置的数比这个第i个数还要小的时候，再去移动下一个数。所以，这个方法仍然需要嵌套两个for循环，时间复杂度也是\(O(N^2)\)。Java代码

1
2
3
4
5
6
7
8
9
10
11
12
public class InsertionSort{
    public static void sort(double[] a){
        int length = a.length;
        for(int i = 1; i < length; i++){
            for(int j = i; j >= 0 && a[j]< a[j-1]; j--){
                a[j] = a[j] + a[j-1];
                a[j-1] = a[j] - a[j-1];
                a[j] = a[j] - a[j-1];
            }
        }
    }
}

归并排序 (Merge sort)

在之前寻找一个数组中的最大值的时候，我们可以使用二分法的方法寻找最大值，可以大大提高效率。那么在排序的时候，也可以使用类似的想法，利用分治(divide and conquer)可以将时间复杂度降低至\(O(lgN)\)。首先，我们可以考虑一下情况，有两组数，都是已经排好序的，如果将这两组数按照顺序合并在一起，那么我们可以新创建一个数组，存储新的有顺序的数。首先，比较两组数的第一位数，将较小的数放进新的数组中，较小数所在数组的下一位与较大数所在数组原来的数继续进行比较，直到有一组数达到了尽头，然后把另一组剩下的数放进去得到的新的数组就是排好序的合并后的数组。Java代码：

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){
    // 数组aux[]为原数组的复制
    int i = lo, j = mid+1;
    for(inr i = 0; i <= hi; i++){
        aux[i] = a[i];
    }
    for(int k = lo; k <= hi; k++){
        if(i > mid) a[k] = aux[j++]
        else if(j > hi) a[k] = aux[i++];
        else if(less(a[i], a[j])) a[k] = aux[i++];
        else a[k] = a[j++];
    }
}

然后，就可以使用分治算法递归进行计算。Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class MergeSort{
    private static Comparable[] aux;
    
   	public static void sort(Comparable[] a){
        aux = new Comaparable[a.length]; 
        sort(a, 0, hi / 2, hi);
    }
    
    public 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);
    } 
    
   	public static void merge(Comparable[] a, int lo, int mid, int hi){
        // 数组aux[]为原数组的复制	
        int i = lo, j = mid+1;
        for(int k = lo; k <= hi; k++){
            aux[k] = a[k];
        }
        for(int k = lo; k <= hi; k++){
            if(i > mid) a[k] = aux[j++]
            else if(j > hi) a[k] = aux[i++];
            else if(less(a[i], a[j])) a[k] = aux[i++];
            else a[k] = a[j++];
        }
	}
}

快速排序 (Quick sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class QuickSort {
    public void sort(Comparable[] a) {
        quickSort(a, 0, a.length-1);
    }
    
    private void quickSort(Comparable[] a, int lo, int hi) {
        if (lo < hi) {
            int partitionIndex = partition(a, lo, hi);
            quickSort(a, lo, partitionIndex-1);
            quickSort(a, hi, partitionIndex+1);
        }
    }
    
    private int partition(Comparable[] a, int lo, int hi) {
        ...
    }
    
    private void swap(Comparable[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

不同版本的partition：主要思想都是一致的，将比pivot小的放在左边，比他大的放在pivot的右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 算法第四版 */
private int partition(Comparable[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    int pivot = lo;
    // Scan right, scan left, check for scan complete, and exchange
    while (true) {
        while (a[++i] < a[pivot]) if (i == hi) break;
        while (a[pivot] < a[--j]) if (j == lo) break;
        if (i >= j) break;
        swap(a, i, j);
    }
    swap(a, lo, j);
    return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/* 菜鸟教程 */
private int partition(Comaparable[] a, int lo, int hi) {
    int pivot = lo;
    int index = pivot + 1;
    for (int i = index; i <= hi; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}