Algorithm(2) sorting(By solution)

主要是记录一些sort相关的题目。

经典排序算法（8个）

一定不要眼高手低，对基本排序算法的时间复杂度和空间复杂度的良好掌握是后续各种变化题目以及算法改进的基础。而且排序往往是检索的基础，算是各种复杂操作的核心的核心了。

时间复杂度

基本的排序算法叙述要准确。要达到流利叙述思路的程度，就想视频中那样，注意快速排序的一个partition过程(小区间的理解)，划分过程的时间复杂度为O(N)，具体的算法就不再罗列，要能根据书上的内容自己叙述下来。

以ascent sorting为例子:
冒泡排序，两个for loop 每次比较相邻的元素，选出最大的放在最右边。

快速排序，选出一个pivotal元素（第一个），所有小于pivotal的值放在左边，大于pivotal元素的值放在右边

选择排序：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

这里列出了一个各种排序算法的比较，reresh的时候注意一下。特别注意一下冒泡与选择的区别，冒泡要交换好多轮。

插入排序与希尔排序，希尔排序是插入排序的一种。
插入排序，假定原始已知的序列是有序的，每次遇到一个新的元素就从已有的array中找对应的位置，然后将新的元素插入到对应的位置中。
希尔排序又称为缩小增量排序，有点strided version的感觉，每次有一个offset 比如i号元素和i+offset,i+offset+offset … 位置上的元素进行比较(这里的比较使用插入排序)，然后不断地缩小offset，直到最小缩小到1。

归并排序，典型的利用divide and conqure 的思路，left child 与 right child 排好序之后merge 到当前的node。

时间复杂度

直接参考一些网上的资源，比如这个.

补充：

• 介绍快排的时候分两步，一个是递归过程的介绍，一个是划分过程的介绍，一般先是介绍一次划分的思路，然后是介绍如何递归进行。

介绍Partition的时候，一种是把枢值元素单独存出来，在排序的过程中把枢轴元素覆盖掉，最后在填到最终的位置，另外一种是每次进行交换，不用额外的空间，显然每次进行交换的这种方式更容易理解。叙述起来也更好点，就是两个指针，左边的大于枢值的话，交换，右边的小于枢值的话，交换。

• 堆排序在后面题型变种中使用的很多，关键就是相比于选择排序，在每次选择的过程中，将后面剩余的那些元素视为一个大根堆或者小根堆，利用堆结构，不断地对剩余的元素进行调整。在笔试中会考察堆结构的调整算法。 以大根堆为例，1 序列构建好大根对堆 2 堆顶元素与序列中的最后一个元素交换 之前的堆顶元素现在为序列中的最后一个 脱离序列 作为序列的有序部分 分离出来 3 重复前面过程 继续调整迭代

• 基数排序平时用的比较少（在那种大数据的题目中 内存有限 给定很大数据量的题目中 常常会使用到桶排），即按照 bin sort 桶排的思路，以那个三位数的排序为例，首先是按照个位数入桶，出桶，之后是按照十位，入桶，出桶，之后是按照百位。（多次进桶多次出桶）

• 计数排序 也是基于bin sort 的思路 比如员工的身高排序 一般是100cm到300cm之间，之后从100cm 101 cm … 300cm建立桶，之后把员工放入对应的桶中，放好之后再按照桶的顺序将员工倒出，就是排好序的序列。

空间复杂度与稳定性

关于空间复杂度

类别	复杂度
冒泡	O(1)
选择（每次选择出剩余最小的）	O(1)
插入（不断插入前面的有序序列）	O(1)
堆排	O(1)
希尔排	O(1)
快排 （会入栈 出栈）	O(logN)~O(N) O(logN)表示的是栈的深度 递归时候要使用栈空间
归并	O(N)
基数排序 计数排序	O(M) 其中M表示选择桶的数量

关于稳定性

相同值的元素在排序前后，相对次序保持不变。

不稳定算法的的口诀：
希望选择用快速的方法构造一个堆是不稳定的

