一定不要眼高手低,对基本排序算法的时间复杂度和空间复杂度的良好掌握是后续各种变化题目以及算法改进的基础。而且排序往往是检索的基础,算是各种复杂操作的核心的核心了。
基本的排序算法叙述要准确。要达到流利叙述思路的程度,就想视频中那样,注意快读排序的一个partition过程(小区间的理解),划分过程的时间复杂度为O(N),具体的算法就不再罗列,要能根据书上的内容自己叙述下来。
时间复杂度
O(n2) | O(N*logN) | 趋近于O(N) |
---|---|---|
冒泡 | 快速 | 基数排序(不基于比较) |
选择(每次选择出剩余最小的) | 堆排 | 计数排序(不基于比较) |
插入(不断插入前面的有序序列) | 希尔 (插入排序改良 每次比的时候 与往前n个步长位置上的元素进行比较 相当于是按照步长分组 每一轮之后 步长逐渐缩小 最后类似于一个经典的插入排序) | null |
null | 归并排序(常与两指针方式 小segment合并为大的segment) | null |
补充:
介绍快排的时候分两步,一个是递归过程的介绍,一个是划分过程的介绍。 介绍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。
补充:
虽然很简单,但是自己实现的时候还是没能一次实现对,要是面试的时候让手写,可能就惨了,下面是在牛客网上练习的时候自己有些小地方没注意到的。 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; } };
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的一个面试题目了,对于这种比较经典的算法,最好的办法就是记住,特别是连接部分,怎么定义的,怎么返回的,等等,自己再写的时候,有以下几个启发:
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){ 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; while(low<high){ while(low<high&&A[high]>=pivotal) high--; temp=A[indexp]; A[indexp]=A[high]; A[high]=temp; indexp=high; while(low<high&&A[low]<=pivotal) low++; temp=A[indexp]; A[indexp]=A[low]; A[low]=temp; indexp=low; } return indexp; } };
一直以来最不会写的就是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(1)
把两个有序数组合并为一个数组,第一个数组空间正好可以容纳两个数组的元素。
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)。
思路清楚了之后,代码也还算容易的,主要注意一点,就是何时当前指针会向后移动,一个是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)。
看起来一下不知道怎么做,实际上是很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
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 代码 在实际的题目中,soot可能仅仅作为一种基本的操作而出现,直接通过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; } };