|
#??引论??#
-?数学储备：指数对数级数运算、模运算
-?递归：基准+不断往基准推进、递归与循环区别在于是否用函数定义该函数的特定实例；递归四法则——基准、推进、设计法则、合成效益
#??算法分析??#
-?定义：比较函数级别——比较相对增长率（即当程序不断运行、数据量递增时能凸显的比较）
????- 
????
-?解决问题可能有相对低效和高效的算法，对于数据量大小也是有影响的。小数据量一般不用区分算法的高效性。但大数据量上，算法的高效性就很明显了。而高效算法一般又存在一个瓶颈：就是算法运行时间中，数据从磁盘读入的时间较长，一旦数据读入，问题就会迅速解决；相对的低效算法则会更多消耗计算机资源。这二者的平衡是一个需取舍的问题。针对求解最大子序列和问题，即使数据量适当，低效算法依旧无用。
-?运行时间：
> 计算任何事情不要超过一次。
-?求解最大子序列和的算法：
????- 1、两层循环，记录最大和值。
????????- 时间复杂度O(N^2);
????- 2、递归，先递归求出左右两边的最大和值（基准值是当第一个值为负数则标记为0，否则直接加），然后分别以中间向左和向右为起点递加求最大和，最后相加起来。比较者三个的最和值。（这个递归就没有重复运算浪费时间的地方，效率高，同时计算）;
????????- 时间复杂度O(N*logN);
????????- 递归的算法时间复杂度也可以用递归方程表示——然后就是解方程的问题了，从N==1开始，用归纳法找规律解出T(N);也可以使用递归树思想
????????- 注：在含递归的函数中，在基准条件处和函数末都可以出现递归（基准条件处使用if语句）
????- 3、如果前面某段加起来不是负数，那么后面的加上前面的总是更大一些的，所以只需要当前面thisSum<=0时重新开始就行了。
????????- 时间复杂度O(N);??
????????
>??这是联机算法：仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。
# 排序算法 #
## 选择排序 ##
-?算法思想：将数组分为已排序和未排序部分（无须创建新的数组），在未排序数组中找出最大（小）值，放到已排序部分（最前（后）头）。
????????void Choice(int A[],int n){
?????????????int i,j,max=A[0],k;
?????????????for(i=0;i<n;i++){
?????????????????for(j=0;j<n-i;j++){
????????????????????if(max<A[j]){
???????????????????????max=A[j];
???????????????????????k=j;
????????????????????}
?????????????????}
?????????????????swap(A[k],A[n-i-1]);
?????????????}
????????}
> 选择排序的核心就是依次选出最值，关键就是利用数组连续位置下标来区分开未排序和已排序。
-?选择排序的优化：在一趟查找中同时找到最大最小值，分头放置。
????????????void Choice2(int A[],int n){
????????????????int i,j,max=A[0],min=A[0],k,h;
????????????????for(i=0;i<n;i++){
?????????????????????for(j=i;j<n-i;j++){
???????????????????????????if(max<A[j]){
?????????????????????????????????max=A[j];
?????????????????????????????????k=j;
????????????????????????????}
????????????????????????????if(min>A[j]){
?????????????????????????????????min=A[j];
?????????????????????????????????h=j;
????????????????????????????}
?????????????????????}
????????????????????swap(A[k],A[n-i-1]);
????????????????????swap(A[h],A[i]);
????????????????}
????????????}
-?选择排序是不稳定的，时间复杂度为O（n^2）,适用于元素个数较少时。
## 冒泡排序 ##
-?算法思想：就是从左到右两两比较，符合大小关系则交换，令最值在一轮查找中调换到最右边，经过n轮实现排序。
????????void Bubble(int A[],int n){
????????????int i,j;
????????????for(i=0;i<n;i++){
????????????????for(j=0;j<n-i-1;j++){
????????????????????if(a[j]>a[j+1]){
????????????????????????swap(a[j],a[j+1]);
????????????????????}
????????????????}
????????????}
????????}
> 相比于选择算法，冒泡算法倒是少开辟了一个变量，但是由于交换频繁，时间开销也更大。
-?冒泡算法的优化：
????- 冒泡排序就是在未排序的元素当中进行频繁地交换嘛，所以我们总是冒泡到已排序处才停下，但也存在未排序序列在某一趟冒泡的时候，后部分甚至整个序列已经自然形成有序序列，而此时有序序列是无需交换的，所以可以引入变量记录交换状态，如果没有交换，循环就不用再继续了，也可以mark下最后的交换地址，以此代替冒泡的终止位置。
????- 另一个思路就是两头同时工作啊，跟前边的选择排序一样。
????????????void Bubble_position(int a[],int n){
????????????????int i,j,position=n-1,isSwap;
????????????????for(i=0;i<n;i++){
????????????
????????????????????isSwap=0;
????????????????????for(j=0;j<position;j++){
????????????
????????????????????????if(a[j]>a[j+1]){
????????????????????????????swap(a[j],a[j+1]);
????????????????????????????isSwap=1;
????????????????????????????position=j;
????????????????????????}
????????????
????????????????????}
????????????????????if(isSwap==0){
????????????????????????break;
????????????????????}
????????????????}
????????????}
??????????????
????????????
????????????void Bubble_coming(int a[],int n){
????????????????int high=n,low=0,i,j;
????????????????while(low<high){
????????????????????for(i=low;i<high-1;i++){
????????????????????????if(a[i]>a[i+1]){
????????????????????????????swap(a[i],a[i+1]);
????????????????????????}
????????????????????}
????????????????????high--;
????????????????????for(j=high;j>low;j--){
????????????????????????if(a[j]<a[j-1]){
????????????????????????????swap(a[j],a[j+1]);
????????????????????????}
????????????????????}
????????????????????low++;
????????????????}
????????????}
-?由于遇到相等值时不交换，所以是稳定的排序方式；时间复杂度是O（n^2），适用于数据量较小的情况。
## 插入排序 ##
-?算法思想：关键就是区分出一个未排序的集合和一个有序集合，慢慢将未排序集合元素按大小要求挪到有序集合中。这个集合可以以数组下标为分界线。
????????void Insert(int out,int a[]){??????????????//out标记有序集合之外的第一个元素
????????????int in=out,temp=a[out];
????????????for(;in>0&&a[in-1]>a[out];in--){
????????????????a[in]=a[in-1];????????//逐步后退
????????????}
????????????a[in]=temp;
????????}
????????void InsertSort(int a[]){
????????????int i;
????????????for(i=0,i<n;i++){
????????????????Insert(i,a);
????????????}
????????}
-?算法优化：在未排序数与有序序列比较时，不再逐个比较，而是采用二分比较找到那个位置。
-?直接插入排序是稳定的。
-?在插入排序中，当待排序序列是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n- 1次，时间复杂度为O(n)。
??最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n2)。
-?适用：待排序序列的元素个数不多(<=50)，且元素基本有序
## 希尔排序 ##
-?算法思想：希尔排序的由来——插入排序。插入排序的复杂部分在于数组的无序性导致频繁地插入，而很多插入对于最终结果来说都是无效的。所以可以想办法令每一个插入对数组的有序性做出贡献——（插入之后要实现有序效果，那必定每次插入之前都做比较，那必定是两两比较，那怎么实现两两比较呢？分组思想）——固定跨度分组，组内两两排序，再调整逐渐减小跨度至1，数组就变成有序的了。
????????void Shell(int A[],int n){
????????????int add=n/2,i;
????????????while(add>1){
????????????????for(i=0;(i+add)<n;i++){
????????????????????if(A[i]>A[i+add]){
????????????????????????swap(A[i],A[i+add]);
????????????????????}
????????????????add=add/2;
????????????}
????????????}
????????}
-?希尔排序的增量问题：时间复杂度是一个跟增量选取有关的问题，至今增量问题还没研究清楚，有几个主流的理论计算公式。
-?希尔排序是个不稳定的排序。
-?时间复杂度冲破O(N^2)的算法
????- 希尔算法（缩小增量算法）
????????- 原理：利用间隔一开始快速消除了多对逆序，后来增量减小时交换就少了
????????- 特点：hk排序将保持每次排序的成果（不像冒泡排序交换的成果很多时候会被破坏，对最后结果没有直接用处）
????????- 增量算法的关键在于增量的选择可以不同程度地减少逆序数
????????????- Hibbard增量未经证明可以达到N的5/4次方，最坏结果也是N的3/2次方；
????????????- 还有时间复杂度可以达到最坏N的4/3，平均达到N的7/6的增量选择
????????????- 一种极端糟糕的增量状态就是奇偶位分别是有序序列，增量为2的N次方时，前边的排序几乎没有进行过交换，所有的交换集中在最后一轮——时间复杂度达到上界为O(N^2)
## 快速排序 ##
-?算法思想：选择一个参照元素key（一般是第一个元素），然后从右往左找到数组的第一个小于key的数a[high]，将这个数的值赋予给key所在位置。然后从左边key之外的元素从左至右数到第一个大于key的元素a[low]，将这个元素的值赋予a[high]，循环至low和high相遇，至此完成第一轮分割。再递归即可
????????void QuickSort(int a[],int left,int high){//传入数组的左右下标
????????????int low=left+1,key=a[0];
????????????if(low>=high){
????????????????return;
????????????}
????????????while(low<high){
????????????????while(a[high]>key){????
????????????????????high--;
????????????????}
????????????????a[low-1]=a[high];
????????????????while(a[low]<key){
????????????????????low++;
????????????????}
????????????????a[high]=a[low++];
????????????????high--;
????????????}
????????????a[low]=key;
????????????QuickSort(a,left,low);
????????????QuickSort(a,low+1,high);
????????}
> 1.这是常规的做法，但是无法保证固定的参照元素的大小一定在数组的中间范畴，如若数组一开始是有序的，固定首位或尾位效率都会非常低。所以要优化快排，那么最好想办法解决掉这个问题，即尽量确保参照元素值大小位于中间水平。
> 2.遇到与参照元素相等的元素要不要交换呢？用一个所有元素相等的数列显然可以推出答案。答案是进行不必要的交换建立两个均衡的子数组比曼干毛线得到两个不均衡数组要好的多（如果遇到相同元素就交换，那么左右两边就发生了一次交错，枢纽元素最后会几近到中间；但是遇到相同元素不交换，那么就需要设置一个界限，最后枢纽元素就会到达边界）
> 3.快排的最坏排序就是枢纽始终取在边界的时候——O(N^2);最好的时候就是枢纽始终在中间的时候——O(NlogN);还有平均情况
-?优化法1（随机法）：三数取中，提高数值大小靠近中间的概率。即在数组中随机找出三个数，取中位数作为参照。
????- 也可以用随机数生成器生成，随机数生成器不罕见但是时间代价昂贵
-?优化法2：每次分割将等于key的值聚到一起，
-?优化法3：数据量在减少到一定程度可以用其他排序办法如插入法。
-?实际上一直采用快排算法不一定快，小数组可以采取插入算法，整体的算法运行时间会有所提升
-?快排是不稳定的；时间复杂度是O(nlogn)【优化法1的时间复杂度】
-?适用场景：待排序序列元素较多，并且元素较无序。
-?拓展应用：快速选择——可以用快排的思路锁定查找元素的区间
## 归并排序 ##
-?算法思想：就是合并两个已排序的表，初始的时候，两个已排序的表就是两个元素。
????????
????????void Merge(int A[],int i,int j){??//将两个有序序列合并
????????????int k=0,m=0,n=i;
????????????int *p=(int *)malloc(N*sizeof(int));//秒就秒在仅在最后一步归并的时????????????????????????????????????候申请内存，避免了多次少量长时????????????????????????????????????间地占用内存
????????????while(k<i&&k<j){
????????????????if(A[m]>B[n]){
????????????????????p[k++]=A[n++];
????????????????}
????????????????if(A[m]<B[n]){
????????????????????p[k++]=A[m++];
????????????????}
????????????}
????????????while(m<i){
????????????????p[k++]=A[m++];
????????????}
????????????while(n<j){
????????????????p[k++]=B[n++];
????????????}
????????}
????????
????????void Msort(int C[],int left,int right){
????????????mid=(left+right)/2;
????????????Msort(C,left,mid);
????????????Msort(C,mid+1,right);
????????????Merge(C,mid,right);
????????}
-?时间复杂度O(NlogN)，空间复杂度O(N)，是个稳定的算法。
????- 归并排序时间复杂度的计算可以列出递归式子
????????- 用数学归纳法解出
????????- 用相消法（同时除以N，迭代写出所有式子，发现相加能相消）
????????- 用右边连续递归代入法
-?归并排序是一个典型的利用分治策略的递归算法，最坏的情况也是O(logn)，比较次数显然是最优的。但其算法时间大部分在拷贝数组当中消耗，同时又额外占用临时数组空间，虽然这个问题可以在审慎转换中间数组与原数组的办法下解决，但终究主存归并排序是不占优势的。但对于外部排序，归并的思想就尤为重要了。
## 堆排序 ##
-?堆：就是每个父结点都>或<子结点的值的树状结构。他的父结点跟子结点之间的编号是2倍加1或2的关系。
-?算法思想：将待排序数组构造成二叉树结构。构造最大堆或最小堆，然后将最大或最小值跟最后一个元素交换位置，排除最后位置缩小树的范围。重复循环至已排序完成。最后可以通过层序遍历获得有序序列。
????????void sort(int A[],int length){
????????????//1.构建最大堆：从右往左，从下至上构建；
????????????int i;
????????????for(i=length/2-1;i>=0;i--){ //自右而左，自下向上，下边的都是排好顺序????????????????????????????的，所以处理上边的时候只需要从上往下调整????????????????????????????一侧就可以了,另一侧是有序的
????????????????adjust(A,i,length);
????????????}
????????????for(j=length-1;j>=0;j--){??//在改变了首尾的位置之后，就等同于重新调????????????????????????????整一下头元素所在的位置就行了
????????????????swap(A[0],A[j]);
????????????????adjust(A,0,j);
????????????}
????????}
????????
????????void adjust(int A[],int head,int end){
????????????int left,right,max,temp=head;
????????????while(temp<end){
????????????????left=temp*2+1,right=temp*2+2;
????????????????max=A[left]>A[right]?left:right;
????????????????if(A[max]>A[temp]){
????????????????????swap(A[max],A[temp]);
????????????????????temp=max;
????????????????}
????????????}
????????}
> 其实在构建最大堆的时候，可以用填坑法（在插入排序算法的时候就有用到，最后将最初的元素填充到最后一个坑就行）
> 堆排序时间复杂度虽然表示为O(NlogN)，但实际的运行速度是慢于Sedgeniczk增量算法的
> 大黑书里的堆排序的时间复杂度问题还没搞懂
> 堆排序有一个很好的地方在于找最值时可以把找到的元素放在树的末尾，节约空间且速度快。
## 桶式排序 ##
若数据的大小有明确的界限M，那么这些数据可以用M大的数组来装载，数据与下标一一对应即可。
## 外部排序 ##
-?内部排序大多用内存直接寻址，数据量很小很小；而磁盘仅能顺序存储，数据量极大。总体而言，虽然内存排序时间复杂度是O（NlogN），磁盘排序时间为O（N），但是后者时间远大于前者，不可同日而语。
-?内存存不了，数据就只能存在外存了。外存与内存交互的逻辑是，外存存储的部分先进内存排序再将有序序列归并
????- ——优化：多路归并+置换选择（堆排序采取边排序边删除边添加——添加数据若是最小或最大，则加入有序子串，否则留在内存中，当内存已满或串已读完，则剩下在内存中的可以形成另一串有序序列。最后产生两串长度远大于内存的有序子串，可以减少磁盘读写时间。但是字串的长度并不能保证平衡，但若是数据为随机分配那么可以算出平均串长为2M）
> k路归并需要趟数：logk(N/M),因为每次归并完顺串都变为原来的k倍
????- I/O次数计算：看每个数据读写了多少次——不同的归并策略构造不同的I/O次数
????????- 最佳归并树：哈夫曼树（k路就用k叉树）
## 排序分析 ##
-?排序分内存排序和外存排序。
-?简单排序算法时间复杂度下界的问题——简单的排序算法的时间其实大部分消耗在元素交换上——元素交换的本质是消除逆序数（笛卡尔积中的大于或小于关系）——O(T)=逆序数——平均时间求解其实就是在求解平均逆序数（在随机序列当中，一半的序偶是逆序的——即1/2Cn2）————相邻元素交换的算法时间均以n^2为下界（因为相邻变换一次仅消除一对逆序）
????- 优化1：令交换发生在相邻较远的元素之间
????- 优化2：交换一次消除不止一对逆序
????????- 像希尔、快排、归并都利用了这种思路
-?实际应用中的对象常常是结构体，而直接交换对于结构体而言代价极为昂贵。但是指针交换就不同了，间接交换代价更小。
-?决策树：决策树可以用来辅助判断只用比较的排序算法的下界
????- 树的深度为d=[log2L]，树叶最多有2^d个；
????- 若N个元素比较，则有N！种结果，也就是有N！个树叶——进而可以推出有logN!次比较——时间复杂度logN!=Ω（NlogN）;
????- 由此推出一般比较排序算法的下界
|