希尔排序 选择排序 快速排序 堆排序 这几种是不稳定的

但实际上最好给别人讲的时候，能通过一个例子来模拟说明，看对算法的理解是否透彻，其实都是很easy的case。

• 选择排序 比如 2 2 2 1 第一步 元素1被选中，与第一个位置上的2进行交换，这样就导致了不稳定的情况出现。

• 快速排序 比如 4 3 3 3 2 如果在以中间的3做为梳轴，剩下的两个要不全在它左边，要不全在它右边，总之位置肯定发生了改变。

• 堆排序 比如原始的序列中有三个5 5 5 建立了大根堆之后，有可能第一个5在堆顶的位置，这个时候，它会被移动到整个序列最后的位置，于是第一个5在排好序的序列中会位于原来第二个以及第三个5的后面的位置，这样就出现了不稳定的情况。

• 希尔排序 5 1 1 5 步长为2的时候，第二个1会与第一个5进行交换，这样会使得前两个1的位置发生了改变。
  补充：

• bin sort 类的局限 ， 适用于有限的case，可能会导致bin太多，造成空间的浪费

• 工程上的排序是多种排序类算法的综合。

• 选择排序 堆排序 冒泡排序 快速排序 每次都可以使得一个元素到达它的最终位置

基本实现

虽然很简单，但是自己实现的时候还是没能一次实现对，要是面试的时候让手写，可能就惨了，下面是在牛客网上练习的时候自己有些小地方没注意到的。

Bubble sort

class BubbleSort {
public:
    int* bubbleSort(int* A, int n) {
        // write code here
        int i,j,temp;
        //第一层循环表示的是要有 n 次的移动
        for(i=0;i<n;i++){ 
            //第二次表示的是 每次相邻的两个元素比较 
            //注意这里是 j 号元素与j+1号的比较 最后j<n-1-i
            for(j=0;j<n-1-i;j++){
                if(A[j]>A[j+1]){
                    temp=A[j];
                    A[j]=A[j+1];
                    A[j+1]=temp;
                }
            }
        }
        
        return A;
    }
};

Select sort

class SelectionSort {
public:
    int* selectionSort(int* A, int n) {
        // write code here
        int i,j,min,l,temp;
        for(i=0;i<n;i++){
            min=A[i];
            for(j=i;j<n;j++){
                //注意这里要是<= 因为要保证 每次都更新l 即使是相等的时候
                if (A[j]<=min){
                    min=A[j];
                    l=j;
                }
            }
            //注意这里最后找到min元素之后 要与前面的做交换
            if (l<n){
            temp=A[i];
            A[i]=A[l];
            A[l]=temp; 
            }
        }
        return A;
    }
};

QuickSort

手写快排应该是很common的一个面试题目了，对于这种比较经典的算法，最好的办法就是记住，特别是连接部分，怎么定义的，怎么返回的，等等，自己再写的时候，有以下几个启发：

• 题目中给的函数声明是 int A, int n 这种显然不适合进行递归的调用，这个时候要灵活变通，额外声明函数quick(intA,int low,int high)，转化为熟悉的形式，递归存在的时候要注意好函数的声明。

• 在partition的时候，为了思路上的简易，直接写成交换元素的方式，这个时候要用一个额外的元素记录location of pivotal，因为每次都会改变，最后返回。

  class QuickSort {    
  public:
      int* quickSort(int* A, int n) {
          // write code here
          this->quick(A,0,n-1);
          return A;
          
      }
      
      void quick(int*A,int low,int high){
          if(low<high){
              //Typical binary search style
              //选择枢轴元素
              int pivotal=this->Patrition(A,low,high);
              //枢轴左边部分排好
              quick(A,low,pivotal-1);
              //枢轴右边部分排好
              quick(A,pivotal+1,high);
          }
      }
      
      //return the location of the pivotal element
      int Patrition(int*A ,int low,int high){
          int pivotal=A[low];
          //让序列开始位置的元素作为枢值元素
          int indexp=low;
          int temp;
          //围绕pivoal元素进行交换
          while(low<high){
          		  //右边大于pivotal就直接跳过
              //右指针从右边移动到第一个小于pivotal的位置
                 		  // 然后和pivoal的element进行交换
              while(low<high&&A[high]>=pivotal) high--;
              temp=A[indexp];
              A[indexp]=A[high];
              A[high]=temp;
              indexp=high;
              
              //左边也类似，移动到第一个大于pivotal的位置
                       //之后和pivotal的位置进行交换
              while(low<high&&A[low]<=pivotal) low++;
              temp=A[indexp];
              A[indexp]=A[low];
              A[low]=temp;
              indexp=low;   
          }
          return indexp;
      }
  };

