网站搭建运营,电子商务网站推广策略,网站维护 关站 seo,培训心得体会怎么写文章目录 一、插入排序#xff08;一#xff09;直接插入排序#xff08;二#xff09;折半插入排序#xff08;三#xff09;希尔排序 二、交换排序#xff08;一#xff09;冒泡排序#xff08;二#xff09;快速排序 三、选择排序#xff08;一#xff09;简单选… 文章目录 一、插入排序一直接插入排序二折半插入排序三希尔排序 二、交换排序一冒泡排序二快速排序 三、选择排序一简单选择排序二堆排序 四、归并排序五、基数排序六、计数排序七、外部排序 一、插入排序
一直接插入排序 算法思想每次将一个待排序元素按其关键字大小插入到已排好序的序列中直至所有元素都被排完。 1.排序过程1)比较将待排序元素与其左侧的已排序序列从后向前比较直至找到它的位置2)移动将其待放位置的原元素与右侧元素全部右移一位3)对下一个待排序元素继续执行1)、2)操作。
2.举个例子
3.算法特点待排序元素左边的序列是已排好序的序列右边的序列是未排序序列。
4.时间复杂度 1)最好情况最好情况是有序序列每个元素只需要和其左侧第一个元素比较一次无需移动故这种情况下的时间复杂度是O(n)。
2)最坏情况最坏情况是倒序序列每个元素要每个元素要和其左侧所有元素比较故这种情况下的时间复杂度是O(n2)。
3)平均情况取上述最好与最坏情况的平均值作为平均情况下的时间复杂度故这种情况下的时间复杂度是O(n2)。
5.空间复杂度仅使用了常数个辅助单元因而空间复杂度为O(1)。
6.是否稳定 因为每次插入元素时总是从后往前先比较再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是一个稳定的排序算法。
7.适用性适用于顺序存储和链式存储的线性表采用链式存储时无须移动元素。
8.C语言代码
void InsertSort(ElemType A[],int n){int i,j;for(i2;in;i){ //依次将A[2]-A[n]插入前面已排序的序列 if(A[i]A[i-1]){ //若A[i]关键码小于其前驱将A[i]插入有序表 A[0]A[i]; //复制为哨兵A[0]不存放元素 for(ji-1;A[0]A[j];--j){ //从后向前查找待插入元素 A[j1]A[j]; //向后挪位 }A[j1]A[0]; //复制到插入位置 }}
}二折半插入排序 算法思想对直接插入排序进行改进折半查找出元素的待插入位置然后统一地移动待插入位置之后的所有元素。 1.排序过程1)比较将待排序元素与其左侧的已排序序列折半比较直至找到它的位置2)移动将其待放位置的原元素与右侧元素全部右移一位3)对下一个待排序元素继续执行1)、2)操作。
2.举个例子
3.算法特点对直接插入排序的改进仅减少了比较元素的次数可以提交时间效率对于数据量不很大的排序表折半插入排序往往能表现出很好的性能。
4.时间复杂度 1)最好情况最好情况是有序序列折半插入排序减少了元素的平均比较次数且折半插入的比较次数与初始状态无关其移动次数与直接插入排序是一样的故在最好情况下每个元素需要比较时间复杂度为O( n l o g 2 n nlog_2{n} nlog2n)其中n是元素个数O( l o g 2 n log_2{n} log2n)是每个元素需要比较的次数。
2)最坏情况最坏情况是倒序序列共n个元素此时每个元素需要比较O( l o g 2 n log_2{n} log2n)次但每个元素需要移动O(n)次所以总的时间复杂度和直接插入排序一样还是O(n2)。
3)平均情况取上述最好与最坏情况的平均值作为平均情况下的时间复杂度故这种情况下的时间复杂度是O(n2)。
5.空间复杂度仅使用了常数个辅助单元因而空间复杂度为O(1)。
6.是否稳定同样值的元素左侧的一定会出现在右侧的前面故是稳定的。
7.适用性涉及到给定数组下标找相应的数组元素的问题所以只适用于顺序存储的线性表。
8.C语言代码
void InsertSort(ElemType A[],int n){int i,j,low,high,mid;for(i2;in;i){ //依次将A[2]-A[n]插入前面已排序的序列 A[0]A[i]; //暂存至A[0]low1;highi-1; //设置折半查找的范围while(lowhigh){mid(lowhigh)/2; //取中间点if(A[mid]A[0]){highmid-1; //查找左半子表 } else loemid1; //查找右半子表 } for(ji-1;jhigh1;--j){A[j1]A[j]; //统一后移元素空出插入位置 }A[high1]A[0]; //插入操作 }
}三希尔排序 算法思想从前面的分析可知直接插入排序算法的时间复杂度为O(n2),但若待排序列为“正序”时其时间效率可提高至O(n),由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的先将待排序表分割成若干形如L[i,id,i2d,⋯,ikd]的“特殊”子表即把相隔某个“增量”的记录组成一个子表对各个子表分别进行直接插入排序当整个表中的元素已呈“基本有序”时再对全体记录进行一次直接插入排序。 1.排序过程取增量d使所有距离为d的元素为一组进行直接插入排序直至d取到1。
2.举个例子
3.算法特点根据希尔排序的特点可以发现在希尔排序的过程中是按增量段有序的可以通过这个特点判断一个排序过程是否是希尔排序或者是以多大增量进行插入排序的希尔排序。
4.时间复杂度因为希尔排序的时间复杂度依赖于增量序列的函数这涉及数学上尚未解决的难题所以其时间复杂度分析比较困难。当n在某个特定范围时希尔排序的时间复杂度约为O(n1.3)。在最坏情况下希尔排序的时间复杂度为O(n2)。
5.空间复杂度仅使用了常数个辅助单元因而空间复杂度为O(1)。
6.是否稳定 由于是按增量进行插入排序可能导致相同值元素相对位置发生变化因此是不稳定的。
7.适用性涉及到给定数组下标找相应的数组元素的问题所以只适用于顺序存储的线性表。
8.C语言代码
void ShellSort(ElemType A[],int n){
//A[0]只是暂存单元不是哨兵当j0时插入位置已到 for(dkn/2;dk1;dkdk/2){ //步长变化 for(idk1;in;i){if(A[i]A[i-dk]){ //需将A[i]插入有序增量子表 A[0]A[i]; //暂存在A[0]; for(ji-dk;j0A[0]A[j];j-dk){A[jdk]A[j]; //记录后移寻找插入的位置 }A[jdk]A[0]; //插入 }}}
}二、交换排序
一冒泡排序 算法思想冒泡排序恰如其名是将最大最小元素一个个浮上水面最终得到有序序列。 1.排序过程从后往前(或从前往后)两两比较相邻元素的值若为逆序(即 A[i-1]A[i]),则交换它们直到序列比较完这称为一次冒泡。重复冒泡直至成为有序序列。
2.举个例子
3.算法特点冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序),也就是说有序子序列中的所有元素的关键字一定小于(或大于)无序子序列中所有元素的关键字这样每趟排序都会将一个元素放置到其最终的位置上因此会有前面的部分元素或者后面的部分元素是有序的。
4.时间复杂度 1)最好情况当初始序列有序时显然第一趟冒泡后flag依然为false(本趟没有元素交换),从而直接跳出循环比较次数为n-1,移动次数为0,从而最好情况下的时间复杂度为O(n)。
2)最坏情况最坏情况是逆序序列此时每个元素需要比较和交换O(n)次所有元素排完序后比较和交换O(n2)次也即时间复杂度为O(n2)。
3)平均情况取上述最好与最坏情况的平均值作为平均情况下的时间复杂度故这种情况下的时间复杂度是O(n2)。
5.空间复杂度仅使用了常数个辅助单元因而空间复杂度为O(1)。
6.是否稳定 如果是从后往前排假如是同值元素后面的元素无法浮到前面的元素的前面也就是相对位置不会改变即算法稳定。
7.适用性冒泡排序适用于顺序存储和链式存储的线性表。
8.C语言代码
void BubbleSort(ElemType A[],int n){for(i0;in-1;i){flagfalse;//表示本趟冒泡是否发生交换的标志for(jn-1;ji;j--){ //一趟冒泡过程 if(A[j-1]A[j]){ //若为逆序 swap(A[j-1],A[j]); //交换 flagtrue;}}if(flagfalse) return; //本趟遍历后没有发生交换说明表已有序 }
}二快速排序 算法思想基于分治法其中分是划分为两部分治是在这两部分上分别采用快速排序。在待排序表L[1.n]中任取一个元素 pivot 作为枢轴(或称基准通常取首元素),通过一趟排序将待排序表划分为独立的两部分L[1⋯k-1]和L[k1⋯n],使得L[1⋯k-1]中的所有元素小于pivot,L[k1.n]中的所有元素大于或等于pivot,则pivot放在了其最终位置L(k)上这个过程称为一次划分。然后分别递归地对两个子表重复上述过程直至每部分内只有一个元素或为空为止即所有元素放在了其最终位置上。 1.排序过程 1)设两个指针i和j,初值分别为low和 high,取第一个元素值为low为枢轴赋值到变量 pivot 2)指针j从high往前搜索找到第一个小于枢轴的元素,将其交换到i所指位置指针i从low往后搜索找到第一个大于枢轴的元素,将其交换到j所指位置 3)重复2)直至ij 4)对pivot两边的元素再从1)开始进行快排。
2.举个例子
3.算法特点快速排序是所有内部排序算法中平均性能最优的排序算法其每趟排序都能确定枢轴元素的最终位置。
4.时间复杂度快速排序的运行时间与划分是否对称有关有很多方法可以提高算法的效率一种方法是尽量选取一个可以将数据中分的枢轴元素如从序列的头尾及中间选取三个元素再取这三个元素的中间值作为最终的枢轴元素或者随机地从当前表中选取枢轴元素这样做可使得最坏情况在实际排序中几乎不会发生。
1)最好情况在最理想的状态下即Partition()能做到最平衡的划分得到的两个子问题的大小都不可能大于 n/2,在这种情况下快速排序的运行速度将大大提升此时时间复杂度为O( n l o g 2 n nlog_2{n} nlog2n)。
2)最坏情况快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时这种最大限度的不对称性若发生在每层递归上即对应于初始排序表基本有序或基本逆序时就得到最坏情况下的时间复杂度为O(n2)。
3)平均情况平均情况下为O(n2)。
5.空间复杂度由于快速排序是递归的因此需要借助一个递归工作栈来保存每层递归调用的必要信息其容量与递归调用的最大层数一致。 1)最好情况最好情况下为O( l o g 2 n log_2{n} log2n)
2)最坏情况最坏情况下要进行n-1次递归调用因此栈的深度为O(n)
3)平均情况平均情况下为O( l o g 2 n log_2{n} log2n)。
6.是否稳定在划分算法中若右端区间有两个关键字相同且均小于基准值的记录则在交换到左端区间后它们的相对位置会发生变化即快速排序是一种不稳定的排序算法。
7.适用性涉及到给定数组下标找相应的数组元素的问题所以只适用于顺序存储的线性表。
8.C语言代码
void QuickSort(ElemType A[],int low,int high){if(lowhigh){ //递归跳出的条件 //Partition()是划分操作将表A划分为满足上述条件的两个子表int pPartition(A,low,high); //划分QuickSort(A,low,p-1); //依次对两个子表进行递归排序QuickSort(A,p1,high); }
}int Partition(ElemType A[],int low,int high){ //一趟划分 ElemType pivotA[low]; //将表中第一个元素设置为枢轴对表进行划分while(lowhigh){ //循环跳出条件 while(lowhighA[high]pivot) --high;A[low]A[high]; //将比枢轴元素小的移动至左端 while(lowhighA[low]pivot) low;A[high]A[hlow]; //将比枢轴元素大的移动至右端 } A[low]pivot; //枢轴元素存放至最终位置
}
三、选择排序
一简单选择排序 算法思想每一趟(如第i趟)在后面n-i1(i1,2,⋯,n-1)个待排序元素中选取关键字最小的元素作为有序子序列的第i个元素直到第n-1趟做完待排序元素只剩下1个就不用再选。 1.排序过程假设排序表为L[1⋯n],第i趟排序即从L[i⋯n]中选择关键字最小的元素与L(i)交换每一趟排序可以确定一个元素的最终位置这样经过n-1趟排序就可使得整个排序表有序。
2.举个例子
3.算法特点排序过程中前面部分或者后面部分的元素是有序的。
4.时间复杂度从上述伪码中不难看出在简单选择排序过程中元素移动的操作次数很少不会超过3(n-1)次最好的情况是移动0次此时对应的表已经有序但元素间比较的次数与序列的初始状态无关始终是n(n-1)/2次因此时间复杂度始终是O(n2)。
5.空间复杂度仅使用常数个辅助单元所以空间效率为O(1)。
6.是否稳定 在第i趟找到最小元素后和第i个元素交换可能会导致第i个元素与含有相同关键字的元素的相对位置发生改变简单选择排序是一种不稳定的排序算法。
7.适用性简单选择排序适用于顺序存储和链式存储的线性表以及关键字较少的情况。
8.C语言代码
void SelectSort(ElemType A[],int n){for(i0;in-1;i){ //共进行n-1趟 mini; //记录最小元素位置 for(ji1;jn;j){ //在A[]中选择最小的元素 if(A[j]A[min]) minj; //更新最小元素位置 }if(min!i)swap(A[i],A[min]);}
}二堆排序 算法思想堆排序的思路很简单先初始化堆然后调整堆。 1.排序过程 1初始化堆将存放在L[1⋯n]中的元素从上至下按层排列成一个堆然后从下至上依次比较左右结点并将较大元素与其对应的父结点交换(以大顶堆为例)因为堆本身的特点所以堆顶元素就是最大值。 2输出堆顶元素后通常将堆底元素送入堆顶此时根结点已不满足大顶堆的性质堆被破坏将堆顶元素向下调整使其继续保持大顶堆的性质再输出堆顶元素。如此重复直到堆中仅剩一个元素为止。 3如果后续再插入先将新结点放在堆的末端再对这个新结点向上执行调整操作。
2.举个例子 1初始化堆 2调整堆 3插入元素
3.算法特点每趟都能确定一个元素在其最终位置。
4.时间复杂度建堆时间为O(n),之后有n-1次向下调整操作每次调整的时间复杂度为O(h),所以在最好、最坏和平均情况下堆排序的时间复杂度为O( n l o g 2 n nlog_2{n} nlog2n)。
5.空间复杂度仅使用了常数个辅助单元所以空间复杂度为O(1)。
6.是否稳定 进行筛选时有可能把后面相同关键字的元素调整到前面所以堆排序算法是一种不稳定的排序算法。
7.适用性堆排序仅适用于顺序存储的线性表。
8.C语言代码
void HeadAdjust(ElemType A[],int k,int len){//函数将k为根的子树进行调整A[0]A[k]; //A[0]暂存子树的根节点for(i2*k;ilen;i*2){if(ilenA[i]A[i1]){i; //取key较大的子结点的下标 }if(A[0]A[i]) break; //筛选结束else{A[k]A[i]; //将A[i]调整到双亲结点上ki; } } A[k]A[0]; //将筛选结点的值放入最终位置
}void BuildMaxHeap(ElemType A[],int len){for(int ilen/2;i0;i--){ //从i[n/2]--1,反复调整堆 HeadAdjust(A,i,len);}
}void HeapSort(ElemType A[],int len){BuildMaxHeap(A,len); //初始建堆for(ilen;i1;i--){ //n-1趟的交换和建堆的过程 Swap(A[i],A[1]); //输出堆顶元素和堆底元素交换 HeadAdjust(A,1,i-1); //调整把剩余的i-1个元素整理成堆 }
}四、归并排序 算法思想归并排序与上述基于交换、选择等排序的思想不一样归并的含义是将两个或两个以上的有序表合并成一个新的有序表。 1.排序过程假定待排序表含有n个记录则可将其视为n个有序的子表每个子表的长度为1,然后两两归并得到「n/2]个长度为2或1的有序表继续两两归并⋯⋯如此重复直到合并成一个长度为n的有序表为止这种排序算法称为二路归并排序。
2.举个例子
3.算法特点逐段有序。
4.时间复杂度每趟归并的时间复杂度为O(n),共需进行「log?n]趟归并因此算法的时间复杂度为O( n l o g 2 n nlog_2{n} nlog2n)。
5.空间复杂度Merge()操作中辅助空间刚好为n个单元因此算法的空间复杂度为O(n)。
6.是否稳定 由于 Merge()操作不会改变相同关键字记录的相对次序因此二路归并排序算法是一种稳定的排序算法。
7.适用性归并排序适用于顺序存储和链式存储的线性表。
8.C语言代码
int *B(int *)malloc(n*sizeof(int)); //辅助数组B//A[low...mid]和A[mid...high]各自有序将两个部分归并
void Merge(int A[],int low,int mid,int high){int i,j,k;for(klow;khigh;k)B[k]A[k]; //将A中所有元素复制到B中for(ilow,jmid1,ki;imidjhigh;k){if(B[i]B[j])A[k]B[i]; //将较小值复制到A中elseA[k]B[j]; } while(imid) A[k]B[i];while(jhigh) A[k]B[j];
} void MergeSort(int A[],int low,int high){if(lowhigh){int mid(lowhigh)/2; //从中间划分MergeSort(A,low,mid); //对左半部分进行归并排序MergeSort(A,mid1,high); //对右半部分进行归并排序Merge(A,low,mid,high); //归并 }
}五、基数排序 算法思想基数排序是一种很特别的排序算法它不基于比较和移动进行排序而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。 1.排序过程
2.举个例子
3.算法特点逐位有序。
4.时间复杂度基数排序需要进行d趟“分配”和”收集”操作。一趟分配需要遍历所有关键字时间复杂度为O(n)一趟收集需要合并r个队列时间复杂度为O®。因此基数排序的时间复杂度为O(d(nr)),它与序列的初始状态无关。
5.空间复杂度一趟排序需要的辅助存储空间为r(r个队列r个队头指针和r个队尾指针),但以后的排序中会重复使用这些队列所以基数排序的空间复杂度为O®。
6.是否稳定 每一趟分配和收集都是从前往后进行的不会交换相同关键字的相对位置因此基数排序是一种稳定的排序算法。
7.适用性基数排序适用于顺序存储和链式存储的线性表。
8.C语言代码
void RadixSort(int* arr, int n){//max为数组中最大值int max arr[0];int base 1;//找出数组中的最大值for (int i 0; i n; i){if (arr[i] max){max arr[i];}}//循环结束max就是数组最大值//临时存放数组元素的空间int* tmp (int*)malloc(sizeof(int)*n);//循环次数为最大数的位数while (max / base 0){//定义十个桶桶里面装的不是数据本身而是每一轮排序对应十、白、千...位的个数//统计每个桶里面装几个数int bucket[10] { 0 };for (int i 0; i n; i){//arr[i] / base % 10可以取到个位、十位、百位对应的数字bucket[arr[i] / base % 10];}//循环结束就已经统计好了本轮每个桶里面应该装几个数//将桶里面的元素依次累加起来就可以知道元素存放在临时数组中的位置for (int i 1; i 10; i){bucket[i] bucket[i - 1];}//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置//开始放数到临时数组tmpfor (int i n - 1; i 0; i--){tmp[bucket[arr[i] / base % 10] - 1] arr[i];bucket[arr[i] / base % 10]--;}//不能从前往后放因为这样会导致十位排好了个位又乱了百位排好了十位又乱了//把临时数组里面的数拷贝回去for (int i 0; i n; i){arr[i] tmp[i];}base * 10;}free(tmp);
}六、计数排序 算法思想计数排序也是一种不基于比较的排序算法。计数排序的思想是对每个待排序元素x,统计小于x的元素个数利用该信息就可确定x的最终位置。 1.排序过程假设输入是一个数组 A[n],序列长度为 n,我们还需要两个数组B[n]存放输出的排序序列c[k]存储计数值。用输入数组A中的元素作为数组c的下标(索 引),而该元素出现的次数存储在该元素作为下标的数组c中。
2.举个例子
3.算法特点计数排序适用于序列中的元素是整数。
4.时间复杂度上述代码的第1个和第3个 for循环所花的时间为O(k),第2个和第4个 for 循环所花的时间为O(n),总时间复杂度为O(nk)。因此当kO(n)时计数排序的时间复杂度为O(n);但当kO(nlogn)时其效率反而不如一些基于比较的排序(如快速排序、堆排序等)。
5.空间复杂度计数排序是一种用空间换时间的做法。输出数组的长度为n;辅助的计数数组的长度为k,空间复杂度为O(nk)。若不把输出数组视为辅助空间则空间复杂度为O(k)。
6.是否稳定 相同元素在输出数组中的相对位置不会改变因此计数排序是一种稳定的排序算法。
7.适用性计数排序更适用于顺序存储的线性表。计数排序适用于序列中的元素是整数且元素范围(0k-1)不能太大否则会造成辅助空间的浪费。
8.C语言代码
void CountSort(ElemType A[],ElemType B[],int n,int k){int i,c[k];for(i0;ik;i){c[i]0; //初始化计数数组} for(i0;in;i){ //遍历输入数组统计每个元素出现的次数C[A[i]]; //c[A[i]]保存的是等于A[i]的元素个数}for(i1;ik;i){c[i]C[i]C[i-1]; //C[x]保存的是小于或等于x的元素个数}for(in-1;i0;i--){ //从后往前遍历输入数组B[C[A[i]-1]]A[i]; //将元素A[i]放在输出数组 B[]的正确位置上C[A[i]]C[A[i]]-1;}
}七、外部排序 算法思想上述排序算法都是内部排序而在许多应用中经常需要对大文件进行排序因为文件中的记录很多无法将整个文件复制进内存中进行排序。因此需要将待排序的记录存储在外存上排序时再把数据一部分一部分地调入内存进行序在排序过程中需要多次进行内存和外存之间的交换。这种排序算法就称为外部排序。 1.排序过程外部排序通常采用归并排序算法。它包括两个阶段①根据内存缓冲区大小将外存上的文件分成若干长度为C的子文件依次读入内存并利用内部排序算法对它们进行排序并将排序后得到的有序子文件重新写回外存称这些有序子文件为归并段或顺串②对这些归并段进行逐趟归并使归并段(有序子文件)逐渐由小到大直至得到整个有序文件为止。
为减少平衡归并中外存读/写次数以提高排序速度所采取的方法增大归并路数和减少归并段个数。 ①利用败者树增大归并路数
②利用置换-选择排序增大归并段长度来减少归并段个数
③由长度不等的归并段进行多路平衡归并需要构造最佳归并树。
关于提高外部排序速度的三种方式我将在下一篇文章中说明【408精华知识】提高外部排序速度的三种方式
3.时间效率文件通常是按块存储在磁盘上的操作系统也是按块对磁盘上的信息进行读/写的。因为磁盘读/写的机械动作所需的时间远远超过在内存中进行运算的时间(相比而言可以忽略不计),因此在外部排序过程中的时间代价主要考虑访问磁盘的次数即 I/O 次数。
小总结 1我们大致可以发现与二叉树、折半有关的排序其时间复杂度都有log这可以帮助我们记忆各种排序的时间复杂度。 2在排序过程中每趟都能确定一个元素在其最终位置的有冒泡排序、简单选择排序、堆排序、快速排序其中前三者能形成全局有序的子序列后者能确定枢轴元素的最终位置。 3内部排序在内存中进行的排序包括插入、交换、选择、归并、基数、计数。
写在后面 这个专栏主要是我在学习408真题的过程中总结的一些笔记因为我学的也很一般如果有错误和不足之处还望大家在评论区指出。希望能给大家的学习带来一点帮助共同进步! 参考文献 [1]王道408教材2025版
