快速排序-归并排序-堆排序

十大排序动图

快速排序优化

数组取标pivot,将小的元素放在pivot左边,大元素在右侧,然后依次对右边的子数组继续快排,以达到整个序列有序

public class QuickSort {
    public static void quickSort(int[] array, int beain, int end) {
        if (beain >= end) return;
        int pivot = partition1(array, beain, end);
        quickSort(array, beain, pivot - 1);
        quickSort(array, pivot + 1, end);
    }

    private static int partition1(int[] array, int beain, int end) {
        int pivot = end;//标杆位置
        int counter = beain;
        for (int i = beain; i < end; i++) {
            if (array[i] < array[pivot]) {
                int temp = array[counter];
                array[counter] = array[i];
                array[i] = temp;
                counter++;
            }
        }
        int temp = array[pivot];
        array[pivot] = array[counter];
        array[counter] = temp;
        return counter;
    }
}

归并排序

分治:

1. 把长度为n的输入序列分为两个长度为n/2的子序列
2. 把这两个子序列分别采用归并排序
3. 将两个排序好的子序列合并为一个最终的排序序列

public class MergeSort {
    public static void mergeSort(int[] array, int left, int right) {
        if (right <= left) return;
        int mid = (left + right) >> 1;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];//中间数组
        int i = left, j = mid - 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }
        while (i <= mid) temp[k++] = array[i++];
        while (j <= right) temp[k++] = array[j++];
        for (int l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

堆排序

堆排序详解

堆排序–堆插入o(logN) 取最大值最小O(1)

1. 数组元素依次简历小顶堆
2. 依次取堆顶元素,并删除

平均时间复杂度O(nlogn)

最好情况 O(nlogn)

最坏情况 O(nlogn)

空间复杂度 O(1)

排序方式 in-place

稳定性 不稳定

package com.nie.Bzhan.tree;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class BinaryTreeDemo {

    public static void main(String[] args) {
        int arr[] = {4, 6, 8, 5, 9};
        Date date = new Date();
        SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:sss");
        System.out.println(format.format(date));
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int arr[]) {
        int temp = 0;
        System.out.println("堆排序");

        //将无序序列构建成一个堆,  大堆 或者小堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length  - 1; j > 0; j--) {
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
    }


    //降一个数组(二叉树) 调整为一个大顶堆

    /**
     * @param arr    待调整的数组
     * @param i      非叶子节点在数组中索引
     * @param length 表示对多少和元素的继续调整  length在逐渐减少
     */
    public static void adjustHeap(int arr[], int i, int length) {
        int temp = arr[i];//先取出当前的元素的值,保存在临时变量中
        //开始调整
        //说明
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                //说明左子节点的值小于右子节点
                k++;
            }
            if (arr[k] > temp) {//如果子节点大于夫节点
                arr[i] = arr[k];//把较大的值赋给当前节点
                i = k;//!! i指向k 继续循环比较
            } else {
                break;//!
            }
        }
        //当for循环结束后 我们已经将以i位父节点的树的最大值,放在了顶部
        arr[i] = temp;//将temp值放在调整后的位置

    }
}