Heapsort

一直以来最不会写的就是heapsort，因此要多熟悉熟悉。
实际编写的时候，为了方便，位置为0的第一个元素没有存值，前面搞得有点乱。。。
AdjustDown的思路还是有点绕的

class HeapSort {
public:
    int* heapSort(int* A, int n) {
        // write code here
        int i;
        int*a=(int*)malloc((n+2)*sizeof(int));
        for(i=0;i<n;i++){
            a[i+1]=A[i];
        }
        int *b=heap(a,n);
        for(i=0;i<n;i++){
            A[i]=b[i+1];
        }
        a=NULL;
        b=NULL;
        return A;
    }
    
    int* heap(int *A,int n){
        int i,j,temp;
        this->BuildMaxHeap(A,n);
        for(i=n;i>1;i--){
            temp=A[i];
            A[i]=A[1];
            A[1]=temp;
            this->AdjustDown(A,1,i-1);
        }
        return A;
    }
    void BuildMaxHeap(int *A,int n){
        // 从len/2到1 反复调整根堆 默认的是从1号位置开始调整
        // 每次传入的i应该都是根元素
        int i;
        for(i=n/2;i>0;i--){
            this->AdjustDown(A,i,n);
        }
    }
    //将元素向下进行调整 k为堆顶元素的编号 len为数组的长度
    //A[0]中不存放元素
    void AdjustDown(int*A,int k,int len){
        int i;
        //A[0]的位置不存放元素
        A[0]=A[k];
        for(i=2*k;i<=len;i*=2){
            //先从左右孩子中选出较大的一个 然后与根元素交换
            //左孩子 < 右孩子 则i变为右孩子的位置
            if(i<len&&A[i]<A[i+1])
                i++;
            //如果根元素大于孩子里面较大的那个 则这次调整跳过
            if(A[0]>=A[i])break;
            //根元素 换成孩子
            else{
                A[k]=A[i];
                k=i;
            }
        }
        //k号元素被调整过 还要调整回来
        A[k]=A[0];
    }
    
};

插入排序由于在数组的时候，还要大量移动元素，了解思路即可，这里先不再写了

经典排序算法的变形

题目一

已知一个几乎有序的数组，所谓几乎有序，是指如果把这个数组排好顺序的话，每个元素移动的距离不超过k，（换句话说，元素当前所在的位置距离元素排好序之后的最终位置的距离是k），并且相对于整个数组长度来说，k很小，选择哪种排序算法比较好。注意思考的思路:

• 思考 O(N2) 基数以及计数 由于并不知道数组中数字的范围 它们不一定适用所有的情况
• O(N2) 插入排序较好 由于每个元素移动不超过k，可以做到O(N*K)
• O(NlogN) 快排 以及 归并 仍然为 O(N logN)
  改进之后的堆排序，整个数组的最小值，因为移动的距离不会超过k，（提取这句话的信息量）排序之后，最小的元素会被放在a[0]的位置上，所以最小的元素存在于a[0]到a[k-1]的范围中。a[0]…a[k-1]这么些元素，组成小根堆，弹出最小值，放在数组的位置0上，之后，每次窗口后移一个位置，并且把窗口中的这些元素构造成堆的结构，弹出最小值，按序排列，弹出的顺序是每次数组从小到大的顺序。调整的时间复杂度O(logk)一共N个数，总共时间复杂度，O(N*logK)

