欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序、快速排序、桶排序---Java实现(带注释)

程序员文章站 2022-05-13 20:02:57
...

归并排序:

package sort;

/**
 * Created by Hollake on 2019\5\26 0026.
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
        MergeSort.mergeSort(arr);
        printArr(arr);

    }

//    归并时间复杂度O(N*logN),额外空间复杂度O(N),稳定
    public static void mergeSort(int[] arr) {
       if (arr == null || arr.length <2) return;
        
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int l, int r) {
//        如果左边界小于右边界执行,否则返回
        if (l < r) {
            int mid = (l + r) / 2;
//            采用分治
            mergeSort(arr, 0, mid);
            mergeSort(arr, mid + 1, r);
//            将左右排好序的数组重新排好序
            merge(arr, l, mid, r);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
//        创建一个新数组
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
//        只有arr数组的l到mid以及mid到r都没越界的时候执行
        while ( p1 <= mid && p2 <= r ) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
//        执行到这里说明arr数组的mid到r已经拷贝完了,接着直接拷贝l到mid的所有数
        while ( p1 <= mid ) {
            help[i++] = arr[p1++];
        }
//        执行到这里说明arr数组的l到mid已经拷贝完了,接着直接拷贝mid到r的所有数
        while ( p2 <= r ) {
            help[i++] = arr[p2++];
        }
//        将所有数重新拷贝回arr[l---r]
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
    }


    private static void printArr(int[] arr) {
        for (int i: arr){
            System.out.print(i+",");
        }
    }
}

快速排序:

package sort;

/**
 * Created by Hollake on 2019\5\29 0029.
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
        QuickSort.quickSort(arr);
        printArr(arr);
    }
//  快排时间复杂度O(N*logN),额外空间复杂度O(logN),不稳定
    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(int[] arr, int l, int r) {
//        快排递归执行条件
        if (l < r) {
//            将数组最后一个数arr[r]作为判断对象,小于它的放左边,大于它的放右边,
//            返回数组中等于arr[r]的起始位置,p数组只包含起始这两个值。例如数组为[12,3,4,6,8,6]
//            ,partation 后的数组为[3,4,6,6,12,8],返回的p =  [2,3]
            int[] p = partation(arr, l, r);
//            递归,按照中间数的起始位置将数组分治
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    private static int[] partation(int[] arr, int l, int r) {
//        less表示数组小于arr[r]的下标,第一次从-1开始,只要小于arr[r],
//        那么就less++,
        int less = l - 1;
//        less表示数组大于arr[r]的下标,第一次从r开始,只要大于arr[r],
//        那么就more--,注意,其实需要判断的是从l---r-1的数,因为r的数是作为被比较的数的
        int more = r;
//        当左下标小于右下标的时候循环
        while ( l < more ) {
//            判断l位置元素是否小于arr[i],如果小于那么将l位置和左下标也就是less加1后交换,
//            其实大部分时间,也就是没有碰到和arr[i]相等的元素,并没有进行交换,因为less+1就是l
            if (arr[l] < arr[r]) {
                swap(arr, l++, ++less);
//            如果大于,那么将--more位置的元素交换到l位置,但是l不会++,这是因为换过来的数还得重新进行判断
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
//                如果碰到等于arr[i]的数,l++
                l++;
            }
        }
//        最后将r位置的数交换到more位置,因为用的是arr[r]的数进行比较,所以最终需要将这个和more位置交换
        swap(arr, r, more);
        return new int[]{less + 1, more };
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    private static void printArr(int[] arr) {
        for (int i: arr){
            System.out.print(i+",");
        }
    }
}

桶排序:

package sort;

/**
 * Created by Hollake on 2019\5\30 0030.
 */
public class HeapSort {
    public static void main(String[] args) {
//        int[] arr = {2, 4, 6, 9, 3, 6, 4, 86, 3, 2, 4};
        int[] arr = {4,3,4};
        HeapSort.heapSort(arr);
        printArr(arr);
    }
//    堆排时间复杂度O(N*logN),额外空间复杂度O(1),不稳定
    private static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
//      从第一个数开始遍历,让数组变为大根堆(大根堆是完全二叉树)
        for (int i = 0; i < arr.length; i++) {
//            每次堆的容量扩大1,进行大根堆转变
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        while ( heapSize > 0 ) {
//          将大根堆第一个数也就是数组第一个数(大根堆中最大的数)和大根堆最后一个数交换位置,然后大根堆大小减一
            swap(arr, 0, --heapSize);
//          让交互到0位置喜爱那个对较小的数下沉,继续形成大根堆。
            heapify(arr, 0, heapSize);
        }
    }

    private static void heapify(int[] arr, int index, int heapSize) {
//        大根堆父节点的左叶子结点
        int left = index * 2 + 1;
//        判断左儿子是否越界
        while ( left < heapSize ) {
//            判断父节点的左儿子在没有越界的情况下谁最大,拿到数组下标,
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
//            判断左右儿子中最大值和父节点谁最大,拿到最大值下标
            largest = arr[index] > arr[largest] ? index : largest;
            if (largest == index) {
                break;
            }
//            交换父节点和左右儿子中的最大值
            swap(arr, largest, index);
//            将左右儿子最大值下标赋给父节点
            index = largest;
//            赋值后父节点的左儿子
            left = index * 2 + 1;
        }
    }

    private static void heapInsert(int[] arr, int index) {
//        当index位置的这个值大于它的父节点的时候需要上浮,最终形成大根堆
        while ( arr[index] > arr[(index - 1) / 2] ) {
//            如果大于交换位置
            swap(arr, index, (index - 1) / 2);
//            更新节点,把父节点更新为当前节点,继续循环
            index = (index - 1) / 2;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static void printArr(int[] arr) {
        for (int i: arr){
            System.out.print(i+",");
        }
    }
}