【笔记-排序】

作者: 杂学小生 | 来源:发表于2021-03-18 20:06 被阅读0次

排序	平均时间复杂度	最差时间复杂度	最好时间复杂度	稳定性
冒泡排序	O(n^2)	O(n^2)	O(n)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	不稳定
快速排序	O(n*logn)	O(n^2)	O(n*logn)	不稳定
插入排序	O(n^2)	O(n^2)	O(n)	稳定
希尔排序	O(n^1.3)	O(n^2)	O(n)	不稳定
堆排序		O(n*logn)	O(n)	不稳定
归并排序	O(n*logn)	O(n*logn)	O(n*logn)	稳定

稳定性：相同元素，排序后，相对位置的变化情况，不变则稳定

公共代码

    //交换
    public static void swap(int[] array, int i, int j) {
        if (i == j) {
            return;
        }
        array[i] ^= array[j];
        array[j] ^= array[i];
        array[i] ^= array[j];
    }

    public static void main(String[] args) {
        int[] array = new int[10];
        for (int i = 0; i < 10; i++) {
            int num = ThreadLocalRandom.current().nextInt(100);
            array[i] = num;
        }
//        array[1] = array[0];
        System.out.println("原始：" + JsonManager.getGson().toJson(array));

        int[] copyArray = Arrays.copyOf(array, array.length);
        bubbleSort(copyArray);
        System.out.println("冒泡：" + JsonManager.getGson().toJson(copyArray));

        copyArray = Arrays.copyOf(array, array.length);
        quickSort(copyArray, 0, copyArray.length - 1);
        System.out.println("快排：" + JsonManager.getGson().toJson(copyArray));
    }

冒泡排序

第i个元素和后面的元素一一比较，比第i个元素小的则互换
比较次数：顺序n次，逆序(n-1)+(n-2)+...+1=(1+n-1)(n-1)/2=n(n-1)/2
交换次数：顺序0次，逆序n*(n-1)/2

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean swap = false;
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    swap(array, i, j);
                    swap = true;
                }
            }
            if (!swap) {
                //一次到底后，没有交换过，提前结束，有这一步，冒泡排序最好情况才能达到O(n)
                return;
            }
        }
    }

选择排序

在数组中找到最小的元素放到起始位置，剩余的在继续找最小的元素放到已排序的末尾，一直到排序完
比较次数：顺序=逆序=(n-1)+(n-2)+...+1=(1+n-1)(n-1)/2=n(n-1)/2
交换次数：顺序0次，逆序n次

  public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            swap(array, i, min);
        }
    }

快速排序（包含重复元素）

分治算法的思想

将某一个元素作为基准元素，然后将数组分成两边，左侧的数据比基准元素小，右侧的比基准元素大
然后将两侧的数组递归重复第一步

左右指针所对应的元素重复时（等于基准元素），将左指针向右移动一位，继续比较，可使快速排序支持重复元素
最坏情况是每次的基准为最大或者最小数字，那么所有数都划分到一侧去了时间复杂度为O(n^2)
不稳定是基准值不保证都能在中间

  public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = array[left];
        int leftIndex = left;
        int rightIndex = right;
        while (leftIndex < rightIndex) {//当左>=右时结束
            while (leftIndex < rightIndex && array[leftIndex] < mid) {//从左向右一直找到>=基准点
                leftIndex++;
            }
            while (leftIndex < rightIndex && array[rightIndex] > mid) {//从右向左一直找到<=基准点
                rightIndex--;
            }
            //重复元素，左索引进1再比较，左侧将含有mid的值
            if (leftIndex + 1 <= rightIndex && array[leftIndex] == array[rightIndex]) {
                leftIndex++;
            } else {
                swap(array, leftIndex, rightIndex);//交换
            }
        }
        quickSort(array, left, leftIndex - 1);
        quickSort(array, leftIndex + 1, right);
    }

插入排序

