七大排序算法

public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        //大于号 是预防1 2 3 4 5 6,直接没有左树或没有右树
        if (start >= end){
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    //找基准
    //Hoare版本
    private static int partition(int[] array,int left,int right){
        int i = left;
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot){
                right--;
            }
            //right下标的值小于pivot

            while (left < right && array[left] <= pivot){
                left++;
            }
            //left下标的值大于pivot
            swap(array,left,right);
        }
        //循环走完,left和right相遇
        //交换 和原来的left
        swap(array,left,i);
        //返回基准
        return left;
    }

时间复杂度:O(n*logn)

此时间复杂度不是最坏情况下的时间复杂度,最坏情况下是有序的情况下,此时树的高度是n,时间复杂度是O(n^2),空间复杂度也变成了O(n).

空间复杂度:O(logn)

稳定性:不稳定

挖坑法找基准

private static int partition(int[] array,int left,int right){
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot){
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        //返回基准
        return left;
    }

挖坑法是找到合适的值直接交换.

需要注意的是挖坑法和hoare找基准的结果是不一样的但是最终都是有序的.

快速排序优化

当数据有序的时候,快速排序的时间复杂度达到最大,而且空间复杂度也会随之改变.

三数取中法

为了使二叉树的划分尽可能的均匀,我们在left,mid,right三个数中,取出中间大的值,来作为key(left).

比如1 2 3 4 5,如果不采用三数取中法,那么1作为key走下来,left和right在1相遇,基准就是1,此时划分的就是单分支的树;如果采用三数取中,将数组顺序调整为 3 2 1 4 5,3作为key,走下来,left和right在中间位置相遇,将3和1交换,变为 1 2 3 4 5,虽然又变回去了,但是此时的基准在中间位置3的地方,此时二叉树划分的将更加均匀.

public static void quick(int[] array,int start,int end){
        //大于号 是预防1 2 3 4 5 6,直接没有左树或没有右树
        if (start >= end){
            return;
        }
        //在找基准之前,进行三数取中的优化,尽量去解决划分不均匀的问题.
        //在left,mid,right三个数中找到中间大的数字做key
        int index = findMidValueOfIndex(array, start, end);
        swap(array,start,index);

        int pivot = partitionHoare(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    //3个数中取中位数
    private static int findMidValueOfIndex(int[] array,int start,int end){
            int minIndex = (start+end)/2;
            if (array[start] > array[end]){
                if (array[minIndex] > array[start]){
                    return start;
                }else if (array[minIndex] < array[end]){
                    return end;
                }else {
                    return minIndex;
                }
            }else {
                if (array[minIndex] > array[end]){
                    return end;
                }else if (array[minIndex] < array[start]){
                    return start;
                }else {
                    return minIndex;
                }
            }
    }

我们除了采取这种优化之外,还可以在快速排序递归到小区间的时候,采用插入排序.

因为插入排序在数据趋于有序并且数据量小的时候,排序的速度非常快.

非递归实现快速排序

 public static void quickSort2(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length-1;
        int pivot = partition(array,start,end);
        //1.判断左边是不是有2个元素
        if(pivot > start+1) {
            stack.push(start);
            stack.push(pivot-1);
        }
        //2.判断右边是不是有2个元素
        if(pivot < end-1) {
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end);
            //3.判断左边是不是有2个元素
            if(pivot > start+1) {
                stack.push(start);
                stack.push(pivot-1);
            }
            //4.判断右边是不是有2个元素
            if(pivot < end-1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }

归并排序

先分解,后合并.

public static void mergeSort1(int[] array) {
        mergeSortChild(array,0,array.length-1);
    }

    private static void mergeSortChild(int[] array,int left,int right) {
        if(left == right) {
            return;
        }
        int mid = (left+right) / 2;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }

    private static void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmpArr = new int[right-left+1];
        int k = 0;//表示tmpArr 的下标
        while (s1 <= e1  && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //tmpArr当中 的数据 是right  left 之间有序的数据
        for (int i = 0; i < k; i++) {
            array[i+left] = tmpArr[i];
        }
    }

时间复杂度:O(n*logn).

空间复杂度:O(n)

稳定性:稳定

非递归的归并排序

 public static void mergeSort(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i += gap*2) {
                int left = i;
                int mid = left + gap -1;
                int right = mid+gap;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }