0%

常见排序算法

发表于 分类于
今天实在不想刷笔试题就把常见的排序手敲了一遍
今天实在不想刷笔试题就把常见的排序手敲了一遍

1.选择排序

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
31
32
33
34
35
36
37
38
39
class ChoiceSort<T extends Comparable>{

    public static void main(String[] args) {
        ChoiceSort<Integer> choiceSort = new ChoiceSort<>();
        Integer[] arr = new Integer[]{1,4,2,3,0,5,9,7};
        choiceSort.sort(arr);
        choiceSort.show(arr);
    }

    public void sort(T[] arr){
        int n = arr.length;
        for(int i = 0; i < n; i++){
            int min = i;
            for(int j = i + 1; j < n; j++){
                if(less(arr[j] , arr[min])){
                    min = j;
                }
            }
            exch(arr, i ,min);
        }
    }

    private boolean less(T t1, T t2){
        return t1.compareTo(t2) < 0;
    }

    private void exch(T[] arr, int i, int j){
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public void show(T[] arr){
        for(T t : arr){
            System.out.println(t);
        }
    }

}

2.插入排序

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
31
32
33
class InsertSort<T extends Comparable>{

    public static void main(String[] args) {
        InsertSort<Integer> insertSort = new InsertSort<>();
        Integer[] arr = new Integer[]{1,4,2,3,0,5,9,7};
        insertSort.sort(arr);
        insertSort.show(arr);
    }

    public void sort(T[] arr){
        for(int i = 1; i < arr.length; i++){
            for(int j = i; j > 0 && less(arr[j], arr[j-1]) ; j--){
                exch(arr, j, j -1);
            }
        }
    }

    private boolean less(T t1, T t2){
        return t1.compareTo(t2) < 0;
    }

    private void exch(T[] a, int i, int j){
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public void show(T[] arr){
        for(T t : arr){
            System.out.println(t);
        }
    }
}

3.冒泡排序

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
class BubbleSort<T extends Comparable>{
    public static void main(String[] args){
        BubbleSort<Integer> bubbleSort = new BubbleSort<>();
        Integer[] arr = new Integer[]{1,6,2,3,88,-2,6,2,8,0,5,9,7};
        for(int i = arr.length - 1; i >= 0; i--){
            for(int j = 0; j < i; j++){
                if(!bubbleSort.less(arr[j], arr[j+1])){
                    bubbleSort.exch(arr, j, j+1);
                }
            }
        }
        bubbleSort.show(arr);
    }

    private boolean less(T t1, T t2){
        return t1.compareTo(t2) < 0;
    }

    private void exch(T[] a, int i, int j){
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public void show(T[] arr){
        for(T t : arr){
            System.out.println(t);
        }
    }
}

4.归并排序

自顶向下的排序
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class MergeSortStartByTop<T extends Comparable>{

    private T[] tmpArr;

    public static void main(String[] args) {
        MergeSortStartByTop<Integer> mergeSort = new MergeSortStartByTop<>();
        Integer[] arr = new Integer[]{1,4,2,3,0,5,9,7};
        mergeSort.sort(arr);
        mergeSort.show(arr);
    }
    public void sort(T[] arr){
        tmpArr = (T[]) new Comparable[arr.length];
        sort(arr, 0, arr.length - 1);
    }

    private void sort(T[] arr, int l, int r){
        if(l >= r){
            return;
        }
        int mid = l + (r - l)/2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, mid, l, r);
    }

    private void merge(T[] arr, int mid, int l, int r){
        int i = l;
        int j = mid+1;
        for(int k = l; k <= r; k++){
            tmpArr[k] = arr[k];
        }
        for(int k = l; k <= r; k++){
            if(i > mid){
                arr[k] = tmpArr[j++];
            }else if(j > r){
                arr[k] = tmpArr[i++];
            }else if(less(tmpArr[i], tmpArr[j])){
                arr[k] = tmpArr[i++];
            }else {
                arr[k] = tmpArr[j++];
            }
        }
    }

    private boolean less(T t1, T t2){
        return t1.compareTo(t2) < 0;
    }