默认第一个为有序数组
取下一个新元素，从有序数组后往前比较，小于新元素的往后移，直到找到大于新元素，然后在它后面新元素，一直重复排完所有
比较次数：顺序n次，逆序1+2+...+(n-1)=n*(n-1)/2
交换词素：顺序=逆序=n次

    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int preIndex = i - 1;
            int value = array[i];
            while (preIndex >= 0 && value < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = value;
        }
    }

希尔排序

初始给定一个步进长度step（一般是数组的一半），则数组可划分为[[0, step, step+step...],[1, 1+step, 1+step+step...]......[n, n+step, n+step+step...]]
依次对分组后的数组进行插入排序
都排序好后步进长度step在缩减一半，重新划分数组，在依次对分组后的数组进行插入排序，直到步进长度step=1
步进长度为1的时候，就是最原始的插入排序，但由于之前的分组排序，所以进行原始插入排序，移动的数据量少，效率高

    //写法一
    public static void shellSort(int[] array) {
        int len = array.length;
        int step = len / 2;
        while (step > 0) {
            //【0,   step,   step+step】
            //【1,   1+step, 1+step+step】
            int i = 0;
            //分组，一组组进行插入排序
            while (i < step) {
                for (int j = i + step; j < array.length; j = j + step) {
                    int preIndex = j - step;
                    int value = array[j];
                    while (preIndex >= 0 && value < array[preIndex]) {
                        array[preIndex + step] = array[preIndex];
                        preIndex = preIndex - step;
                    }
                    array[preIndex + step] = value;
                }
                i++;
            }
            step /= 2;
        }
    }

    //写法二
    public static void shellSort2(int[] array) {
        int len = array.length;
        int step = len / 2;
        while (step > 0) {
            //【i,   i+step,   i+step+step】
            //【i+1, i+1+step, i+1+step+step】
            //每组交替执行，先执行第一组的step位，在执行第二组1+step...直到所有组执行了一次，在步进后一个段位，重复各组
            for (int i = step; i < array.length; i++) {
                int preIndex = i - step;
                int value = array[i];
                while (preIndex >= 0 && value < array[preIndex]) {
                    array[preIndex + step] = array[preIndex];
                    preIndex = preIndex - step;
                }
                array[preIndex + step] = value;
            }
            step /= 2;
        }
    }

堆排序

将数组看成一个完全二叉树
构建一个任意节点都大于等于子节点完全二叉树
完全二叉树有以下性质：
根节点 = 0，节点 = i，节点数量 = n，则：

节点的左孩子 = 2i+1
节点的右孩子 = 2i+2
节点的父亲 = (i-1)/2
最后的非叶子节点 = 最后的叶子节点的父亲 = (n-1)/2

构建堆的复杂度

深度k = log(n)，要处理的节点数 =n/2
最好的情况是，不交换或交换后不用处理子节点
 <= n/2 
=> O(n)
最坏的是交换后还要处理子节点
节点i 的层数 = log(i)，节点i 的处理次数 = k - log(i) = log(n) - log(i)
= log(n) -log(1)+...+log(n) -log(n)=n * log(n) - log(!n)=log(n^n / !n)
=>不会简化，换下一种解法

第i层有节点数 = 2^(i-1)，每个节点需要处理次数 = (k-i)
=> 第i层需要处理的次数 =  2^(i-1)*(k-i)
S = 2^(1-1)*(k-1) + 2^(2-1)*(k-2) + ... + 2^(k-1)*(1) 
乘2错位
2S =                       2^(2-1)*(k-1) + ....+ 2^(k-1)*(2) + 2^k*(1) 
两个式相减
S = -2^(1-1)*(k-1) + 2^(2-1) + ...... + 2^(k-1) + 2^k*(1)
   = 2+2^2+...+2^(k-1)-(k-1)
再乘2错位
2S =   2^2+...+2^(k-1)+2^k - 2(k-1)
再两个式相减
S = 2^k - 2 -(k-1) =  2^k - k-1
=>2^(log(n)) - log(n) -1 = n - logn -1
=>O(n)