题目二

给定一个数组，判断数组中是否有重复的值，必须保证额外的空间复杂度为O(1)

• 没有空间复杂度的限制，显然用Hashmap，在遍历数组的过程中，统计每个数出现的次数，时间复杂度与空间复杂度全为O(N)
• 空间复杂度为O(1)的时候，显然堆排序有较好的速度，传统的堆排序是基于递归实现的，函数栈的大小是堆的层数，最好是能使用非递归的堆排序。

题目三

把两个有序数组合并为一个数组，第一个数组空间正好可以容纳两个数组的元素。

• 两个指针，每次比较，大的元素拷贝到最后的位置，拷贝之后指针前移。
• 关键是从后往前覆盖数组A，保证数组A的有用的部分不会因为合并操作而被覆盖掉。
  这个是参考了比人之后的代码，真的是很简单，这样写，以indexn为游标从后往前，这样思路会比较清晰，之前是使用了indexA以及indexB为游标，有一个case总是过不去。

class Merge {
public:
    int* mergeAB(int* A, int* B, int n, int m) {
        // write code here
        int indexA=n-1;
        int indexB=m-1;
        int indexn=m+n-1;
        int i;
        for(i=indexn;i>=0;i--){
            A[i]=A[indexA]>B[indexB]?A[indexA--]:B[indexB--];
        }
        
        return A;
    }
};

题目四

荷兰国旗问题，整个数组中仅仅包含0,1,2三个元素，排序之后，所有的0在最左边，所有的1在中间，所有的2在最右边，只能使用交换，原地排序，不能使用计数进行排序，即是说空间复杂度只能是O(1)，之后时间复杂度可以变成O(N)。

• 这个实际上是对快排的加深理解，应用了partition的思路进行划分，在最左边设想有一个0区，在最右边设想有一个2区，之后中间是1区。
• 需要三个指针记录位置，left current right ，如过当前元素是0，就和0区间右边的一个元素交换，如果是2就和2区左边一个元素交换，直到current指针和right指针重合。
  思路清楚了之后，代码也还算容易的，主要注意一点，就是何时当前指针会向后移动，一个是0元素发生交换之后，一个是当前元素为1的时候。因为只有三个种类的数字，值为0的元素发生交换的时候，肯定是和当前元素紧挨着的，所以也要向后发生移动，这里容器忽略。

class ThreeColor {
static void swap(vector<int> &A,int indexa,int indexb){
    int temp;
    temp=A[indexa];
    A[indexa]=A[indexb];
    A[indexb]=temp;
}
    
static void partition(vector<int> &A , int left, int right){
    int index_l=left,index_r=right;
    int i;
    for(i=left;i<=index_r;){
        if(A[i]==0){
            swap(A,index_l,i);
            index_l++;
            //注意这里要同步地加上
            i++;
        }else if(A[i]==2){
            swap(A,index_r,i);
            index_r--;
        }else{
            i++;
        }
    }   
}
public:
    vector<int> sortThreeColor(vector<int> A, int n) {
        // write code here
        partition(A,0,n-1);
        return A;
    }
};

题目五

给定一个二维数组，二维数组的每行和每列都是排好序的，再给定一个数，判断二维数组中是否包含这个数。时间复杂度可以做到O(m+n)，空间复杂度可以做到O(1)。

• 这个题目其实还有点trick，开始遍历的时候，从右上角的元素开始，比如待查元素为n，若n<右上角元素，最后一列都比n大，左移。如果n比左移之后的元素大，那么只需要在当前的这一列比较即可。
• 总之是要很好的利用排好序的矩阵的这种特性。
  看起来一下不知道怎么做，实际上是很cute的一段代码，就是根据不同的情况不断调整row以及column的值即可，注意边界条件的判断while (row<n && column>-1) 。

