六种常见的排序算法

冒泡排序 BubbleSort

基本原理

在一趟扫描中，如果元素 array[i] 大于元素 array[i]，则交换二者位置，这样最大的元素就会移动到数组最后，然后开始下一趟扫描，扫描区间的长度减一

复杂度

平均时间复杂度 $ O(N^2) $，最好可以到 $ O(N) $，如果已经有序，提前终止排序即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort {
    public static void sort(Integer[] array) {
        if(array==null || array.length<2) return;
        for(int end=array.length-1;end>0;end--) {
            boolean sorted = true;
            for(int begin=0;begin<end;begin++) {
                if(array[begin] > array[begin+1]) {
                    swap(array,begin,begin+1);
                    sorted = false;
                }
            }
            if(sorted) break;
        }
    }

    private static void swap(Integer[] array,int i,int j) {
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

选择排序 SelectionSort

基本原理

在一趟扫描中，选择最大的元素，将之与这趟扫描的最后一个元素交换，这样每一次扫描后，最后的元素一定是最大的

复杂度

最好，最坏，平均时间复杂度都是 $ O(N^2) $，不是稳定排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class SelectionSort {
    public static void sort(Integer[] array) {
        if(array==null || array.length<2) return;
        for(int end=array.length-1;end>0;end--) {
            int maxIndex = 0;
            for(int begin=0;begin<=end;begin++) {
                maxIndex = array[maxIndex] < array[begin] ? begin : maxIndex;
            }
            swap(array,maxIndex,end);
        }
    }

    private static void swap(Integer[] array,int i,int j) {
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

插入排序 InsertionSort

基本原理

假设数组前半段已经排好序，对于接下来的元素，需要找到一个合适的位置插入即可，找到插入位置之后，需要将其后的元素都向后移动一位（从后往前的顺序依次移动）

复杂度

最坏，平均时间复杂度都是 $ O(N^2) $，最好复杂度可以是 $ O(N) $，即数组本身是完全有序的，扫描一趟即可，注意查找插入位置可以使用二分查找，但是依然不可避免移动元素，是稳定排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class InsertionSort {
    public static void sort(Integer[] array) {
        for(int begin=1;begin<array.length;begin++) {
            Integer element = array[begin];
            int currentIndex = begin;
            while(currentIndex>0 && array[currentIndex-1] > element) {
                array[currentIndex] = array[currentIndex-1];
                currentIndex--;
            }
            array[currentIndex] = element;
        }
    }
}

堆排序 HeapSort

基本原理

堆排序可以看做是对选择排序的优化，因为选择排序需要做的是线性扫描数组，选出最大元素，而如果维护一个最大堆，可以以 $ O(1) $ 的复杂度找到堆中剩余元素的最大值，删除对顶后也只需要 $O(logN)$ 的复杂度维护最大堆的属性，其流程如下：首先使用自上而下的下滤操作对数组原地建堆，然后交换数组的首（堆顶）尾元素，减小堆的 size 对堆顶元素进行下滤，以维持最大堆的性质，然后再交换堆的首尾元素，重复以上操作

复杂度

最好、最坏、平均时间复杂度都是 $ O(NlogN) $，可以对数组原地建堆，无需额外空间开销，不是稳定排序

代码实现

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
public class HeapSort {
    public static void sort(Integer[] array) {
        heapify(array);
        int size = array.length;
        while(size > 1) {
            size--;
            swap(array,0,size);
            siftDown(array,0,size);
        }
    }

    public static void heapify(Integer[] array) {

        for(int i=(array.length>>1)-1;i>=0;i--) {
            siftDown(array,i,array.length);
        }

    }

    private static void siftDown(Integer[] array, int index, int size) {
        Integer element = array[index];
        int halfIndex = size >> 1;
        while(index<halfIndex) {
            int childIndex = (index << 1) + 1;
            Integer child = array[childIndex];

            int rightChildIndex = childIndex + 1;
            if(rightChildIndex<size && array[rightChildIndex] > child) {
                child = array[rightChildIndex];
                childIndex = rightChildIndex;
            }

            if(element >= child) break;
            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
    private static void swap(Integer[] array,int i,int j) {
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

归并排序 MergeSort

基本原理

利用递归的思想，假设数组已经使用归并排序将左右两段数组各自排好序，则按顺序合并在一起即可

复杂度

最好、最坏、平均时间复杂度都是 $O(NlogN)$，在合并的过程中需要先拷贝一份前半段（或者后半段数组），所以需要额外的 $O(N) $ 的空间，不是原地排序（In-Place），是稳定排序

代码实现

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
public class MergeSort {
    public static void sort(Integer[] arr) {
        if(arr==null || arr.length<2) return;
        int mid = arr.length >> 1;
        Integer[] leftArray = new Integer[mid];
        sort(arr, leftArray, 0, arr.length);
    }

    private static void sort(Integer[] arr, Integer[] leftArray, int begin, int end) {
        if(end-begin<2) return;
        int mid = begin + ((end - begin) >> 1);
        //int mid = (end + begin) >> 1;
        sort(arr, leftArray, begin, mid);
        sort(arr, leftArray, mid, end);
        merge(arr, leftArray, begin, mid, end);
    }

    private static void merge(Integer[] arr, Integer[] leftArray, int begin, int mid, int end) {
        int li = 0;
        int le = mid - begin;
        int ri = mid;
        int re = end;
        int ai = begin;

        
        /*for(int i=li;i<le;i++) {
            leftArray[i] = arr[begin + i];
        }*/

        // 拷贝的部分可以使用 JDK 优化过的 API
        if (le - li >= 0) System.arraycopy(arr, begin + li, leftArray, li, le - li);

        while(li < le) {
            if(ri < re && leftArray[li] > arr[ri]) {
                arr[ai++] = arr[ri++];

            }else {
                arr[ai++] = leftArray[li++];
            }
        }
    }
}

快速排序QuickSort

基本原理

首先选择某一元素作为轴点，将数组调整为：所有小于轴点的元素都在轴点左边，所有大于轴点的元素都在轴点右边，然后对左右两段数组再分别进行快速排序

复杂度

平均时间复杂度 $ O(NlogN) $，最坏时间复杂度 $ O(N^2) $，这是由于选到的轴点可能是整个数组中的最小或最大元素，注意由于每次递归中需要常数空间来临时保存轴点元素，所以空间复杂度为 $ O(logN) $，快速排序不是稳定排序

代码实现

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
public class QuickSort {
    public static void sort(Integer[] array) {
        if(array==null || array.length<2) return;
        sort(array,0,array.length);
    }

    private static void sort(Integer[] array, int begin, int end) {
        if(end-begin<2) return;
        int pivotIndex = pivotIndex(array,begin,end);
        sort(array,begin,pivotIndex);
        sort(array,pivotIndex+1,end);
    }

    private static int pivotIndex(Integer[] array, int begin, int end) {
        // 选择一个随机元素作为轴点
        //swap(array,begin, begin + (int)(Math.random() * (end-begin)));
        Integer pivot = array[begin];
        end--;
        while(begin<end) {
            while(begin<end) {
                if(pivot < array[end]) {
                    end--;
                } else {
                    array[begin++] = array[end];
                    break;
                }
            }
            while(begin<end) {
                if(pivot > array[begin]) {
                    begin++;
                } else {
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        array[begin] = pivot;
        return begin;
    }

    private static void swap(Integer[] array,int i,int j) {
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

排序总结

十大排序算法

参考