调整堆的复杂度

循环次数：n-1，剩一个的时候不执行
每次都是从根节点往下，调整次数为树的层数-1，且每次调整都会少个节点
= log(n)-1 + log(n-1)-1 + log(n-2)-1 +...+ log(2)-1 = log(2)+...+log(n) - (n-1)
=log(!n)-n+1
完了又不会简化，和n*log(n)比较下吧
n*logn=log(n^n) > log(!n)
O(n*log(n)) > O(log(!n))
所以起码复杂度不会超过O(n*log(n))

整个算法最复杂的复杂度为O(nlog(n))+O(n) = O(nlog(n))

 //调整堆，使节点k的子树，k最大
    public static void adjustHeap(int[] array, int k, int length) {
        int parent = k;
        int child = 2 * parent + 1;

        while (child < length) {
            int rightChild = child + 1;
            if (rightChild < length && array[child] < array[rightChild]) {
                child = rightChild;
            }
            if (array[parent] >= array[child]) {
                break;
            }
            swap(array, parent, child);

            parent = child;
            child = 2 * parent + 1;
        }
    }

    //堆排序
    public static void heapSort(int[] array) {
        int len = array.length;
        //构建堆
        for (int i = (len - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i, len);
        }

        for (int i = len - 1; i > 0; i--) {
            swap(array, 0, i);
            adjustHeap(array, 0, i);
        }
    }

归并排序

自顶向下（先代码分组成一个个数组，再一个个合并）

    public static int[] mergeSort(int[] array, int start, int end) {
        if (start == end) {
            return new int[]{array[start]};
        }
        //分组
        int mid = (start + end) / 2;
        int[] left = mergeSort(array, start, mid);
        int[] right = mergeSort(array, mid + 1, end);

        //合并
        int i = 0, j = 0, rIndex = 0;
        int[] r = new int[left.length + right.length];
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                r[rIndex++] = left[i++];
            } else if (left[i] > right[j]) {
                r[rIndex++] = right[j++];
            } else {
                r[rIndex++] = left[i++];
                r[rIndex++] = right[j++];
            }
        }

        if (j >= right.length) {
            while (i < left.length) {
                r[rIndex++] = left[i++];
            }
        }
        if (i >= left.length) {
            while (j < right.length) {
                r[rIndex++] = right[j++];
            }
        }
        return r;
    }

自底向上（主观上将他们分成一个个了，代码直接对相邻的数组合并）

    public static void mergeSort2(int[] array) {
        int len = array.length;
        //i为间隔
        for (int i = 1; i < len; i *= 2) {
            int start = 0;
            int end = start + 2 * i;
            //两两合并相同长度的数组
            while (end < len) {
                merge(array, start, start + i, end);
                start = end;
                end = start + 2 * i;
            }
            //剩余大于一个间隔，但不足两个间隔长度的
            if (start + i < len) {
                merge(array, start, start + i, len);
            }
        }
    }

    public static void merge(int[] array, int start, int mid, int end) {
        int[] r = new int[end - start];
        int i = start, j = mid, rIndex = 0;
        while (i < mid && j < end) {
            if (array[i] < array[j]) {
                r[rIndex++] = array[i++];
            } else if (array[i] > array[j]) {
                r[rIndex++] = array[j++];
            } else {
                r[rIndex++] = array[i++];
                r[rIndex++] = array[j++];
            }
        }
        if (j >= end) {
            while (i < mid) {
                r[rIndex++] = array[i++];
            }
        }
        if (i >= mid) {
            while (j < end) {
                r[rIndex++] = array[j++];
            }
        }
        //拷贝回原数组
        int k = 0;
        while (k < r.length) {
            array[start++] = r[k++];
        }
    }

【笔记-排序】

公共代码

冒泡排序

选择排序

快速排序（包含重复元素）

插入排序

希尔排序

堆排序

归并排序

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读