程序员必会算法系列--基本排序7个

发表于 | 分类于
7个程序员必会的排序算法

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 时间复杂度O(n2)
 *
 * @author Administrator
 *
 */
public class BubbleSort {
    // 排序算法
    public static int[] bubbleSort(int[] A, int n) {
        long startTime = System.nanoTime();
        // i控制比较次数
        for (int i = 0; i < n; i++) {
            for (int j = n - 2; j >= i; j--) {
                if (A[j + 1] < A[j]) {
                    swap(A, j, j + 1);
                }
            }
        }
        long endTime = System.nanoTime();
        System.out.println("优化前运行时间为："+(endTime-startTime)+"纳秒");
        return A;
    }
    // 排序算法优化
    public static int[] newBubbleSort(int[] A, int n) {
        long startTime = System.nanoTime();
        // i控制比较次数
        boolean flag = true;
        for (int i = 0; i < n && flag; i++) {
            flag = false;
            for (int j = n - 2; j >= i; j--) {
                if (A[j + 1] < A[j]) {
                    swap(A, j, j + 1);
                    flag = true;
                }
            }
        }
        long endTime = System.nanoTime();
        System.out.println("优化后运行时间为："+(endTime-startTime)+"纳秒");
        return A;
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    // 测试
    public static void main(String[] args) {
        int arr[] = { 54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28 };
        int arr1[] = {54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28};
        System.out.println(Arrays.toString(BubbleSort.bubbleSort(arr, arr.length)));
        System.out.println("-------------------------------------------------------");
        System.out.println(Arrays.toString(BubbleSort.newBubbleSort(arr1, arr1.length)));
    }
}

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
34
35
36
37
38
39
40
41
42
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 选择排序
 * 时间复杂度O(n2)
 *
 * @author Administrator
 *
 */
public class SelectionSort {
    public static int[] selectionSort(int A[], int length) {
        int min = -1;
        for (int i = 0; i < length; i++) {
            //初始化最小值的索引为i
            min = i;
            for (int j = i + 1; j < length; j++) {
                if (A[min] > A[j]) {
                    min = j;
                }
            }
            if(min != i){
                swap(A, i, min);
            }
        }
        return A;
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    // 测试
    public static void main(String[] args) {
        int arr[] = { 54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28 };
        System.out.println(Arrays.toString(SelectionSort.selectionSort(arr, arr.length)));
    }
}

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
31
32
33
34
35
36
37
38
39
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 插入排序
 * 时间复杂度O(n2)
 *
 * @author Administrator
 *
 */
public class InsertSort {
    // 排序算法
    public static int[] insertSort(int[] A, int n) {
        //空出索引0，认为A[0]是有序的
        for(int i = 1; i < n; i++){
            //依次用A[i]与A[i]左边的值比较，找到插入位置
            for(int j = i; j > 0; j--){
                if(A[j-1] > A[j]){
                    swap(A, j, j-1);
                }
            }
        }
        return A;
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    // 测试
    public static void main(String[] args) {
        int arr[] = { 54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28 };
        System.out.println(Arrays.toString(InsertSort.insertSort(arr, arr.length)));
    }
}

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
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 希尔排序
 * 时间复杂度为O(N*logN)
 *
 * @author Administrator
 *
 */
public class ShellSort {
    public static int[] shellSort(int arr[], int length) {
        //初始化一个步长
        int step = 1;
        //获得一个最优步长
        while (step < length / 3) {
            step = 3*step +1;
        }
        //根据步长执行插入排序
        while (step >= 1) {
            for (int i = step; i < length ; i++) {
                for (int j = i; j >= step ; j = j - step) {
                    if (arr[j] < arr[j - step]) {
                        swap(arr, j, j - step);
                    }
                }
            }
            //缩小步长划分的数组范围
            step = step / 3;
        }
        return arr;
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    public static void main(String[] args) {
        int arr[] = { 255,64,108,341,217,35,263,272,49,225,229,5,184,119,200,239,126,361,333,58,145,204,322,313,141,95,190,41,5,16,139,212,281,72,302,5,178,156,33,87,116,12,69,253,178,78,95,245,260,218,131,311,175,150,370,164,350,192,373,294,239,325,25,137,147,354,287,169,37,102,232 };
        System.out.println(Arrays.toString(ShellSort.shellSort(arr, arr.length)));
    }
}

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
91
92
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 归并排序
 * 时间复杂度O(N*logN)
 *
 * @author Administrator
 *
 */
public class MergeSort {
    /**
     * 归并操作，将两个有序的子区间归并成一个有序的子区间
     *
     * @param src
     * @param des
     * @param low
     * @param mid
     * @param high
     */
    private static int[] temp;
    public static void merge(int src[], int low, int mid, int high) {
        // 左边子区间的第一个索引值
        int leftIndex = low;
        // 右边子区间的第一个索引值
        int rightIndex = mid + 1;
        // 辅助数组的第一个索引值
        int startIndex = 0;
        //辅助数组
        temp = new int[high-low+1];
        // 归并操作
        while (leftIndex <= mid && rightIndex <= high) {
            if (src[leftIndex] < src[rightIndex]) {
                temp[startIndex++] = src[leftIndex++];
            } else {
                temp[startIndex++] = src[rightIndex++];
            }
        }
        // 如果左边的区间索引值还没到终点，则把左边区间的值依次赋给辅助数组
        while (leftIndex <= mid) {
            temp[startIndex++] = src[leftIndex++];
        }
        // 如果右边的区间索引值还没到终点，则把右边区间的值依次赋给辅助数组
        while (rightIndex <= high) {
            temp[startIndex++] = src[rightIndex++];
        }
        //把辅助数组里的值赋给目标数组，目标数组的初始下标为传入的最左下标
        for (int i = 0; i < temp.length; i++) {
            src[low+i] = temp[i];
        }
    }
    /**
     * 分别给左右区间排序
     *
     * @param src
     * @param low
     * @param high
     */
    public static void MSort(int src[], int low, int high) {
        int mid = (low + high) / 2;
        // 递归的结束条件
        if (low == high) {
            return;
        }
        // 给左子区间排序
        MSort(src, low, mid);
        // 给右子区间排序
        MSort(src, mid + 1, high);
        // 归并
        merge(src, low, mid, high);
    }
    /**
     * 归并排序
     *
     * @param arr
     * @param length
     * @return
     */
    public static void mergeSort(int arr[], int length) {
        MSort(arr, 0, length-1);
    }
    public static void main(String[] args) {
        int arr[] = { 54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28 };
        MergeSort.mergeSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }
}

6.快速排序

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
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 快速排序 时间复杂度O(N*logN)
 *
 * @author Administrator
 *
 */
public class QuickSort {
    /**
     * 划分左右子区间，使左子区间的里的值都小于切分的，使右子区间的里的值都大于切分点。
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition(int arr[], int low, int high) {
        // 得到切分点
        int pivot = arr[low];
        // 左右扫描指针
        int left = low+1;
        int right = high;
        while (true) {
            while (arr[left] <= pivot) {
                left++;
                if (left >= high) {
                    break;
                }
            }
            while (arr[right] > pivot) {
                right--;
                if (right == low) {
                    break;
                }
            }
            if (left >= right) {
                break;
            }
            swap(arr, left, right);
        }
        swap(arr, low, right);
        return right;
    }
    /**
     * 递归调用
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void QSort(int arr[], int low, int high) {
        if (low >= high) {
            return;
        }
        int pivot = partition(arr, low, high);
        QSort(arr, low, pivot - 1);
        QSort(arr, pivot + 1, high);
    }
    /**
     * 快速排序
     *
     * @param arr
     * @param length
     */
    public static void quickSort(int arr[], int length) {
        QSort(arr, 0, length - 1);
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    public static void main(String[] args) {
        int arr[] = { 14,313,206,53,182,215,169,148,158,272,22,80,176,200,266,301,37,234,174,163,158,158,112,281,86,14,306,137,258,27,247,33,102,5,217,254,286,255,195,234,229,225,296,158,247,42,124,96,292,71,303,144,57,297,315,44,20,111,68,92,181,187,130,167,59,156,240,75,118,184,46,94,74,142,14,313,206,53,182,215,169,148,158,272,22,80,176,200,266,301,37,234,174,163,158,158,112,281,86,14,306,137,258,27,247,33,102,5,217,254,286,255,195,234,229,225,296,158,247,42,124,96,292,71,303,144,57,297,315,44,20,111,68,92,181,187,130,167,59,156,240,75,118,184,46,94,74,142,14,313,206,53,182,215,169,148,158,272,22,80,176,200,266,301,37,234,174,163,158,158,112,281,86,14,306,137,258,27,247,33,102,5,217,254,286,255,195,234,229,225,296,158,247,42,124,96,292,71,303,144,57,297,315,44,20,111,68,92,181,187,130,167,59,156,240,75,118,184,46,94,74,142 };
        quickSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }
}

7.堆排序（代码有问题，只当记录。求指导。。）

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
package pers.yijin.sort;
import java.util.Arrays;
/**
 * 堆排序 时间复杂度O(NlogN) 提示：使用优先队列构造堆(二叉树)
 *
 * @author Administrator
 *
 */
public class HeapSort {
    public static int[] heapSort(int[] arr) {
        int size = arr.length -1;
        //只需将堆元素的一半下沉，就能使堆有序
        for (int k = size / 2 -1; k >= 0; k--) {
            sink(arr, k, size);
        }
        while(size > 0){
            //将最大元素与最小元素交换，并把交换后的最大元素脱离
            swap(arr, 0, size--);
            //下沉最小元素，找到第二大元素，继续交换
            sink(arr, 0, size);
        }
        return arr;
    }
    /**
     * 下沉算法，使堆有序
     * @param arr
     * @param k
     * @param size
     */
    private static void sink(int[] arr, int k, int size) {
        while (2 * k +1  <= size) {
            int j = 2 * k + 1;
            if (j < size && arr[j] < arr[j+1]) {
                j++;
            }
            if (arr[k] > arr[j]) {
                break;
            }
            swap(arr, k, j);
            k = j;
        }
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {106,167,277,74,146,58,160,201,144,99,146,234,305,337,375,88,64,366,36,227,220,87,163,245,95,128,350,319,129,15,80,326,266,46,216,286,342,150,200,237,299,103,68,126,121,119,149,9,362,210,269,185,262,323,350,27,170,21,110,159,128,328,290,28,253,122,193,176,39,330,260,312,342,27,95,52,163,138,376,358};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}