Cpp LeetCode
模拟 排列的特性 - 下一个排列 排序 bubble sort //逐个冒出当前最大值 template <class T> void bubble_sort(T arr[],int len){ for(int i=0;i<len-1;i++){ for(int j=0;j<len-i-1;j++) if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]); } } //设置flag，如果存在一轮冒泡没有进行交换，则排序完成 selection sort //从序列中选出该位置上应该出现的元素 template <class T> void selection_sort(T arr[],int len){ for(int i=0;i<len-1;i++){ int index=i; for(int j=i+1;j<len;j++){ if(arr[j]<arr[index]){ index=j; } } swap(arr[i],arr[index]); } direct_insert_sort //向前遍历有序序列，寻找当前元素的合适位置插入 template <class T> void direct_insertion_sort(T arr[],int len){ for(int i=1;i<len;i++){ T key=arr[i]; int j=i; while(j-1>=0&&arr[j-1]>key){ arr[j]=arr[j-1]; j--; } arr[j]=key; }//位置j的元素要么是j-1(挪),要么是key(插) } //二分法加快插入位置的搜索 shell _sort //宏观性优先调控，减少插排比较和交换次数 template <class T> void shell_sort(T arr[],int len){ int h=1; while(h<len/3) h=3*h+1; while(h>=1){ for(int i=h;i<len;i++){ T key=arr[i]; int j=i; while(j-h>=0&&key<arr[j-h]){ arr[j]=arr[j-h]; j-=h; } arr[j]=key; } h/=3; } } //对于增量以除以2递减的排序，时间代价：$\theta$(n^2^);选取的增量之间并不互质，上一轮排序中某些子序列已经排过了导致处理效率不高 //对于增量不以除以2递减的排序，时间代价：$\theta$(n^3/2^) qsort /*1.选择轴值 2.划分两个子序列L和R - 使得L中所有记录都小于或者等于轴值 - R中记录大于轴值 */ //采用双指针排列小序列，也可以使用夹逼的方式 int partitioner(int arr[],int low,int high){ int pivot=arr[high]; int i=low; for(int j=low;j<high;j++)//处理low~high-1的元素pivot分离 if(arr[j]<pivot) swap(arr[i++],arr[j]); swap(arr[i],arr[high]); //对小于pivot的最后一个元素的后一位置与pivot交换（包括边界） return i; } void qsort(int arr[],int low,int high){ if(low<high){ int mid=partitioner(arr,low,high); qsort(arr,low,mid-1); qsort(arr,mid+1,high); } } inline int findpivot(int* arr,int i ,int j){ return (i+j)/2; } inline int Partition(int* arr,int left,int right,int pivotindex){ swap(arr[pivotindex],arr[right]); int pivot = arr[right]; int i = left-1, j=right; do{ while(arr[++i] < pivot); while((i < j) && (pivot < arr[--j])); swap(arr[i], arr[j]); }while(i<j); swap(A[i],A[right]); return i; } inline int Partition(int* arr,int left,int right,int pivotindex){ swap(arr[pivotindex],arr[left]); int pivot = arr[left]; int i = left,j=right+1; while(ture){ while(arr[++i]<=pivot && i<right); while(arr[--j]>=pivot && j>left+1); if(i<j) swap(arr[i],arr[j]); else break; } swap(arr[j],arr[left]); return j; } //交换循环中要求对i,j索引有边界限制和qsort交换限制 //交换要求i<j //mid与pivot位置有关，pivot放在右边，则为i（第一个大于pivot的index）；否则为j void qsort(int *arr,int left,int right){ if(left<right){ int pivotindex = findpivot(arr,left,right); int mid=Partition(A,left,right,pivotindex); qsort(A,left,mid-1); qsort(A,mid+1,right); } } merge_sort void merger(int arr[],int temparr[],int left,int mid,int right){ int l_pos=left; int r_pos=mid+1; int pos=left; while(l_pos<=mid&&r_pos<=right) { if(arr[l_pos]<arr[r_pos]) temparr[pos++]=arr[l_pos++]; else temparr[pos++]=arr[r_pos++]; } while(l_pos<=mid) { temparr[pos++]=arr[l_pos++]; } while(r_pos<=right) { temparr[pos++]=arr[r_pos++]; } while(left<=right) { arr[left]=temparr[left]; left++; } } void merge_sort(int arr[],int temparr[],int left,int right) { if(left<right){ int mid=(left+right)/2; merge_sort(arr,temparr,left,mid); merge_sort(arr,temparr,mid+1,right); merger(arr,temparr,left,mid,right); } } 二分法 原理：针对sortedArr，目标位于[left,right]之间，对middle搜索，right+1=left时终止。 ...