class Finder {
public:
    bool findX(vector<vector<int> > mat, int n, int m, int x) {
        // write code here
        int row=0;
        int column=m-1;
        int element;
        while(row<n && column>-1){
             element=mat[row][column];
          if(element>x){
             column--; 
           }else if(element<x){ 
             row++;
           }else if(element==x){
             return true;
           }
        }
        return false;
    }
};

题目六

给定一个数组，返回这个数组中需要排序的最短子数组的长度。比如[1,5,4,3,2,6,7]，返回4，只有[5,4,3,2]需要排序。

• 解法1 先使用快排排好序，再用两指针的思路与原序列比较，找到位置不同的序列的最大长度，注意这里的最短子序列应该是连起来的一段，比如排好序 1 2 3 4 5 6 7 原序列 1 2 7 3 5 4 6 这样最短序列是5，虽然元素5在排好序的序列中的位置和排序前的位置是一样的，但是它仍然要被算在最短子序列中。
• 解法2 实际可以用O(N)的解法计算。首先从左向右遍历，记录遍历过的部分的最大值，如果遍历过的部分的最大值大于当前的数，在最终排序之后，最大值起码在当前数的位置，或者当前数往右的位置。同样的道理，从右往左遍历，记录遍历过的数字的最小的值，之后考察当前元素大于这个元素的情况，这样在最终排序之后，最小值起码在当前数字所在的位置或者其左边，这样就找到了序列的两个端点，于是中间的部分就是最短的需要调整的子序列。
  解法1

class Subsequence {
static int cmp(int a,int b){
    if (a<b){
        return 1;
    }else{
        return 0;
    }
}
public:
    int shortestSubsequence(vector<int> A, int n) {
        // write code here
        vector<int>B(A);
        sort(B.begin(),B.end(),cmp);
        int i,j,count=0,left=0,right=n-1;
        for(i=0;i<n;i++){
            if(A[i]==B[i]){
                left++;
            }else{
                break;
            }
        }
        for(j=n-1;j>0;j--){
            if(A[j]==B[j]){
                right--;
            }else{
                break;
            }
        }
        if (left<=right){
            count=right-left+1;
        }
        return count;
    }
};

题目七

给定一个整形数组，返回如果排序之后，相邻两数的最大差值。例如某数组排序之后为 1，2，3，4，7，8，9 最大差值来自于4和7，所以返回3。最优时间复杂度O(N)，额外空间复杂度O(N)。

• 解法1 先使用sort排好序列 之后遍历 记录最大的差值
• 解法2 借用bin sort的思路
  解法1 代码
  在实际的题目中，sort可能仅仅作为一种基本的操作而出现，直接通过sort函数来完成，但是在面试的时候，可能要手写相关的代码。

class Gap {
        
static int cmp(int a ,int b){
        if (a<b){
            return 1;
        }else{
            return 0;
        }
    }
static int abs(int a,int b){
    return a<b?(b-a):(a-b);
}
public:
    int maxGap(vector<int> A, int n) {
        // write code here
        sort(A.begin(), A.end(), cmp);
        int i,max=0;
        for(i=0;i<n-1;i++){
            if(max<abs(A[i],A[i+1])){
                max=abs(A[i],A[i+1]);
            }
        }
        return max;
    }
    
};

题目八（动态求中位数）

输入若干个数，对第k个输入，如果k为奇数，则输出前k个数的中位数。

堆结构的升级，利用夹逼的思路:其实就是三种类型，小于这个数的，大于这个数的，等于这个数的，小于这个数字的所有数字，可以使用一个大根堆保存，大于这个数字的所有数字，可以用一个小根堆保存，这样每次只要保存住小根堆的堆顶元素，还有大根堆的对顶元素，就可以找到中间的一个元素了。大体思路是这样，具体还要涉及元素为基数个的时候，还有元素为偶数个的时候。

快排思路:通过一次partition的过程，将中位数挑选出来，多少有点类似于荷兰国旗的问题。

利用快排的思路，每次进行partition

利用其他结构进行排序

利用一个额外的help栈对原栈中的元素进行排序，具体的题目和答案参考”栈和队列”相关主题整理中的题目。