精华内容
下载资源
问答
  • 排序算法有多种,常用的排序算法有冒泡排序、插入排序、选择排序、快速排序、堆排 序、归并排序、希尔排序、二叉树排序、计数排序等。在所有的排序算法中,冒泡排序是最重要的种排序算法。 冒泡排序:假设排序小...

    冒泡排序

    排序算法有多种,常用的排序算法有冒泡排序、插入排序、选择排序、快速排序、堆排 序、归并排序、希尔排序、二叉树排序、计数排序等。在所有的排序算法中,冒泡排序是最重要的一种排序算法。

    冒泡排序:假设排序小聪、小美、小黑、小莉、小薇的身高,他们的身高如图所示。冒泡排序的算法是通过对相邻元素的大小进行比较,每一轮将一个最小或最大的数放到队列的最后面,冒泡排序算法如图所示。

                                                                      

                                                                                     五个人的身高
     
                                                         
                                                         
     

    从键盘上输入 5 名学生的身高,使用冒泡排序算法,按照从高到低排序输出每一个学生的身高。

    public static void main(String[] args) {
        java.util.Scanner input = new java.util.Scanner(System.in);
        // 存储五个人的身高
        int[] height = new int[5];
        // 循环输入五个人的身高
        for (int i = 0; i < height.length; i++) {
            System.out.println("请输入第" + (i + 1) + "个新兵的身高:");
            height[i] = input.nextInt();
        }
        // 定义临时变量
        int temp;
        // 进行冒泡排序
        for (int i = 0; i < height.length - 1; i++) { // 外循环控制比较多少轮
            for (int j = 0; j < height.length - 1 - i; j++) { // 内循环控制每轮比较多少次
                if (height[j] > height[j + 1]) {
                // 进行两数交换
                temp = height[j];
                height[j] = height[j + 1];
                height[j + 1] = temp;
                } 
            } 
        }
        // 将排序后结果进行输出
        System.out.println("从低到高排序后的输出:");
        for (int i = 0; i < height.length; i++) {
        System.out.println(height[i]);
    }

    结果如下

     
     
     
     
     
     
    展开全文
  • 、排序算法系列目录说明冒泡排序(Bubble Sort)插入排序(Insertion Sort)希尔排序(Shell Sort)选择排序(Selection Sort)快速排序(Quick Sort)归并排序(Merge Sort)堆排序(Heap Sort)...

    前几回,我们已经对冒泡排序、直接插入排序、希尔排序、选择排序、快速排序、归并排序、堆排序做了说明分析。本回,将对计数排序进行相关说明分析。


    一、排序算法系列目录说明

    • 冒泡排序(Bubble Sort)
    • 插入排序(Insertion Sort)
    • 希尔排序(Shell Sort)
    • 选择排序(Selection Sort)
    • 快速排序(Quick Sort)
    • 归并排序(Merge Sort)
    • 堆排序(Heap Sort)
    • 计数排序(Counting Sort)
    • 桶排序(Bucket Sort)
    • 基数排序(Radix Sort)

    二、计数排序(Counting Sort)

    计数排序(Counting sort)是一种稳定的线性时间排序算法。

    1. 基本思想

    计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

    用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),然后进行分配、收集处理:

    分配。扫描一遍原始数组,以当前值-minValue作为下标,将该下标的计数器增1。
    收集。扫描一遍计数器数组,按顺序把值收集起来。

    2. 实现逻辑

    ① 找出待排序的数组中最大和最小的元素
    ② 统计数组中每个值为i的元素出现的次数,存入数组C的第i项
    ③ 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
    ④ 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

    3. 动图演示

    0159f88b46aa120ba549a00d2584ddbf.gif
    计数排序演示

    举个例子,假设有无序数列nums=[2, 1, 3, 1, 5], 首先扫描一遍获取最小值和最大值,maxValue=5, minValue=1,于是开一个长度为5的计数器数组counter

    (1) 分配
    统计每个元素出现的频率,得到counter=[2, 1, 1, 0, 1],例如counter[0]表示值0+minValue=1出现了2次。(2) 收集
    counter[0]=2表示1出现了两次,那就向原始数组写入两个1,counter[1]=1表示2出现了1次,那就向原始数组写入一个2,依次类推,最终原始数组变为[1,1,2,3,5],排序好了。

    4. 复杂度分析

    平均时间复杂度:O(n + k)
    最佳时间复杂度:O(n + k)
    最差时间复杂度:O(n + k)
    空间复杂度:O(n + k)

    当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。。在实际工作中,当k=O(n)时,我们一般会采用计数排序,这时的运行时间为O(n)。

    计数排序需要两个额外的数组用来对元素进行计数和保存排序的输出结果,所以空间复杂度为O(k+n)。

    计数排序的一个重要性质是它是稳定的:具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序是相同的。也就是说,对两个相同的数来说,在输入数组中先出现的数,在输出数组中也位于前面。

    计数排序的稳定性很重要的一个原因是:计数排序经常会被用于基数排序算法的一个子过程。我们将在后面文章中介绍,为了使基数排序能够正确运行,计数排序必须是稳定的。

    5. 代码实现

    C版本:

    // 计数排序(C)
    

    Java版本:

    // 计数排序(Java)
    

    6. 优化改进

    场景分析:举个极端的例子:如果排序的数组有200W个元素,但是这200W个数的值都在1000000-1000100,也就说有100个数,总共重复了200W次,现在要排序,怎么办?

    这种情况排序,计数排序应该是首选。但是这时候n的值为200W,如果按原来的算法,k的值10001000,但是此时c中真正用到的地方只有100个,这样对空间造成了极大的浪费。

    改进思路:针对c数组的大小,优化计数排序

    改进代码:

    // 计数排序优化(Java)
    

    三、总结

    计数算法只能使用在已知序列中的元素在0-k之间,且要求排序的复杂度在线性效率上。 Â 计数排序和基数排序很类似,都是非比较型排序算法。但是,它们的核心思想是不同的,基数排序主要是按照进制位对整数进行依次排序,而计数排序主要侧重于对有限范围内对象的统计。基数排序可以采用计数排序来实现。

    下一篇预告:桶排序(Bucket Sort)。欲知详情,且听下回分解。


    PS: 更多资源,欢迎关注微信公众号:developer1024

    e00ca684eec4218ab39fce17b3bbe983.png
    展开全文
  • 之前的文章中,我们介绍了Merge Sort算法,其时间复杂度虽然是线性对数的,但是由于辅助数组的存在,致使其空间复杂度为线性的。那有没有种排序算法,能够在...归并排序是先两个子数组分别排序,然后将两个有序...

    73a5df2b826c8ba2819c3e006b33bbbb.png

    之前的文章中,我们介绍了Merge Sort算法,其时间复杂度虽然是线性对数的,但是由于辅助数组的存在,致使其空间复杂度为线性的。那有没有一种排序算法,能够在时间、空间上都表现较为良好均衡呢?答案是有的,这就是在各种库中广泛使用的 Quick Sort 快速排序,简称"快排"

    切分过程详解

    切分目的

    快速排序,和归并排序算法一样,亦运用了分治的思想在里面。归并排序是先对两个子数组分别排序,然后将两个有序的子数组归并在一起以使整个数组有序;而快速排序虽然也是先将待排序数组通过切分操作一分为二的分为两个子数组,但是当这两个子数组分别排序、有序之后,整个数组即已经是排序完成的了。下图即是一个将数组切分后再分别对子数组升序排序的图解

    75ff60c57ae4b8a4f65e3991c4dfe878.png

    结合上图可以看出,其切分时,先从待排序数组中随机选取一个元素(记为切分元素),当切分操作完成时,必须保证数组中切分元素的左侧元素均不大于它、切分元素的右侧元素均不小于它。即,通过快速排序的切分过程,我们实际上是完成了对切分元素的排序工作。故,当左、右两半部分元素分别有序后(可通过递归调用切分实现),整个数组自然而然就是有序状态

    切分原理

    从上文我们知道了切分的作用及目的,现在我们结合下图来看看切分的原理。一般地,我们随机地使用数组的第一个元素作为切分元素Partition Element——即切分后排序完成的元素。然后从数组的左端开始向右扫描,直到找到一个大于等于切分元素的元素;再从数据的右端开始向左扫描,直到找到一个小于等于切分元素的元素;然后交换array[i]、array[j]这两个元素。重复上述的"扫描-交换"过程,即可保证:游标i左侧的元素均不大于切分元素Partition Element、游标j右侧的元素均不小于切分元素Partition Element。当两个游标i、j相遇时,我们只需将切分元素array[start]与左子数组最右侧的元素(a[j])交换,即完成切分,此时切分元素array[start]即完成排序,位置索引即为j

    c30701b00bde3437781b90a766aab7e2.png

    Java 实现

    这里以Java为例实现了一个用于数组array升序的切分方法partition()

    /**
         * 对数组指定范围的元素进行切分操作,并返回切分点 j
         * 使之满足 array[start]~array[j-1] <= array[j] <= array[j+1]~array[end]
         * @param array 待排序数组
         * @param start 起点
         * @param end 终点
         * @return
         */
        private static int partition(int[] array, int start, int end) {
            int i = start;      // 左游标
            int j = end + 1;    // 右游标
            int partitionElement = array[start];    //  切分元素
    
            while (true) {
                // 左游标从左向右扫描, 查找不小于切分元素的元素
                while ( array[++i] < partitionElement ) {
                    if( i>=end ) {  // 边界检查
                        break;
                    }
                }
                // 右游标从右向左扫描, 查找不大于切分元素的元素
                while ( array[--j] > partitionElement ) {
                    if( j<=start ) {    // 边界检查
                        break;
                    }
                }
                // 左、右游标相遇,即扫描结束
                if( i>=j ) {
                    break;
                }
                swap(array, i, j);
            }
            swap(array, start, j);  // 将切分元素放入正确的位置, 即 array[j] 排序完成
            return j;   // 返回切分点, array[start]~array[j-1] <= array[j] <= array[j+1]~array[end]
        }
        /**
         * 交换数组元素
         * @param array
         * @param indexA
         * @param indexB
         */
        private static void swap(int[] array, int indexA, int indexB) {
            int temp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = temp;
        }

    有些人看完代码会有一个疑问,为什么"扫描-交换"过程完成之后,左子数组最右侧的元素位置是array[j],即,切分元素的排序位置为什么就是j呢?这里,我们分别以切分元素为最小值、最大值、非最值三种情况为例,计算一下"扫描-交换"完成后i、j游标的数值,通过观察下图即可看出切分元素的排序位置恰好是j

    7cb43b7f1284077029ae1db878ddf63f.png

    基础快速排序

    算法思想

    上文我们详细分析了快速排序中的关键操作——切分。现在,我们来看看快速排序算法的思想:要对数组排序,需先对欲排序数组进行切分,获取切分点(记为j),根据切分点即可将原数组一分为二:左子数组(array[start]~array[j-1])、右子数组(array[j+1]~array[end]),再通过递归的方式分别对左、右子数组进行切分、排序。即可完成对整个数组的排序

    Java 实现

    现通过Java代码实现快速排序(partition方法实现在上文已给出,此处不再赘述)

    /**
     * 快速排序
     */
    public class QuickSort {
        /**
         * 升序排列
         */
        public static void sort1() {
            int[] array = getTestCase();
            int size = array.length;
    
            System.out.println("before sort: " + Arrays.toString(array) );
    
            sort(array, 0, size-1);
    
            System.out.println("after sort: " + Arrays.toString(array) );
        }
    
        /**
         * 对数组指定范围的元素进行升序排列
         * @param array 待排序数组
         * @param start 起点
         * @param end 终点
         */
        private static void sort(int[] array, int start, int end) {
            if( start >= end ) {
                return;
            }
            int partitionIndex = partition(array, start, end); // 切分并返回切分点j, 此时array[j]排序完成
            sort( array, start, partitionIndex-1 ); // 对左子数组 array[start]~array[j-1] 进行排序
            sort( array, partitionIndex+1, end);    // 对右子数组 array[j+1]~array[end] 进行排序
        }
    
        /**
         * 获取测试用例
         */
        private static int[] getTestCase() {
            int[] caseArray = {3,7,10,1,4,9,8,5,2,6};
            return caseArray;
        }
    }

    测试结果:

    17f5facc9c4abcf55cfab13479b313f1.png

    特点

    | 时间复杂度(average) | 时间复杂度(worst) | 时间复杂度(best) | 空间复杂度 | 稳定性 | | :-: | :-: | :-: | :-: | :-: | | $O(N log N)$ | $O(N^2)$ | $O(N log N)$ | $O(log N)$ | 不稳定 |

    从上表可以看出快速排序的平均时间复杂度是线性对数级别,而空间复杂度是对数级别,较我们之前介绍的排序算法而言,时间、空间耗费均较为平衡。故在有些语言的默认排序方法即是通过快排实现

    值得一提的是,该算法非常脆弱。因为切分后理想的切分点应是在正中间的位置,而如果待排序数组是有序的。那么每次切分时,再选数组中第一个元素作为切分元素,则其切分点位置恰好都是在数组的两端,此时既为最坏的情况——即时间复杂度为平方级别,为最大程度避免出现该情况。在实际应用中,可以通过以下两点进行优化:

    • 保证随机性 : 排序前先将元素打乱;每次任意地选取不同位置上的元素作为切分元素
    • 处理与切分元素相等的元素情况 : 在上文的"扫描-交换"过程,左游标是遇到一个大于等于切分元素的元素停下;右游标是遇到一个小于等于切分元素的元素停下。虽然这样处理可能会导致一些不必要的元素交换,但可以一定程度上避免切分点过于靠近数组的两端

    基于三向切分的快速排序

    当待排序元素中包含大量重复元素时,基础快速排序算法实际上会对重复元素每一个均会进行切分、排序。而如果我们在切分的过程中,按小于、等于和大于切分元素这三个分类来切分,可以大大提高快速排序的效率,可将时间复杂度从线性对数降至线性级别

    原理

    我们通过游标i从左到右遍历整个数组,同时分别维护一个左游标lt、右游标gt。使得左游标lt左侧元素(array[start] ~ array[lt-1])均小于切分元素,右游标gt右侧元素(array[gt+1] ~ array[end])均大于切分元素。而在 array[lt] ~ array[i-1] 中的元素均等于切分元素,array[i] ~ array[gt] 中的元素则待遍历、分类。三向切分图解如下图所示,当三向切分完成时,array[lt] ~ array[gt] 中的元素均等于切分元素,即绿色部分已经排序完成,只需对蓝色部分(小于切分元素)、黄色部分(大于切分元素)递归完成排序即可

    f22fec79c034c19b74bb87f8d91a070c.png

    Java 实现

    现通过Java代码实现基于三向切分的快速排序

    /**
     * 快速排序
     */
    public class QuickSort {
        /**
         * 升序排列(使用三向切分)
         */
        public static void sort2() {
            int[] array = getTestCase();
            int size = array.length;
    
            System.out.println("before sort: " + Arrays.toString(array) );
    
            sortBy3Way(array, 0, size-1);
    
            System.out.println("after sort: " + Arrays.toString(array) );
        }
        /**
         * 三向切分
         * @param array
         * @param start
         * @param end
         */
        private static void sortBy3Way(int[] array, int start, int end) {
            if( start >= end ) {
                return;
            }
    
            int partitionElement = array[start];    //  切分元素
            int lt = start;     // 游标 lt 左侧元素 均小于 切分元素
            int gt = end;       // 游标 gt 右侧元素 均大于 切分元素
             int i = start+1;    // 遍历游标
            // 三向切分,使得下式结果成立
            // array[start]~array[lt-1] < array[lt]~array[gt] = partitionElement < array[gt+1]~array[end]
            while ( i<=gt ) {
                if( array[i] > partitionElement) {  // 大于切分元素,则将其放置在 gt 游标右侧
                    swap(array, i, gt);
                    gt--;
                } else if (array[i] < partitionElement) {   // 小于切分元素,则将其放置在 lt 游标左侧
                    swap(array, i, lt);
                    lt++;
                    i++;
                } else {    // 等于切分元素, 则无需改变其位置
                    i++;
                }
            }
            sortBy3Way(array, start, lt-1);     // 对左子数组 array[start]~array[lt-1] 进行排序
            sortBy3Way(array, gt+1, end);       // 对右子数组 array[gt+1]~array[end] 进行排序
        }
        /**
         * 获取测试用例
         */
        private static int[] getTestCase() {
            int[] caseArray = {5,4,5,7,1,5,5,8};
            return caseArray;
        }
    }

    测试结果:

    c612a5807b4972f0d0d712825e6b84a1.png

    特点

    ad578141f55154eab5a00c14b15a930e.png

    参考文献

    1. 算法(第4版) Robert Sedgewick、Kevin Wayne 著
    展开全文
  • 归并排序 树状数组 数组离散化 STL+二分离散化 树状数组求逆序 前言 也许有许多大佬看到这个标题,就会心生嘲笑,毕竟只是个小小的逆序嘛。 当然,这只是逆序而已。 我只是准备抛砖引玉,介绍一下本...

    计算逆序对问题    BZOJ    1266


    目录

    前言

    正文

    普通做法

    归并排序

    树状数组

    数组离散化

    STL+二分离散化

    树状数组求逆序对


    前言

    也许有许多大佬看到这个标题,就会心生嘲笑,毕竟只是一个小小的逆序对嘛。

    当然,这只是逆序对而已。

    我只是准备抛砖引玉,介绍一下本蒟蒻的一点点对树状数组的理解而已。

    如有不适,可以自行跳过

    正文

    题目描述

    设A[1..n]是一个包含N个数的数组。如果在i< j的情况下,有A[i] >a[j],则(i,j)就称为A中的一个逆序对。 例如,数组(3,1,4,5,2)的“逆序对”有 <3,1>,<3,2>,<4,2>,<<5,2> 共4个。

    输入

    第1行:1个整数N表示排序元素的个数。(1≤N≤100000)  第2行:N个用空格分开的整数,每个数小于100000。

    输出

    1行:仅一个数,即序列中包含的逆序对的个数

    样例输入

    3
    1 3 2

    样例输出

    1

    普通做法

    相信各位大神们对逆序对一定不陌生,所以可以直接跳过,当然,如果是跟我一样的同道中人新手们,可以详见:https://baike.baidu.com/item/%E9%80%86%E5%BA%8F%E5%AF%B9/11035554

    可以看出,这道题是可以用暴力双层循环求解的。

    #include <cstdio>
    int a[20], n, i, j, ans;
    int main (){
        scanf ("%d", &n);
        for (i = 1; i <= n; i++)
            scanf ("%d", &a[i]);
        for (i = 2; i <= n; i++){
            for (j = 1; j < i; j++){
                if (a[j] > a[i])
                    ans ++;
            }
        }
        printf ("%d\n", ans);
        return 0;
    }

    可是可以清楚地看出,这个程序的时间复杂度为O(n^2)的,这未免太大了一点吧。

    因此,这里将引入新的知识点——归并排序。

    归并排序

    在这里,如果运用了归并排序的思想,那么时间复杂度将会变成O(nlogn),这下时间就蹭蹭蹭的往下掉了。

    详见代码:

    #include<cstdio>
    #define MAXN 100000
    using namespace std;
    
    int n, a[MAXN + 5], b[MAXN + 5];
    long long inver;
    
    void merge_array (int l, int r, int mid){
        int x = l, y = l, z = mid + 1;
        while (x <= mid && z <= r){//排序,同时在计算逆序对
            if (a[x] <= a[z]){
                b[y++] = a[x++];
            }
            else{
                inver += mid - x + 1;
                b[y++] = a[z++];
            }
        }
        while (x <= mid)//如果说第一个序列还有元素,就直接插入进去
            b[y++] = a[x++];
        while (z <= r)//同上,即为第二个序列
            b[y++] = a[z++];
        for (int i = l; i <= r; ++i)//将有序的序列再赋值回去
            a[i] = b[i];
    }
    
    void mergesort (int l, int r){//归并排序,将数组二分成单个元素,再进行排序
        if (l >= r)
            return ;
        int mid = (l + r) / 2;
        mergesort (l, mid);
        mergesort (mid + 1, r);
        merge_array (l, r, mid);
    }
    
    template <typename T>//读入优化不解释
    void read (T &x){
        x = 0;
        char c = getchar ();
        while (c < '0' || c > '9')
            c = getchar ();
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
    }
    
    int main (){
        read (n);
        for (int i = 1; i <= n; ++i)
            read (a[i]);
        mergesort (1, n);
        printf ("%lld", inver);
    }
    

    在这里的read函数很简单,其实就跟scanf作用一样,唯一的好处就是可以提高读入的速度,相当于骗分神器

    当然,重点还是mergesort和merge_array了。

    mergesort其实就是将一个统一的数组一分为二,最后分成一个,然后再来进行合并。merge_array就是合并的sao操作,如果说左边的序列小于右边的序列,就可以直接把这个元素放到临时数组中。否则即相当于产生出了逆序对。

    因为如果这个数与另一个数成为了逆序对,那么他就将会跟后面的所有数都能成为逆序对(前提是有序的)。

    例如:

    3 2

    这里可以很清楚的看出将会产生一组逆序对。

    我们一起来走一遍:

    1、

    l = 1, r = 2,mid = 1,分成的序列是3和2。

    x = 1,z = 2,a[x]大于了a[z],那么inver将会等于mid - x + 1,即为1。

    然后临时数组将会把a[z]装进去。

    2、

    l = 1, r = 3,不满足循环条件,退出。

    把a[x]放进去。

    3、

    把临时数组赋值回a数组中。

    在这里,归并算法思想的逆序对就做完了,但是,今天我的主题并不是这个,而是——树状数组!

    树状数组

    逆序对同样也可以用树状数组求解。终于扯到正文了,不知道有没有谁是直接跳到这里的呢

    不过如果要用树状数组的话,那么就需要用到离散化了。

    离散化是程序设计中的一个常用的技巧,它能够有效地降低时间复杂度。

    如果有些数据特别大,无法作为数组的下标保存对应的属性,可只需要这些数据的相对属性的话,那么就可以直接进行离散化了。

    例如:

    在这里只需要保存排序后的数组下标(即是第几小的)。

    离散化常见的有两种方式:1、数组离散化    2、STL+二分离散化

    数组离散化

    可以将需要离散化的数组映射成更小的值(支持为下标),以下使用的是对应的顺序(rank)值。

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    struct node{
        int value, id;
        bool operator < (const node &k)const {
            return value < k.value;
        }
    }a[20];
    int b[20], N;
    
    int main (){
        scanf ("%d", &N);
        for (int i = 1; i <= N; i++){
            scanf ("%d", &a[i].value);
            a[i].id = i;
        }
        sort (a + 1, a + 1 + N);
        for (int i = 1; i <= N; i++){
            b[a[i].id] = i;
        }
        for (int i = 1; i <= N; i++){
            printf ("%d\n", b[i]);
        }
    }
    

    输入:

    5
    
    1000 65 32 1200 78
    

    输出:

    4
    2
    1
    5
    3

    STL+二分离散化

    #include <cstdio>
    #include <algorithm>//sort,unique,lower_bound都需要这个函数
    using namespace std;
    
    int N, a[20], b[20], cnt;
    
    int main (){
        scanf ("%d", &N);
        for (int i = 1; i <= N; i++){
            scanf ("%d", &a[i]);
            b[i] = a[i];
        }
        sort (a + 1, a + 1 + N);
        cnt = unique (a + 1, a + 1 + N) - a - 1;//unique的作用就是排序并去重,返回的是无重复数组的最后一个位置的地址加一
        for (int i = 1; i <= N; i++){
            b[i] = lower_bound (a + 1, a + 1 + N, b[i]) - a;//lower_bound是在a数组中找第一个大于等于b[i]的地址
        }
        for (int i = 1; i <= N; i++){
            printf ("%d\n", b[i]);
        }
    }
    

    如果有不了解unique和lower_bound的朋友可以点这里:https://www.cnblogs.com/wangkundentisy/p/9033782.html

    https://blog.csdn.net/qq_41603898/article/details/81603327,这里就不再赘述。

    树状数组求逆序对

    有了离散化,就可以来考虑逆序对了。

    其实逆序对实际上就是统计当前元素前有几个比他大的元素个数,累加就OK了。

    演示:

    注意:这里的sum函数就是计算前缀和,而这个前缀和是把自己也算在里头了的。

    参考代码:

    #include <cstdio>
    #include <algorithm>
    #define MAXN 100000
    #define lowbit(a) a & -a
    using namespace std;
     
    struct node{
        int val, id;
        bool operator < (const node &k)const {
            return val < k.val;
        }
    }s[MAXN + 5];
    int n, b[MAXN + 5], c[MAXN + 5];
    int a[MAXN + 5], num[MAXN + 5];
    long long inver;
     
    template <typename T>
    void read (T &x){
        x = 0;
        char c = getchar ();
        while (c < '0' || c > '9')
            c = getchar ();
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
    }
     
    void upDate (int k){//相当于更改k的值,同时更改k后,他的祖先也会改变,所以一直追溯到祖先都要改变
        for (int i = k; i <= n; i += lowbit(i)){
            c[i] += 1;
        }
    }
     
    long long Sum (int k){//计算前缀和
        long long tot = 0;
        for (int i = k; i >= 1; i -= lowbit (i)){
            tot +=c[i];
        }
        return tot;
    }
     
    int main (){
        read (n);
        //这里有两种去重方法,一种是STL,另一种是数组去重
        /*for (int i = 1; i <= n; ++i){
            read (s[i].val);
            s[i].id = i;
        }
        sort (s + 1, s + 1 + n);
        int cnt = 0;
        for (int i = 1; i <= n; ++i){
            if (s[i].val != s[i - 1].val)
                cnt ++;
            b[s[i].id] = cnt;
        }*/
        for (int i = 1; i <= n; ++i){
            read (a[i]);
            num[i] = a[i];
        }
        sort (num + 1, num + 1 + n);
        int cnt = unique (num + 1, num + 1 + n) - num - 1;
        for (int i = 1; i <= n; ++i){
            a[i] = lower_bound (num + 1, num + 1 + cnt, a[i]) - num;
        }
        for (int i = 1; i <= n; ++i){
            upDate (a[i]);
            inver += i - Sum (a[i]);
        }
        printf ("%lld",inver);
    }
     
    展开全文
  • 我们来简单的分析归并算法的过程,简单的说分为三步,其中包括有序数组的合并,数组的压缩,二维数组与一维数组的转换。 1.有序数组的合并(分别使用了for(参数无关),while) /** * 入参为两个从小到大的有序数组...
  • 大家可能对一维数组的快速排序和归并排序比较熟悉,但是dan
  • 请创建一个一维整型数组用来存储待排序关键码,关键码从数组下标为1的位置开始存储,下标为0的位置不存储关键码。输入关键码的个数,以及各个关键码,采用归并排序的方法关键码数组进行排序,输出每轮的中间过程。...
  • 【问题描述】[中等] 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,...最直接的做法是将二维数组另存为为一维数组,并一维数组进行排序。最
  • 【基于归并排序的分治】统计问题

    千次阅读 2010-10-24 19:27:00
    题目是这样的:给你个N*N的矩阵,可以完成两个操作 1....对于2个偏序集,我们常用的方法是其中某个偏序集进行排序使其成为全序集,再用数据结构统计另个偏序集。3个应该怎么办?(看了题解后)应该
  • 闲话 ...这类分治有个重要的思想——用个子问题来计算个子问题的贡献。 有了这种思想,就可以方便地解决更复杂的问题。 这样句话怎样理解好呢?还是做做题目吧。 例题1 三偏序问题...
  • 题目大意: 题面传送门 三维偏序裸题 ...而$c_{i}$这一维需要用权值树状数组维护 归并排序时,已知左侧右侧两个指针分别是$i,j$ 如果$b_{i} \leq bj$,将左侧已经遍历过的三元组的$c_{i}$推...
  • 三维偏序的模板问题,咕咕咕了有一年的CDQ分治,今天终于补出来了,简单总结一下,一维偏序排个序就出来了,二维偏序是对一维排序,另一维用线段树或树状数组维护,三维的话,第一维排序,第二维用归并排序维护,...
  • 树状数组总结

    千次阅读 2011-10-18 11:04:56
    Poj上的一些题:1)poj1195 Mobile phones 难度:1题意:给定n*n矩阵,和几种在线操作,包括某一点(x,y)值修改,查询个...分析:有两种方法:归并排序;树状数组。这里提一下树状数组的方法。倒着处理,每次统计...
  • 一维 1. 排序及数组规律  递归排序,归并排序,堆排序,时间复杂度及分析。 题目(面试题29):数组中出现次数超过一半的数字。 题目(面试题30):数组中最小的k个数。 题目(面试题36):数组中的逆序。考察...
  • 二路归并

    2021-02-21 10:09:30
    二路归并 题目描述 编写个程序,使用分治策略实现二路归并排序(升序)。...、将数组拆分为两个部分,一般取数组长度一般的位置为界,分为两个子数组,再分别这两个子数组进行递归归并排序。 ​
  • 开始学cdq分治,然后看到了__stdcall的博客,然后发现从前打过的归并排序求逆序就是一个典型的cdq分治。 大致思想就是先按照一维来排序,然后按照第一维的顺序进行分治。然后在分治的过程中保证在第一维下左半...
  • hdu 5126 stars ( CDQ分治 + 树状数组)

    千次阅读 2015-07-24 14:25:01
    个叫做旺仔的坏学长教会的算法---CDQ分治,和归并排序很像,只是在归并排序的过程中每个查询进行统计。 下面这个是他的博客链接: 点击打开链接 我主要结合hdu 5126这个题来讲解CDQ分治的具体做法: ...
  • 偏序问题

    2020-09-15 20:46:54
    我们先一维进行排序来 aaa 降维,再在第二维用归并排序 bbb 实现降维,再在归并排序中套一个树状数组来计算 ccc 的贡献,即可求出答案(cdq分治的思想) 其复杂度为 O(nlog2n)O(nlog^2n)O(nlog2n) 代码...
  • 题意  给出某种排列,按照某种顺序依次删除m个数,在每次删除一个数前统计序列中逆序对对个数。... 这里介绍下三维偏序的求法:一维排序,二维归并,三维树状数组。  排序维护x维之后,递...
  • 偏序(cdq分治)

    2019-03-07 08:30:00
    一维对a排序 第二维归并排序,因为已经按a排过序,在左边和右边b排序时仍保证左边的a小于右边 第三维树状数组,查询满足前两位偏序关系,且c小于当前数的个数 #include<cstdio> #include<cstring...
  • 然后以b为关键字按照从小到大的顺序进行归并排序,在归并排序时,用树状数组来维护c。但是这样只能计算前面的元素后面的元素的贡献,当存在相等的元素时就会漏算,所以在归并前先将相同的合并,对于合并的内部另外...
  • 对一维排序后,使用$cdq$分治,以类似归并排序的方法处理的二维,对于满足$a[i].b \leq a[j].b$的点对,用树状数组维护$a[i].c$的数量。当遇到$a[i].b>a[j].b$时可以更新$j$的答案,因为前半部分中剩余的点的第二...
  • cdq分治的模板题目,用cdq分治处理点的问题,首先按照第一维排序,然后分治,这样就可以每次考虑二三维即可,然后就可以利用树状数组求解了,然后一个核心的代码就是归并排序了,但是不是很难写。 然后需要处理一...
  • 一、排序问题:对一个n维数组排序 输入:一个n维整数数组,A[0..n-1] 输出:递增排序的A 插入排序: 时间复杂度: 归并排序: 时间复杂度: 比较两种方法,插入排序和归并排...
  • poj2299

    2015-05-11 21:41:41
    poj2299题目链接 题意: 一个含有n个数的数组, 每次只能交换相邻的两个数, 求最少操作多少次可以使该数组变成一个有序数组...归并排序核心操作:将一维数组中前后相邻的两个有序序列归并为一个有序序列。那看一下我
  • 若要求尽可能快地序列进行稳定的排序,则应选() 快速排序 归并排序 起泡排序 正确答案:B 排序的稳定性,所谓稳定性即能保证两个相等的数,经过排序之后,其在序列...2.以下正确定义一维数组的选项是( ) int a...
  • poj2299 二分思想

    2015-05-11 21:49:00
    poj2299 http://poj.org/problem?id=2299题意:一个含有n个数的数组, 每次只能交换相邻的两个数, 求最少操作多少次可以使该数组变成一个有序数组(从小到大)。...归并排序核心操作:将一维数组中...
  • CDQ分治

    2019-07-26 21:34:00
    学长课件在文件。...对于二维偏序问题,我们可以一维排序,然后用树状数组维护第二维。 对于三维偏序,我们可以用cdq第一维 归并第二维 树状数组第三维 提醒自己:cmp函数最好拆开写! 第一维...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 143
精华内容 57
关键字:

归并排序对一维数组排序