排序算法

image.png

冒泡排序

public void BubbleSort(int[] arr) {
        for(int i = 0;i < arr.length-1; i++){//冒泡趟数
            for(int j = arr.length-i-1; j >= 0; j--){
                if(arr[j] > arr[j+1]){//从小到大
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

简单选择排序

public void selectSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[min] > arr[j]) {//从小到大
                    min = j;
                }
            }
            
            if(min != i) {
                swap(arr, i, min); //交换
            }
        }
    }

直接插入排序

public void insertSort(int[] arr) {
        for(int i = 1; i < arr.length; i++){
            if (arr[i] < arr[i-1]) {
                int temp = arr[i];
                int j;
                for (j = i-1; j >= 0; j--) {
                    if (arr[j] > temp) {//从小到大
                        arr[j+1] = arr[j];
                    }else {
                        break;
                    }
                }
                arr[j+1] = temp;
            }
        }
    }

堆排序

堆排序算法：

1. 构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
2. 将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。
3. 重新构建堆。
4. 重复2~3，直到待排序列中只剩下一个元素(堆顶元素)。

    private void heapSort(int[] arr) {
        //创建堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }

        //调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            //将堆顶元素与末尾元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            //重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }

    private void adjustHeap(int[] arr, int parent, int length) {
        int temp = arr[parent];
        for(int j = 2*parent+1; j < length; j = j*2+1){
            //沿着关键字较大的孩子结点向下筛选，有孩子大于左孩子
            if (j+1 < length && arr[j] < arr[j+1]) {  
                j++;
            }
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if(arr[j] <= temp){
                break;
            }
            arr[parent] = arr[j];
            parent = j;
        }
        arr[parent] = temp;
    }

归并排序

public int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }

快速排序

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotkey = sort(arr, low, high);
            quickSort(arr, low, pivotkey - 1);
            quickSort(arr, pivotkey + 1, high);
        }
    }


    public static int sort(int[] arr, int i, int j) {
        // 基准数
        int temp = arr[i];
        while(i < j) {
            // 先从右边开始往左找，直到找到比temp值小的数
            while(arr[j] >= temp && i < j) {
                j--;
            }
            arr[i] = arr[j];

            // 再从左往右边找，直到找到比temp值大的数
            while(arr[i] <= temp && i < j) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        return i;
    }