手写六种常见的排序算法

手写六种常见的排序算法

冒泡排序 BubbleSort

基本原理

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

复杂度

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

代码实现

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) $,不是稳定排序

代码实现

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) $,即数组本身是完全有序的,扫描一趟即可,注意查找插入位置可以使用二分查找,但是依然不可避免移动元素,是稳定排序

代码实现

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) $,可以对数组原地建堆,无需额外空间开销,不是稳定排序

代码实现

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),是稳定排序

代码实现

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++];
            }
        }
    }
}

快速排序

基本原理

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

复杂度

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

代码实现

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;
    }
}

排序总结

十大排序算法.jpg

参考

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://yzt.cool/archives/手写六种常见的排序算法