    private void exch(T[] a, int i, int j){
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public void show(T[] arr){
        for(T t : arr){
            System.out.println(t);
        }
    }
}
自底向上的排序
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class MergeSortStartByButton<T extends Comparable>{

    private T[] tmpArr;

    public static void main(String[] args) {
        MergeSortStartByButton<Integer> mergeSort = new MergeSortStartByButton<>();
        Integer[] arr = new Integer[]{1,4,2,3,0,5,9,7};
        mergeSort.sort(arr);
        mergeSort.show(arr);
    }
    public void sort(T[] arr){
        tmpArr = (T[]) new Comparable[arr.length];
        int width = 0;
        int index = 0;

        //外循环为每次归并排序,每组数据的宽度,每组数据的宽度之后进行2倍递增
        for (width = 1; width < arr.length; width = width * 2)
        {
            //内循环为基于每组数据宽度,进行多组数据的归并排序
            //index += 2 * width 因为一次归并排序都是使用2组数据进行排序,所以每次
            //  递增2组数据的偏移量
            //index < (size - width) 这里表示如果排序的索引位置连1组数据个数都不够了
            //  那就没必要处理了,因为排序至少需要1组多的数据.
            for (index = 0; index < (arr.length - width); index += 2 * width )
            {
                int l = index;
                int r = index + (2 * width - 1);
                int mid = index + (r - l) / 2;

                merge(arr, mid, l, r);
            }
        }
    }

    private void merge(T[] arr, int mid, int l, int r){
        int i = l;
        int j = mid+1;
        for(int k = l; k <= r; k++){
            tmpArr[k] = arr[k];
        }
        for(int k = l; k <= r; k++){
            if(i > mid){
                arr[k] = tmpArr[j++];
            }else if(j > r){
                arr[k] = tmpArr[i++];
            }else if(less(tmpArr[i], tmpArr[j])){
                arr[k] = tmpArr[i++];
            }else {
                arr[k] = tmpArr[j++];
            }
        }
    }

    private boolean less(T t1, T t2){
        return t1.compareTo(t2) < 0;
    }

    private void exch(T[] a, int i, int j){
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public void show(T[] arr){
        for(T t : arr){
            System.out.println(t);
        }
    }
}

5.快速排序

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class QuickSort<T extends Comparable>{

    public static void main(String[] args) {
        QuickSort<Integer> quickSort = new QuickSort<>();
        Integer[] arr = new Integer[]{1,6,2,3,88,-2,6,2,8,0,5,9,7};
        quickSort.sort(arr);
        System.out.println("-----");
        quickSort.show(arr);
    }

    public void sort(T[] arr){
        sort(arr,0, arr.length - 1);
    }

    public void sort(T[] arr, int l, int r){
        if(l >= r){
            return;
        }
        int i = partation1(arr, l, r);
        sort(arr, l, i - 1);
        sort(arr, i + 1, r);
    }

    //基准值为右边的
    public int partation(T[] arr, int l, int r){
        int i = l-1;
        int j = r;
        T t = arr[r];
        while(true){
            while(less(arr[++i], t)){
                if(i == r){
                    break;
                }
            }
            while (less(t, arr[--j])){
                if(j == l){
                    break;
                }
            }
            if(i >= j){
                break;
            }
            exch(arr, i , j);
        }
        exch(arr, r, i);
        return i;
    }

    //基准值为左边的
    public int partation1(T[] arr, int l, int r){
        int i = l;
        int j = r + 1;
        T t = arr[l];
        while(true){
            while(less(arr[++i], t)){
                if(i == r){
                    break;
                }
            }
            while (less(t, arr[--j])){
                if(j == l){
                    break;
                }
            }
            if(i >= j){
                break;
            }
            exch(arr, i , j);
        }
        exch(arr, l, j);
        return j;
    }


    private boolean less(T t1, T t2){
        return t1.compareTo(t2) < 0;
    }

    private void exch(T[] a, int i, int j){
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public void show(T[] arr){
        for(T t : arr){
            System.out.println(t);
        }
    }
}