面试中常见的七种排序算法

Posted on

排序算法可以说是一项基本功，解决实际问题中经常遇到，针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率。

一、选择排序

对于给定的一组记录，将每轮比较最小记录的位置与该轮初始位置的记录交换。

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
/**
 * SelectSort
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        selectSort(arrays);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }
    }

    private static void selectSort(int[] arrays) {
        int min;
        int min_index;
        for (int i = 0; i < arrays.length - 1; i++) {
            min = Integer.MAX_VALUE;
            min_index = i;
            for (int j = i + 1; j < arrays.length; j++) {
                if (min > arrays[j]) {
                    min_index = j;
                    min = arrays[j];
                }
            }
            if (arrays[i] > arrays[min_index]) {
                arrays[i] ^= arrays[min_index];
                arrays[min_index] ^= arrays[i];
                arrays[i] ^= arrays[min_index];
            }

        }
    }
}

二、插入排序

将当前记录依次插入到之前的有序数组中。

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
/**
 * InsertSort
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        insertSort(arrays);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }

    }

    private static void insertSort(int[] arrays) {
        for (int i = 1; i < arrays.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arrays[i] < arrays[j]) {
                    int temp = arrays[i];
                    for (int k = i - 1; k >= j; k--) {
                        arrays[k + 1] = arrays[k];
                    }
                    arrays[j] = temp;
                    break;
                }
            }
        }
    }
}

三、冒泡排序

依次对相邻的两个数进行比较。

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
/**
 * BubbleSort
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        bubbleSort(arrays);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }
    }

    private static void bubbleSort(int[] arrays) {
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = arrays.length - 1; j > i; j--) {
                if (arrays[j] < arrays[j - 1]) {
                    arrays[j - 1] ^= arrays[j];
                    arrays[j] ^= arrays[j - 1];
                    arrays[j - 1] ^= arrays[j];
                }
            }
        }
    }
}

四、快速排序

一趟排序后将原序列分成两部分，前一部分的所有记录均比后一部分小，递归该过程。

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
/**
 * QuickSort
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        quickSort(arrays, 0, arrays.length - 1);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }
    }

    private static void quickSort(int[] arrays, int head, int tail) {
        int i = head;
        int j = tail;
        int index = arrays[i];
        while (i < j) {
            while (i < j && arrays[j] >= index) {
                j--;
            }
            if (i < j) {
                arrays[i++] = arrays[j];
            }
            while (i < j && arrays[i] < index) {
                i++;
            }
            if (i < j) {
                arrays[j--] = arrays[i];
            }
            arrays[i] = index;
            quickSort(arrays, head, i - 1);
            quickSort(arrays, i + 1, tail);

        }
    }

}

五、归并排序

两两归并，直到得到一个有效序列

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
/**
 * MergeSort
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        mergeSort(arrays, 0, arrays.length - 1);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }
    }

    private static void mergeSort(int[] arrays, int head, int tail) {
        if (head < tail) {
            int mid = (head + tail) / 2;
            mergeSort(arrays, head, mid);
            mergeSort(arrays, mid + 1, tail);
            merge(arrays, head, mid, tail);
        }
    }

    private static void merge(int[] arrays, int head, int mid, int tail) {
        int[] new_arrays = new int[tail - head + 1];
        int i = head;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= tail) {
            if (arrays[i] <= arrays[j]) {
                new_arrays[index] = arrays[i];
                i++;
            } else {
                new_arrays[index] = arrays[j];
                j++;
            }
            index++;
        }
        while (i <= mid) {
            new_arrays[index++] = arrays[i++];

        }
        while (j <= tail) {
            new_arrays[index++] = arrays[j++];
        }
        for (int k = head; k <= tail; k++) {
            arrays[k] = new_arrays[k - head];
        }
    }

}

六、堆排序

堆排序包括:

1、构建堆。

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
43
/**
 * MinHeapSort
 */
public class MinHeapSort {

    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        minHeapSort(arrays);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }
    }

    private static void minHeapSort(int[] arrays) {
        for (int i = arrays.length / 2 - 1; i >= 0; i--) {
            adjustMinHeap(arrays, i, arrays.length - 1);
        }
        for (int i = arrays.length - 1; i >= 0; i--) {
            int temp;
            temp = arrays[0];
            arrays[0] = arrays[i];
            arrays[i] = temp;
            adjustMinHeap(arrays, 0, i - 1);

        }
    }

    private static void adjustMinHeap(int[] arrays, int i, int j) {
        int temp = 0;
        int child = 0;
        for (temp = arrays[i]; 2 * i + 1 <= j; i = child) {
            child = 2 * i + 1;
            if (child < j && arrays[child] > arrays[child + 1]) {
                child++;
            }
            if (arrays[child] < temp)
                arrays[i] = arrays[child];
            else
                break;
        }
        arrays[i] = temp;
    }
}

七、希尔排序

也称为“缩小增量排序”。根据对应步长，将待排序列分成多个子序列，分别对子序列进行插入排序。

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
/**
 * ShellSort
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arrays = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
        shellSort(arrays);
        for (int var : arrays) {
            System.out.print(var + "  ");
        }
    }

    private static void shellSort(int[] arrays) {
        for (int h = arrays.length; h > 0; h /= 2) {
            for (int i = h; i < arrays.length; i++) {
                int temp = arrays[i];
                int j;
                for (j = i - h; j >= 0; j -= h) {
                    if (temp < arrays[j]) {
                        arrays[j + h] = arrays[j];
                    } else {
                        break;
                    }
                }
                arrays[j + h] = temp;
            }

        }
    }
}