Memory of Cutey

简介：归并排序(merging sort)的时间复杂度为O(nlogn)，是一种稳定的排序方法。常用的2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，递归算法形式简洁，简单易用。 应用1：求逆序对数 设a[1...n]是一个包含n个不同数的数组，对于i<j如有a[i]>a[j]，则称(i,j)为一个逆序对。出题方式很多，比如直接求一个序列中逆序对的个数；比如交换原序列中相邻两元素位置使之成为单调不下降序列，求交换次数等等。当然，求逆序对数的方法也很多，但时间复杂度不大于O(nlogn)就只有归并排序和平衡二叉树了吧，显然归并排序实现起来更加简单，代码如下所示。 #include <stdio.h> #define MAX 50001 int temp[MAX]; int count, n; void Merge(int *array, int s, int m, int t) { int i=s, j, k; for (j=m+1,k=s; s<=m&&j<=t; ++k) { if (array[s]<=array[j]) temp[k] = array[s++]; else { temp[k] = array[j++]; count += m-s+1; //record the inversion pairs } } while (s<=m) temp[k++] [...]

C语言可以说是我学习的第一门语言，不过似乎也是忘的最多的一门语言，自从因为项目需要重新拾起C语言，我的噩梦就开始了。 依稀记得大二学习数据结构时编程解决“约瑟夫环”、“迷宫”等问题后的骄傲，认为C简直就是天神一般的语言，如此强大，如此让人着迷。后来学了C++，后来开始搞.net，后来自学了CSS和简要的PHP，当C快被我抛弃的时候，由于种种原因，被分到一个新的项目，重新开始做C编程。 继语法树构造完之后自我放假了好久，这两天开工写了一段文件处理的代码，发现以前学习的C语言知识确实完全还给老师了，小崔，我对不起你啊，下面是遭遇问题小结。 1. 字符型转化为整型 如果不是正好用到，我想我永远不会知道居然还有标准库函数可以将字符串转换为任意类型（整型、长整型、浮点型等），我太无知了，我居然只知道强制类型转换，却从来没想过对于字符串要怎样处理，不过还好有人跟我一样不知道，哼哼。 atof()：将字符串转换为双精度浮点型值； atoi()：将字符串转换为整型值； atol()：将字符串转换为长整型值； strtod()：将字符串转换为双精度浮点型值，并报告不能被转换的所有剩余数字； strtol()：将字符串转换为长整值，并报告不能被转换的所有剩余数字； strtoul()：将字符串转换为无符号长整型值，并报告不能被转换的所有剩余数字。 用法非常简单，举例说明如下：