免费设计图片素材网站,什么是wordpress程序,做免费网站需要营业执照吗,wordpress模板仿新版虎嗅huxiu-new主题文章目录一、排序定义二、插入排序——直接插入排序1. 描述2. 代码和示例3. 空间效率4. 时间效率5. 稳定性6. 适用性三、插入排序——折半插入排序1. 描述2. 时间效率3. 稳定性四、插入排序——希尔排序#xff08;缩小增量排序#xff09;1. 描述2. 代码和示例3. 空间效率4.…
文章目录一、排序定义二、插入排序——直接插入排序1. 描述2. 代码和示例3. 空间效率4. 时间效率5. 稳定性6. 适用性三、插入排序——折半插入排序1. 描述2. 时间效率3. 稳定性四、插入排序——希尔排序缩小增量排序1. 描述2. 代码和示例3. 空间效率4. 时间效率5. 稳定性6. 适用性五、交换排序——冒泡排序1. 描述2. 代码和示例3. 空间效率4. 时间效率5. 稳定性六、交换排序——快速排序1. 描述2. 代码和示例3. 空间效率4. 时间效率5. 稳定性七、选择排序——简单选择排序1. 描述2. 代码3. 空间效率4. 时间效率5. 稳定性八、选择排序——堆排序1. 堆的定义2. 建堆构造初始堆3. 删除结点4. 插入结点5. 算法与示例6. 空间效率7. 时间效率8. 稳定性9. 适用性九、归并排序1. 描述2. 代码和示例3. 空间效率4. 时间效率5. 稳定性十、基数排序1. 描述2. 算法和示例3. 空间效率4. 时间效率5. 稳定性十一、排序算法的比较一、排序定义
重新排列表中的元素使表中的元素满足按关键字有序。 算法的稳定性带排序表中关键字相同的元素其相对次序在排序前后不变这称这个排序算法是稳定的。算法是否稳定并不能衡量一个算法的优劣。如果带排序表中的关键字均不重复则排序结果是唯一的算法的稳定性就无关紧要。
大部分的内部排序都需要执行比较和移动操作。通过比较两个关键字的大小确定对应元素的前后关系然后通过移动元素以达到有序。
在基于比较的排序方法中每次比较两个关键字大小之后仅出现两种可能的转移。因此可以用一棵二叉树来描述比较判定过程由此可以证明当文件的 n 个关键字随机分布时任何借助比较的排序算法至少需要O(nlog2n)O(n\log_2n)O(nlog2n)的时间。
二、插入排序——直接插入排序
1. 描述
插入排序是一种简单直观的排序方法其基本思想是将一个待排序的记录按其关键字大小插入前面已排好序的子序列。 插入排序通常采用就地排序在从后向前的比较过程中需要反复把已排序元素逐步向后挪位为新元素腾出插入空间。
2. 代码和示例
下面是直接插入排序的代码
void insertSort(ElemType A[], int n){int i, j;for(i 2; i n; i){ // 依次对A[2]到A[n]进行插入排序if (A[i] A[i-1]){ // 如果当前元素小于其前驱将其插入前面序列A[0] A[1]; // 哨兵A[0]不存放元素for(j i-1; A[0] A[j]; j--) // 从后往前查找待插入位置A[j1] A[j]; // 元素挨个往后挪位A[j1] A[0]; // 最后一次循环j指向待插入点的前一个位置。}}
}这里哨兵的作用是防止数组下标越界提高查找效率
3. 空间效率
就地排序仅使用了常数个辅助单元空间复杂度为O(1)O(1)O(1)
4. 时间效率
排序过程中向有序子表中逐个插入元素的操作进行了n-1趟每趟操作都分为比较关键字和移动元素次数取决于待排序表的初始状态。
在最好情况下表中元素已经有序此时每插入一个元素都只需一次比较而不需要移动元素。时间复杂度为O(n)O(n)O(n) 在最坏情况下。表中元素的顺序刚好与排序结果相反逆序总的比较次数达到最大为∑i2ni\sum^n_{i2}i∑i2ni总的移动次数也达到最大为∑i2n(i1)\sum^n_{i2}(i1)∑i2n(i1) 在平均情况下考虑待排序表中的元素是随机的此时取最好与最坏情况的平均值作为平均情况的时间复杂度。总的比较次数和总的移动次数均为n24\frac{n^2}44n2。 因此直接插入排序的时间复杂度为O(n2)O(n^2)O(n2)。
5. 稳定性
每次插入元素总是从后往前先比较在移动算法是稳定的。
6. 适用性
直接插入排序算法时使用与顺序储存大部分排序算法仅适用于顺序储存的线性表和链式储存。
其更适用于基本有序、数据量不大的排序表。
三、插入排序——折半插入排序
1. 描述
对于顺序表对插入位置的查找过程可以采用折半查找来实现。确定待插入位置后再统一向后移动元素。
2. 时间效率
折半插入排序减少了比较元素的次数总比较次数约为O(nlog2n)O(n\log_2n)O(nlog2n)该比较次数与表的初始状态无关仅取决于表中元素的个数 而元素的移动次数并未改变仍依赖于表的初始状态。 因此时间复杂度仍为O(n2)O(n^2)O(n2)。
但对于数据量不是很大的排序表折半插入排序往往表现出很好的性能。
3. 稳定性
折半插入排序是一种稳定的排序方法。
四、插入排序——希尔排序缩小增量排序
1. 描述
基本思想先将待排序表分割成若干形如[i,id,i2d,⋯,ikd][i,id,i2d,\cdots,ikd][i,id,i2d,⋯,ikd]的特殊子表即把相隔某个增量的记录组成一个子表对各个子表进行直接插入排序当整个表中的元素已呈“基本有序”时,再对全体记录进行一次直接插入排序。
希尔排序的过程如下
先取一个小于 n 的步长 d1d_1d1把表中的全部记录分成d1d_1d1组所有距离为d1d_1d1倍数的记录放在同一组在各组内进行直接插入排序取第二个步长d2(d2d1)d_2(d_2d_1)d2(d2d1)重复第二、三步。不断取更大步长直到dt1d_t1dt1即所有记录已放在同一组中再进行一次直接插入排序。由于此时已经具有了较好的局部有序性故可以很快得到最终结果。
通常步长did_idi的取值为d1n2,di1⌊di2⌋,d最后一个1d_1\frac n2,d_{i1}\lfloor \frac {d_i}2\rfloor,d_{最后一个}1d12n,di1⌊2di⌋,d最后一个1
2. 代码和示例
希尔排序的代码如下
void shellSort(Elemtpye A[], int n){int dk, i, j;for(dk n/2; dk 1; dk dk/2){// 将各个子表的直接插入排序分解合并为一个循环一次循环过程仅按顺序处理一个元素// 从第1个子表的第二个元素开始第二次循环进行第2个子表的第二个元素for(i dk1; i n; i){if(A[i] A[i-dk]) // 仅在当前元素无序时进行排序continue;A[0] A[i]; // A[0]不是哨兵仅暂存元素// j小于等于0时说明该元素在该子表的已排序序列中最小for(j i-dk; j 0 A[0] A[j]; j - dk) A[jdk] A[j];A[jdk] A[0];}}
}3. 空间效率
仅使用了常数个辅助单元空间复杂度为O(1)O(1)O(1)
4. 时间效率
当n在某个特定范围时希尔排序的时间复杂度约为O(n1.3)O(n^{1.3})O(n1.3)。 在最坏情况下希尔排序的时间复杂度为O(n2)O(n^2)O(n2)。
5. 稳定性
当相同关键字的记录被划分到不同子表时可能会改变它们之间的相对次序因此希尔排序是一种不稳定的排序方法。
6. 适用性
希尔排序对较大规模的排序都可以达到很高的效率。
仅适用于顺序存储的线性表。
五、交换排序——冒泡排序
1. 描述
所谓交换是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。
基本思想从后往前或从前往后两两比较相邻元素的值若为逆序则交换它们直到序列比较完这称为一趟冒泡。一趟冒泡的结果是将最小或最大元素交换到待排序的第一个位置。下一趟冒泡时已确定位置的元素不再参与比较。这样最多做n-1趟冒泡就可以把所有元素排好。
冒泡排序中所产生的有序子序列一定是全局有序的每趟排序都会将一个元素放在其最终位置。
2. 代码和示例
冒泡排序算法代码如下
void bubbleSort(ElemType A[], int n){for(i 0; i n-1; i ){flag false; // 标志位记录本趟冒泡是否发生交换for(int j n-1; j i; j--){ // 一趟冒泡顺序与外层循环相反if(A[j-1] A[j]){ swap(A[j-1], A[j]);flag true;}}if( !flag ) // 若某趟冒泡过程没有发生交换说明表已经有序return;}
}3. 空间效率
仅使用了常数个辅助单元空间复杂度为O(1)O(1)O(1)。
4. 时间效率
最好情况下当初始序列有序时第一趟冒泡标志位flag仍为false直接跳出循环比较次数为n-1移动次数为0时间复杂度为O(n)O(n)O(n) 最坏情况下当初始序列逆序时需要进行n-1趟排序第 i 趟排序要进行 n-i 次关键字的比较而且每次比较后都必须进行三次移动来交换元素的位置。比较次数∑i1n−1(n−i)n(n−1)2移动次数∑i1n−13(n−i)3n(n−1)2比较次数\sum^{n-1}_{i1}(n-i)\frac{n(n-1)}2移动次数\sum^{n-1}_{i1}3(n-i)\frac{3n(n-1)}2比较次数i1∑n−1(n−i)2n(n−1)移动次数i1∑n−13(n−i)23n(n−1)从而最坏情况下时间复杂度为O(n2)O(n^2)O(n2) 平均情况下时间复杂度为O(n2)O(n^2)O(n2)。
5. 稳定性
冒泡排序时一种稳定的排序方法。 如果把代码中判断是否逆序的条件由“”改为“≥”则算法变得不稳定。
六、交换排序——快速排序
1. 描述
快速排序的基本思想是基于分治法的在待排序表中选取一个元素称为枢轴或称基准常取首元素。通过一趟排序将待排序表分成两部分一部分中所有元素均小于枢轴另一部分元素均大于枢轴两部分分别位于枢轴元素的两侧这个过程称为一趟快速排序或一次划分。然后递归地分别对两个子表重复上述过程直到每部分只有一个元素或空为止此时所有元素都放在了最终位置。
快速排序并不产生有序子序列但每趟排序后会将枢轴元素放在最终位置上。
2. 代码和示例
一趟快速排序是一个交替搜索和交换的过程算法如下
void quickSort(ElemType A[], int low, int high){if(low high) // 递归跳出条件。只有一个元素或为空return;// 一趟快排将表划分为两个子表返回枢轴位置int pivotpos partition(A, low, high); quickSort(A, low, pivotpos-1); // 对左子表进行递归quickSort(A, pivotpos1, high); // 对右子表进行递归
}// 一趟划分交替进行搜索交换
int partition(ElemType A[], int low, int high){ElemType pivot A[low]; // 设为枢轴while(low high){ // 从high往前搜索找到最近的小于枢轴的元素// 将其置入枢轴或者上一次交换留出空位中while(low high A[high] pivot) high--;A[low] A[high];// 从low往后搜索找到最近的大于枢轴的元素// 将其置入上一次交换留出的空位中。while(low high A[low] pivot)low;A[high] A[low];}A[low] pivot; // 将枢轴元素置入交替搜索后留出的空位中。return low; // 返回枢轴位置
}3. 空间效率
快排是递归地需要借助一个递归工作栈来保持每层递归调用的必要信息容量与递归调用的最大深度一致。 最好情况下空间复杂度为O(log2n)O(\log_2n)O(log2n) 最坏情况下因为要进行n-1次递归调用栈的深度为O(n)O(n)O(n) 平均情况下栈的深度为O(log2n)O(\log_2n)O(log2n)。
4. 时间效率
快速排序的运行时间和划分是否对称有关。 最好情况下partition()可以做到最平衡的划分得到的两个子问题大小都不大于n/2这种情况下快速排序的运行速度将大大提升此时时间复杂度为O(nlog2n)O(n\log_2n)O(nlog2n) 最坏情况下划分的两个区域分别包含n-1个元素和0个元素。若初始表基本有序或基本逆序时每层递归都出现最坏情况。此时时间复杂度为O(n2)O(n^2)O(n2) 平均情况下的快速排序与其最佳情况的运行时间很接近时间复杂度为O(nlog2n)O(n\log_2n)O(nlog2n)。
有很多方法可以提升算法的效率一种方法时尽可能选择一个可以将数据平分的枢轴如从序列的头尾和中间选取三个元素选择三个元素的中间值作为枢轴或随机从表中选取一个枢轴这样做可以时最坏情况几乎不会出现。
快速排序是所有内部排序中平均性能最优的排序算法。
5. 稳定性
某一趟中两个关键字相同的元素从一个区间被交换到另一个区间的过程中相对位置会发生变化。快速排序是一种不稳定的排序方法。
七、选择排序——简单选择排序
1. 描述
基本思想每一趟排序后将剩余待排序元素中选择关键字最小或最大的元素放在其最终位置最终位置的原有元素与其交换位置。
2. 代码
简单选择排序代码如下
void selectSort(ElemType A[], int n){for(int i 0; i n-1; i){ // 到第n-1趟待排元素只剩一个就不用再选了int min i;for(int j i1; j n; j){ // 选择待排序列中的最小元素if(A[j] A[i])min j;}if(min ! i)swap(A[i], A[min]);}
}3. 空间效率
仅使用常数个辅助单元空间效率为O(1)O(1)O(1)。
4. 时间效率
在简单选择排序中元素移动的次数很少不会超过3(n−1)3(n-1)3(n−1)次最好情况是移动0次此时对应表已有序。但元素的比较次数和序列的初始状态无关始终是n(n−1)2\frac{n(n-1)}22n(n−1)次因此时间复杂度始终是O(n2)O(n^2)O(n2)
5. 稳定性
在第 i 趟把最小元素和第 i 个元素进行交换时可能导致第 i 个元素与其后含有相同关键字元素的相对位置发生变化。简单选择排序是不稳定的。
八、选择排序——堆排序
1. 堆的定义
若n个关键字序列满足以下任一条件 {L(i)⩾L(2i)∧L(i)⩾L(2i1)(1⩽i⩽⌊n2⌋)L(i)⩽L(2i)∧L(i)⩽L(2i1)\left\{ \begin{array}{l} L(i)\geqslant L(2i)\wedge L(i)\geqslant L(2i1)(1\leqslant i\leqslant\lfloor\frac n2\rfloor)\\ L(i)\leqslant L(2i)\wedge L(i)\leqslant L(2i1) \end{array} \right. {L(i)⩾L(2i)∧L(i)⩾L(2i1)L(i)⩽L(2i)∧L(i)⩽L(2i1)(1⩽i⩽⌊2n⌋) 该序列称为堆。
堆可以视为一棵顺序存储的完全二叉树满足第一个条件的称为大根堆其最大元素放在根节点且堆的非叶结点的值均大于其左右子树。满足第二个条件的称为小根堆。
2. 建堆构造初始堆
n个结点的完全二叉树其最后一个非叶结点序号是⌊n2⌋\lfloor \frac n2\rfloor⌊2n⌋。从最后一个非叶结点开始往前一次遍历结点对每一个以当前结点为根的子树进行检查对于大根堆若根结点关键字小于左右孩子将左右孩子中较大者与之交换小根堆反之交换后可能破坏下一级的堆因此对下一级的堆重复进行检查和交换直到以当前结点为根的子树构成堆为止。
下面是建立大根堆的算法
void buildMaxHeap(ElemType A[], int len){for(int i len/2; i 0; i--) // 从最小非叶结点开始反复调整堆headAdjust(A, i, len);
}void headAdjust(ElemType A[], int k, int len){A[0] A[k]; // 暂存子树根节点for(int i 2*k; i len; i * 2){ // 沿key值较大的结点往下if(i len A[i1] A[i]) // 左右子树在顺序表中总是相邻i; // 选择key值较大的结点if(A[0] A[i]) // 当前堆已满足性质break;A[k] A[i]; // 调整结点k i; // 进入较大叶结点的子树}A[k] A[0];
}调整的时间与数高h有关为O(h)O(h)O(h)。 在建含 n 个元素的堆时关键字的比较总次数不超过4n时间复杂度为O(n)O(n)O(n)这说明可以在线性时间将一个无序数组建成一个堆。
3. 删除结点
堆的删除通常在根节点处此时需要重新调整结构以保持性质。
输出堆顶元素后将堆底元素移到堆顶。再从堆顶元素开始向下调整使其保持大堆顶的性质。
4. 插入结点
对堆进行插入时先将新结点放在堆的末端再对这新结点向上执行调整操作。
5. 算法与示例
下面给出堆排序算法即依次删除根节点的算法
void heapSort(ElemType A[], int len){buildMaxHeap(A, len); // 建立初始堆// 进行n-1趟交换和建堆过程。当i1时仅剩根节点此时数组已经有序for(int i len; i 1; i--){ // 输出堆顶元素和堆底元素进行交换此时数组中i~len的元素已经是全局有序的了swap(A[i], A[1]); headAdjust(A, 1, i-1); // 把剩余i-1个元素元素整理成堆}
}建立初始堆的示例如下
输出根节点87将最后一个叶节点09置于根的位置将剩余元素调整成新堆调整 在堆的末端插入新结点重新调整堆
6. 空间效率
仅使用了常数个辅助单元空间复杂度为O(1)O(1)O(1)
7. 时间效率
建堆时间为O(n)O(n)O(n)之后有n-1次向下调整操作每次调整时间复杂度为O(h)。故在最好、最坏和平均情况下堆排序的时间复杂度O(nlog2n)O(n\log_2n)O(nlog2n)。
8. 稳定性
在进行筛选时有可能把后面相同关键字的元素调整到前面所以堆排序时一种不稳定的排序方法。
9. 适用性
堆排序适合关键字较多的情况。
九、归并排序
1. 描述
假定待排序表含有n 个记录则可将其视为n个有序的子表每个子表长度为1。然后两两归并称为2路归并排序再将得到的长度为2或1的有序表两两归并如此重复直到合并成一个长度为n的有序表为止。
2. 代码和示例
递归形式的归并排序算法时基于分治的分为分解和合并两个步骤
void mergeSort(ElemType A[], int low, int high){if(low heigh){ // 递归退出条件当lowheigh时子表长度为1停止分解int mid (low high) / 2; // 分解划分两个子表对两个子表递归地进行排序mergeSort(A, low, mid); mergeSort(A, mid1, high);merge(A, low, mid, high); // 归并合并两个已经排序的子表得到新的排序结构}
}// 设立一个辅助数组
ElemType *B (ElemType *)malloc( (n1)*sizeof(ElemType) ); // 归并两个子表的过程与合并两个有序链表的算法过程类似
void merge(ElemType A[], int low, int mid, int high){int i, j, k;for(i low; i high; i) // 将两个子表中所有元素复制到B中的对应位置B[i] A[i];for(i low, j mid1, k low; i mid j high; k){if(B[i] B[j])A[k] B[i];elseA[k] B[j];}while(i mid)A[k] B[i];while(j high)A[k] B[j];}3. 空间效率
merge()操作中辅助空间刚好为n个单元空间复杂度为O(n)O(n)O(n)。
4. 时间效率
每趟归并的时间复杂度为O(n)O(n)O(n)需要进行⌈log2n⌉\lceil\log_2n\rceil⌈log2n⌉趟归并所以算法的时间复杂度为O(nlog2n)O(n\log_2n)O(nlog2n)。
一般而言对于N个元素进行 k 路归并排序时排序的趟数 m 满足kmNk^mNkmN从而m⌈logkN⌉m\lceil\log_kN\rceilm⌈logkN⌉。
从单个记录起进行两两归并并不值得提倡通常将它和直接插入排序结合。改进后的归并排序仍是稳定的。
5. 稳定性
merge()操作并不会改变相同关键字记录的相对次序算法是稳定的。
十、基数排序
1. 描述
基数排序十一种很特别的排序方法它基于比较和移动进行排序而基于关键字各位的大小进行排序。技术排序是一种借助多关键字排序的思想以对单逻辑关键字进行排序的方法。
假设长度为 n 的线性表中每个结点aja_jaj的关键字由 d 元组(kjd−1,kjd−2,⋯,kj1,kj0)(k_j^{d-1},k_j^{d-2},\cdots,k_j^1,k_j^0)(kjd−1,kjd−2,⋯,kj1,kj0)组成满足0≤kji≤r−10\leq k_j^i\leq r-10≤kji≤r−1。其中kjd−1k_j^{d-1}kjd−1称为最主位关键字kj0k_j^0kj0称为最次位关键字。
为实现多关键字排序通常由两种方法
最高位优先MSD按关键字位权重递减依次逐层划分成若干更小的子序列最后将所有子序列依次连接成一个有序序列。最低位优先LSD按关键字位权重递增依次进行排序最后形成一个有序子序列。
2. 算法和示例
下面描述以 r 为基数的最低位优先基数排序的过程 在排序过程中使用 r 个队列Q0,Q1,⋯,Qr−1Q_0,Q_1,\cdots,Q_{r-1}Q0,Q1,⋯,Qr−1。基数排序的过程如下 从i0开始数字最低位依次做一次“分配”和“收集”。
分配开始时把Q0,Q1,⋯,Qr−1Q_0,Q_1,\cdots,Q_{r-1}Q0,Q1,⋯,Qr−1各个队列置空然后依次考察线性表中的每个结点aj(j0,1,⋯,n−1)a_j(j0,1,\cdots,n-1)aj(j0,1,⋯,n−1)若aja_jaj关键字kjikk_j^ikkjik就把aja_jaj放进QkQ_kQk队列中。收集把Q0,Q1,⋯,Qr−1Q_0,Q_1,\cdots,Q_{r-1}Q0,Q1,⋯,Qr−1各个队列首位相接得到新的结点序列从而组成新的线性表。
通常采用链式基数排序假设对如下10个记录进行排序 每个关键字是1000以下的正整数由3位子关键字K1K2K3K^1K^2K^3K1K2K3构成分别代表百位、十位、个位一共需要进行三趟分配-收集操作。基数r10在排序过程中需要借助10个链队列。
第一趟分配用最低位关键字个位K3K^3K3进行。将所有K3K^3K3相等的记录分配到同一个队列然后进行收集。 第二趟分配用次低位关键字十位K2K^2K2进行将所有K2K^2K2相等的记录分配到同一个队列然后进行收集。 第三趟分配用最高位关键字百位K1K^1K1进行将所有K3K^3K3相等的记录分配到同一个队列然后进行收集。自此整个排序结束
3. 空间效率
一趟排序需要辅助空间为 rr个队列r个队头指针和队尾指针。空间复杂度为O(r)O(r)O(r)。
4. 时间效率
基数排序需要进行 d 趟分配和收集一趟分配需要O(n)O(n)O(n)一趟收集需要O(r)O(r)O(r)。所以基数排序的时间复杂度为O(d(nr))O(d(nr))O(d(nr))其与序列的初始状态无关。
5. 稳定性
基数排序是稳定的。
十一、排序算法的比较
算法种类时间复杂度空间复杂度是否稳定最好情况最坏情况平均情况直接插入排序插入排序O(n)O(n2)O(n2)O(1)稳定冒泡排序交换排序O(n)O(n2)O(n2)O(1)稳定简单选择排序选择排序O(n2)O(n2)O(n2)O(1)不稳定希尔排序插入排序依赖增量函数O(1)不稳定快速排序交换排序O(n2)最坏情况下是O(n)不稳定堆排序选择排序O(1)不稳定2路归并排序O(n)稳定基数排序O(d(nr))O(d(nr))O(d(nr))O(r)稳定
在实际应用中快速排序往往可以优于其他算法被认为是目前基于比较的内部排序中最好的方法。冒泡排序和堆排序每趟处理后都能产生当前的最大值或最小值。快速排序一趟处理就能确定一个元素的最终位置。若 n 较小可以采用直接插入排序或简单选择排序 由于直接插入排序所需的记录移动次数较简单选择排序多当记录本身信息量较大时选用简单选择排序较好。 若文件的初始状态已经按关键字基本有序选用直接插入排序或冒泡排序。若 n 较大则应采用时间复杂度为Olog2n)O\log2n)Olog2n)的排序方法快速排序、推排序或归并排序 当关键字随机分布时快速排序平均时间最短堆排序所需的辅助空间少于快速排序且不会出现快速排序可能出现的最坏情况若要求排序稳定则可选用归并排序。 若 n 很大、记录的关键字位数较少且可以分解时采用基数排序较好当记录本身信息量较大时为避免耗费大量时间移动记录可以采用链表作为存储结构。
