排序算法

Posted on Edited on In Waline:

本文讲述排序算法, 分别分为插入排序、交换排序、选择排序、堆排序几种算法, 分别用java进行详细的描述.

0x01.插入排序

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import java.util.*;
public class InsertionSort 
{
    public static void main(String[] args){
        int[] arr = {10, 20, 30, 15, 25, 12};
        System.out.print("原数组:");
        printArray(arr);
        // insertionSort3(arr);
        shellsort(arr);
        System.out.print("排序之后的:");
        printArray(arr);
    }
    
		// 希尔排序
    public static int[] shellsort(int[] arr) {
        int number = arr.length/2;
        int i;
        int j;
        int temp;
        while(number >= 1) {
            for (i = number; i < arr.length; i++) {
                temp = arr[i];
                j = i - number;
                while (j >= 0 && arr[j] > temp) {
                    arr[j+number] = arr[j];
                    j = j-number;
                }
                arr[j+number] = temp;
            }
            number = number/2;
        }
        return arr;
    }

		// 第三种实现方式
    public static int[] insertionsort3(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int focus = arr[i];
            int j = i-1;
            for (; j >= 0 && arr[j] > focus; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = focus;
        }
        return arr;
    }
    
    // 第二种实现方式
    public static int[] insertionsort2(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int focus = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > focus)
            {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = focus;
        }
        return arr;
    }

    /*  
       1, 3 , 2, 8, 6, 7
       第一圈 base = 132867 focus=3
            132867
       第二圈 base = 132867 focus=2
            123867
            123867
       第三圈 base = 123867 focus=8
            123867
            123867
            123867
       第四圈 base = 123867 focus=6
            123687
            123687
            123687
            123687
       第五圈 base = 123687 focus=7
            123678
            123678
            123678
            123678
            123678
    */
    public static int[] insertionsort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j-1]) {
                    swapElement(arr, j, j-1);               
                }
            }
        }
        return arr;
    }

    public static int[] swapElement(int[] arr,int i,int j) {
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }

    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x != arr.length-1) {
                System.out.print(arr[x] + ", ");
            } else {
                System.out.print(arr[x] + "]" + "\n");
            }
        }
    }
}

0x02.交换排序

0x0201.冒泡排序
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
import java.util.*;

public class BubbleSort
{
    public static void main(String[] args) {
        int[] arr = {149,138,165,197,176,113,127,114,110};
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
        System.out.println();
        bubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
        System.out.println();
    }
    
  	// 冒泡排序
    public static int[] bubbleSort(int[] arr)
    {
        for (int i =0; i < arr.length; i++)
        {
            for (int j = 0; j < arr.length-1-i;j++)
            {
                if (arr[j] > arr[j+1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }
}
0x0202.快速排序
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
import java.util.*;

public class QuickSort
{
    public static void main(String[] args) {
        int[] arr = {9,4,6,8,1,5,3};
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
       recurPartiton(arr, 0, arr.length-1); 
    }

    public static void recurPartiton(int[] arr, int start,int end) {
        if (end-start<1) {
            return;
        }
        int part = partArr(arr, start, end);
        // 分三种情况继续拆分
        if (part == start) {
             recurPartiton(arr, part+1, end);
        } else if(part == end) {
            recurPartiton(arr, start, end-1);
        } else {
            recurPartiton(arr, start, part-1);
            recurPartiton(arr, part+1, end);
        }
    }

    public static int partArr(int[] arr, int start, int end) {
        int base = arr[end];
        int n = start;
        for (int i = start; i < end; i++) {
            if(arr[i] < base) {
                if (i != n){
                    exchangeE(arr, i, n);
                }
                n++;
            }
        }
        exchangeE(arr, n, end);
        return n;
    }
    
  	// 工具
    public static void exchangeE(int[] arr, int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

0x03. 选择排序

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
public class SelectSort
{
    public static void main(String[] args) {
        int a[] = {13, 15, 89, 60, 39, 12, 109, 56, 72};
        int i;
        int j;
        for (i = 0; i < a.length; i++) {
            System.out.print(a[i] + "  ");
        }
        System.out.println();
        for (i = 0; i < a.length; i++) {
            int min = a[i];
            for (j = i+1; j < a.length; j++) {
                if(min > a[j]) {
                    min = a[j];
                    a[j] = a[i];
                    a[i] = min;
                }
            }
            a[i] = min;
        }
        
        for (i = 0; i < a.length; i++) {
            System.out.print(a[i]+"  ");
        }
        System.out.println();
    }
}

0x04.堆排序

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
import java.util.*;

public class HeapSort
{
    public static void main(String[] args) {
        int[] arr = {9,1,7,6,5,4,3,2,8};
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        // 1.构造一个大顶堆
        for (int i = arr.length/2-1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        // 2.调整对结构+交换对顶元素与末尾元素
        for (int j = arr.length-1; j > 0; j--) {
            swap(arr,0,j);
            adjustHeap(arr,0,j);
        }
    }
    
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        for(int k = 2*i+1; k < length; k=k*2+1) {
            if(k+1 < length && arr[k] < arr[k+1]) {
                k++;
            }
            if(arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}