排序算法（一）冒泡&归并_冒泡排序和归并排序

（1）冒泡排序

已知冒泡排序通过检测逆序对来判断一个数组是否有序

每次循环都会把未排序部分中的最大者放大正确的位置（减而治之）

形成（未排好 ， 已排好）的数组，但是未排好的状态是自己定义的

但是它实际可能是排好的

改进方法：

在每一次扫描交换的过程中，记录是否真的存在逆序对，若没有直接返回

template <typename T> //A
bool Vector<T>::bubble(Rank low,Rank high){
     bool sorted = true;
     while(low++ < high){
          if(_elem[low - 1] > _elem[low]){          
              swap(_elem[low],_elem[low + 1]);
              sorted = false;
              }
          }
     return sorted;
   }
     
1
2
3
4
5
6
7
8
9
10
11
12

template <typename T> //B
void Vector<T>::bubblesorted(Rank low,Rank high){
     while(!bubble( low , high--)) //至多（high - low）次全部排序
     }
1
2
3
4

//A部分 ： 针对每次扫描检查是否有逆序对，若没有，返回 true 给 B ，直接结束

//B部分 ： 进行至多 n 次扫描
1
2
3

复杂度分析：

最坏情况和冒泡算法一样，n²

但在某些情况下可以得到极大改善，比如前面部分已经顺序了

不好的地方：

当后半部分已经有序，但前半部分无序时，以上算法对此没有优化

至多执行（r）次，（前面部分个数）

但是因为后面的元素也要 一 一 轮过（虽然有序），要减小到只剩前面的无序部分（因为直接比较总共 n 次，交换至多 r 次）

所以 时间复杂度O（n * r）

改进：

把 high 的位置更新到无序部分的末尾

template <typename T> //A
Rank Vector<T>::bubble(Rank low,Rank high){
     Rank last = low;
     while(low++ < high){
           if(_size(low - 1) > _size(low)){
              last = low;
              swap(_size[low],_size[low + 1]);
              }
         }
     return last;
     }
1
2
3
4
5
6
7
8
9
10
11

template <typename T> //B
void Vector<T>::bubbleSort(Rank low,Rank high){
     while(low < (high = bubble(Rank low,Rank high));
     }
1
2
3
4

//A部分 ： 把无序部分初始设定在 [low - 1 , low]

//随着A部分的迭代，若发现逆序对，则把无序部分更新

//A部分更新到最后 low 也就是无序部分的最大者去了它该去的位置，其他值不一定有序

//B部分中，把更新后[low ， low - 1]的次数定为循环次数

//[low，low - 1]：第一个是真正的起始点/0
                  
                  第二个是在 A 部分中更新后无序部分的次大点，中间可能跨越了几个元素

//A部分在经过 r 次后，全部交换完毕
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析：

首先需要全部扫描一遍确定 low 的位置 O（n）

接下来只在无序部分中扫描，O（根号n的²）

虽然最坏情况没有变化吧，但是还算是愉快

更通用的情况：随时更新

对 bubble 综评：

1.效率：嘛，最好最坏两者莫得差别

2.稳定性：数组元素是否按照原有的相对次序排序

在以上两个算法中，只有严格大于才会发生交换，所以维持了稳定

（2）归并排序

应该是数学推出来的吧…这个我就不清楚了

数组排序至少要 nlogn 的时间复杂度，就是 超厉害的这个啦

归并排序要先分开才能合并，就用递归的思想，分而治之

先排出 mid 前，后的顺序，再把两个子列合并起来

复杂度由递推式可知 T（n）= T（n/2）+ O（n）

要一直递归到只有一个元素，返回到由两个元素的状态

开始合并 merge（）

逐层向上

template <typename T>
void Vector<T>::mergesort(Rank low,Rank high){
     
     Rank mid = low + (high - low)<<2; //不一定要保证相等，什么比例划分都OK
     
     if((high - low) <= 1) //单元素 （0，0，1）high不算，自然有序，我笨了
        return ;
                   
     mergesort(low,mid);
     mergesort(mid,high);
     merge(low,mid,high); //针对每层都要去归并（0，0，2）
   } 
1
2
3
4
5
6
7
8
9
10
11
12

template<typename T>
void Vector<T>::merge(Rank low,Rank mid,Rank high){
     T *A = _elem + low; //针对每层归并需要的位置不同
     int lengthB = (mid - low);
     int lengthC = (high - mid);

     T *B = new T[lengthB]; //分配空间
     T *C = mid + _elem;
     for(Rank i = 0;i < lengthB;)
         B[i] = A[i++];
         
     int j=0;
     int k=0;
     
     for(Rank i = 0;(j < lengthB || k < lengthC);){
         if((j < lengthB) && (B[j] < C[k]) || lengthC < k )
            A[i++] = B[j++];
         if((k < lengthC) && (B[j] >= C[k]) || lengthB < j )
            A[i++] = C[k++];
         }
     delete [] B;
  }
          
                         
     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//Q1:为什么给B子列分配空间，而C不用

//A1:其实给B/C哪个分配都一样，只是后续不能覆盖元素，分配两个又浪费，最后记得删除

//Q2：各变量意义？

//A2：lengthB/lengthC 表示B/C子列的长度
      k —— C子列当前比较位置；j —— B子列当前比较位置  Rank
      i —— A子列需要写的位置   Rank
      
//Q3：循环语句中的判断条件是 || 而不是 &&？

//A3：可能一整个子列B，都比子列C的第一个元素小
      所以除非两个都溢出，会终止循环
      此时另一个一直保持在溢出状态，体现在下面的判断语句
 
 //Q4：为什么for（）判断的，if（）还要判断？
 
 //A4：假如有子列秩溢出，在for（）判断中，无法判断哪个溢出
       又不能用溢出的元素判断，所以if里还要再确定一下
       j 对应后面赋 B 值，k 对应后面赋 C 值
 
 //Q5： if（）选择中，比较 length 与 j/k 的作用？
 
 //A5： 假如有一个子列已经排好了，处于溢出状态，此时只需要排另一个子列
        在溢出的状态下无法比较，所以是 或|| 的关系
        与判断的顺序不可以颠倒！！！！，先判断是否越界
 
 //Q6： 小于，等于，大于改变顺序？
 
 //A6： 也可以是 B[j] <= C[k]，反正也相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

复杂度分析：

merge() :

主要是 for() 语句，由 j，k 两个变量组成

虽然不确定每次分支选择是 j+1还是k+1，但是（j+k）总体至多为n

所以 O（n）

mergeSort（）：

对两个子列的递归排序

排序其实没有结束…随着后面学继续补充