苏州市建设局网站,百度站长工具网站认证,河北省石家庄市官网,如何获取wordpress后台登入网址一、插入排序 基本思想#xff1a; 每次将一个待排序的对象#xff0c;按其关键码大小#xff0c;插入到前面已经排好序的一组对象的适当位置上#xff0c;直到对象全部插入为止。即边插入边排序#xff0c;保证子序列中随时都是排好序的。 基本操作——有序插入#xff…一、插入排序 基本思想 每次将一个待排序的对象按其关键码大小插入到前面已经排好序的一组对象的适当位置上直到对象全部插入为止。即边插入边排序保证子序列中随时都是排好序的。 基本操作——有序插入 在有序序列中插入一个元素保持序列有序有序长度不断增加起初a[0]a[0]a[0]是长度为1的子序列。然后逐一将a[1]a[1]a[1]至a[n−1]a[n-1]a[n−1]插入到有序子序列中。 基本操作——有序插入方法 在插入a[i]a[i]a[i]前数组a的前半段a[0]a[0]a[0]a[i−1]a[i-1]a[i−1]是有序段后半段a[i]a[i]a[i]a[n−1]a[n-1]a[n−1]是停留于输入次序的无序段插入a[i]a[i]a[i]使a[0]a[0]a[0]a[i]a[i]a[i]有序也就是要为a[i]a[i]a[i]找到有序位置jjj(0⩽j⩽i0 \leqslant j \leqslant i0⩽j⩽i)将a[i]a[i]a[i]插入在a[j]a[j]a[j]的位置上。 1. 直接插入排序 基本思想 采用顺序查找法查找插入位置 性能分析 算法的时间复杂度为O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1) 稳定性 稳定。 #include iostream
#include vector
using namespace std;/*
* brief: 直接插入排序
* param v: 待排序序列引用
*/
void insertSort(vectorint v)
{int temp; // 辅助空间用于记录每次要插入的元素值for (int i 1; i v.size(); i) // 认定v[0]已经有序所以i从1开始{temp v[i];int j;for (j i - 1; j 0; j--) // 在[0, i-1]中找temp应该插入的位置{if (v[j] temp){v[j 1] v[j]; // 记录后移一位}else // 说明v[0...j]的值都比temp小无需再比{break;}}v[j 1] temp; // j1就是temp要插入的位置 }
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 0,5,3,4,6,2 };cout 排序前 endl;printVec(v);// 排序insertSort(v);cout 排序后 endl;printVec(v);
}2. 二分插入排序 基本思想 采用折半查找法查找插入位置 性能分析 算法的时间复杂度为O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1) 稳定性 稳定。 #include iostream
#include vector
#include assert.h
using namespace std;/*
* brief: 二分插入排序
* param v: 待排序序列引用
*/
void BinsertSort(vectorint v)
{int temp; // 辅助空间用于记录每次要插入的元素值for (int i 1; i v.size(); i) // 认定v[0]已经有序所以i从1开始{temp v[i];// 利用二分法在[0, i-1]中找temp应该插入的位置int low 0, high i - 1;while (low high){ int mid (low high) / 2;if (v[mid] temp){high mid - 1;}else{low mid 1;}} // low就是该插入的位置// 将[low, i-1]处的元素依次向后移动一位for (int j i - 1; j low; j--){v[j 1] v[j];}v[low] temp; // low就是temp要插入的位置 }
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序BinsertSort(v);cout 排序后 endl;printVec(v);
}3. 希尔排序 基本思想 先将整个待排记录序列分割成若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序 性能分析 算法的时间复杂度为O(n1.3)O(n^{1.3})O(n1.3)空间复杂度O(1)O(1)O(1) 稳定性 不稳定。 特点 缩小增量多遍插入排序 思路 定义增量序列DkDMDM−1...D11D_{k}D_{M}D_{M-1}...D_{1}1DkDMDM−1...D11对每个DkD_{k}Dk进行“Dk−间隔D_{k}-间隔Dk−间隔”插入排序kM, M-1, …1 特点 一次移动移动位置较大跳跃式地接近排序后的最终位置最后一次只需要少量移动增量序列必须时递减的最后一个必须是1 注关于 DkD_{k}Dk 如何选择还没有明确定义 #include iostream
#include vector
using namespace std;/*
* brief: 希尔排序
* param v: 待排序序列引用
*/
void ShellSort(vectorint v)
{int temp; // 辅助空间int increment v.size() / 2; // 初始增量while (increment 1) // 最后一步的插入排序增量一定是1{for (int i increment; i v.size(); i){temp v[i];int j;for (j i - increment; j 0; j - increment){if (v[j] temp){v[j increment] v[j]; // 记录后移increment位}else // 说明v[0...j]的值都比temp小无需再比{break;}}v[j increment] temp; // jincrement就是temp要插入的位置}increment / 2; // 更新缩小增量}
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序ShellSort(v);cout 排序后 endl;printVec(v);
}比较希尔排序和直接插入排序的代码发现二者的相似程度非常高原因在于希尔排序就是每次以一定的增量 incrementincrementincrement 间隔对序列中的元素进行排序让序列变得基本有序当 increment1increment1increment1 时最后一步就是直接插入排序由于此刻序列已基本有序最后一步的排序中需要交换位置的元素已经不多了速记方法将直接插入排序代码中的 111 用incrementincrementincrement替换并在最外层加上以 incrementincrementincrement 为条件的循环。 二、交换排序 基本思想 两两比较如果发生逆序则交换直到所有记录都排好序为止。 1. 冒泡排序 基本思想 每趟不断将记录两两比较并按“前小后大”规则交换 性能分析 算法的时间复杂度为O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1) 稳定性 稳定。 #include iostream
#include vector
using namespace std;/*
* brief: 冒泡排序
* param v: 待排序序列引用
*/
void bubbleSort(vectorint v)
{int temp; // 辅助空间int n v.size();for (int i 1; i n; i) // 每次找出一个最大的n个元素要比较n趟{for (int j 0; j n - i; j){if (v[j] v[j 1]) // 比较相邻两个元素大小{// 交换元素temp v[j];v[j] v[j 1];v[j 1] temp;}} }
}/**
* brief: 冒泡排序优化
* param v: 待排序序列引用
*/
void bubbleSortOpt(vectorint v)
{int temp;int n v.size();bool flag true; // 记录某一趟中是否交换了元素位置for (int i 1; i n flag; i){flag false; // 先将当前趟元素交换标记设为falsefor (int j 0; j n - i; j){if (v[j] v[j 1]) // 比较相邻两个元素大小{// 交换元素temp v[j 1];v[j 1] v[j];v[j] temp;flag true; // 发生了元素交换}}}
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序// bubbleSort(v);bubbleSortOpt(v);cout 排序后 endl;printVec(v);
}2. 快速排序 基本思想 任取一个元素如第一个为中心pivot枢轴、中心点所有比它小的元素一律前放比它大的元素一律后放形成左右两个子表对各子表重新选择中心元素并依此规则调整递归思想直到每个子表的元素只剩一个。 通过一趟排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录进行排序以达到整个序列有序。 具体实现 选定一个中间数作为参考所有元素与之比较小的调到其左边大的调到其右边。 每一趟子表的形成是采用从两头向中间交替式逼近法 由于每趟中对各子表的操作都相似可采用递归算法。 枢轴中间数 可以是第一个数、最后一个数、最中间一个数、任选一个数等。 性能分析 算法的时间复杂度为O(nlogn)O(nlogn)O(nlogn)空间复杂度O(logn)O(logn)O(logn)递归需要使用栈 稳定性 不稳定。 #include iostream
#include vector
using namespace std;/*
* brief: 快速排序
* param v: 待排序序列引用
*/
void quickSort(vectorint v, int start, int end)
{if (start end)return;int low start, high end;int pivot v[low]; // 枢轴while (low high){while (low high v[high] pivot) // 将比枢轴小的放到左边high--;v[low] v[high];while (low high v[low] pivot) // 将比枢轴大的放到右边low;v[high] v[low]; // 将枢轴放置中间某个位置}v[low] pivot;// 递归左右子表quickSort(v, start, low - 1);quickSort(v, low 1, end);
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序quickSort(v, 0, v.size() - 1);cout 排序后 endl;printVec(v);
}三、选择排序
1. 简单选择排序 基本思想 在待排序的数据中选出最大小的元素放在其最终的位置。 基本操作 首先通过 n−1n-1n−1 次关键字比较从 nnn 个记录中找出关键字最小的记录将它与第一个记录交换再通过 n−2n-2n−2 次比较从剩余的 n−1n-1n−1 个记录中找出关键字次小的记录将它与第二个记录交换重复上述操作共进行 n−1n-1n−1 趟排序后排序结束。 性能分析 算法的时间复杂度为O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1) 稳定性 不稳定。 #include iostream
#include vector
using namespace std;/*
* brief: 选择排序
* param v: 待排序序列引用
*/
void selectSort(vectorint v)
{int temp; // 辅助空间int n v.size();for (int i 0; i n; i){int minIdx i;for (int j minIdx 1; j n; j) // 找出[i...n-1]中最小元素对应index{if (v[j] v[minIdx]){minIdx j; // 更新minIdx}}if (minIdx ! i){// 交换v[i]和v[minIdx]temp v[i];v[i] v[minIdx];v[minIdx] temp;}}
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序selectSort(v);cout 排序后 endl;printVec(v);
}2. 堆排序 堆的定义 若 nnn 个元素的序列 {a1a_{1}a1, a2a_{2}a2, …, ana_{n}an} 满足 {ai⩽a2iai⩽a2i1\begin{cases} a_{i} \leqslant a_{2i} \\ a_{i} \leqslant a_{2i1} \end{cases}{ai⩽a2iai⩽a2i1 或 {ai⩾a2iai⩾a2i1\begin{cases} a_{i} \geqslant a_{2i} \\ a_{i} \geqslant a_{2i1} \end{cases}{ai⩾a2iai⩾a2i1 则分别称该序列 {a1a_{1}a1, a2a_{2}a2, …, ana_{n}an} 为小根堆和大根堆。 从堆的定义可以看出堆实质是满足如下性质的完全二叉树二叉树中任一非叶子节点均小于大于它的孩子节点。 堆排序定义 若在输出堆顶的最小值最大值后使得剩余 n−1n-1n−1 个元素的序列重新又建成一个堆则得到 nnn 个元素的次小值次大值… 如此反复便能得到一个有序序列这个过程称之为堆排序。 实现堆排序需解决两个问题 如何由一个无序序列建成一个堆如何在输出堆顶元素后调整剩余元素为一个新的堆 堆的调整——小根堆 输出堆顶元素后以堆中最后一个元素替代之然后将根节点值与左、右子树的根节点值进行比较并与其中小者进行交换重复上述操作直至叶子节点将得到新的堆称这个从堆顶至叶子的调整过程为“筛选”。 堆的建立 单节点的二叉树是堆在完全二叉树中所有以叶子节点序号i⩾n/2i \geqslant n/2i⩾n/2为根的子树是堆这样只需依次将以序号为 n/2,n/2−1,...,1n/2, n/2-1, ..., 1n/2,n/2−1,...,1 的节点为根的子树均调整为堆即可即对应由 nnn 个元素组成的无序序列“筛选”只需从第 n/2n/2n/2 个元素开始。 性能分析 初始堆化所需时间不超过O(n)O(n)O(n)排序阶段不含初始堆化 一次重新堆化所需时间不超过O(logn)O(logn)O(logn); n−1n-1n−1 次循环所需时间不超过O(nlogn)O(nlogn)O(nlogn) Tw(n)O(n)O(nlogn)O(nlogn)Tw(n) O(n) O(nlogn) O(nlogn)Tw(n)O(n)O(nlogn)O(nlogn) 稳定性 不稳定。 #include iostream
#include vector
using namespace std;/*
* brief: 将v[start~end]的记录调整为一个大顶堆
* 已知v[start~end]中的记录除v[start]外均满足堆的定义
* param v: 待调整序列引用
*/
void heapAdjust(vectorint v, int start, int end)
{int temp v[start];for (size_t j 2 * start; j end; j * 2) // 沿关键字较大的孩子节点向下筛选{if (j end v[j] v[j 1]) // j:左孩子 j1:右孩子{j; // 右孩子较大将j增1}if (temp v[j]){break; // temp的值比左右孩子值都大不需要调整}v[start] v[j]; // 将较大的孩子节点上调至父节点start j;// j * 2继续对较大孩子节点进行调整}v[start] temp;
}/*
* brief: 堆排序
* param v: 待排序序列引用
*/
void heapSort(vectorint v)
{int length v.size() - 1; // 完全二叉树、堆顶元素从1开始编号所以我们对v// 这里减1是为了不考虑v[0]只对v[1~length]排序// 初始堆化for (size_t i length / 2; i 0; i--){heapAdjust(v, i, length);}for (size_t i length; i 1; i--){// 将堆顶元素与最后一个元素交换int temp v[1];v[1] v[i];v[i] temp;// 将v[1~i-1]再调整称大顶堆heapAdjust(v, 1, i - 1);}
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 1; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 0,81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序heapSort(v);cout 排序后 endl;printVec(v);
}四、归并排序 基本思想 将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中通常采用的是2-路归并排序即将两个位置相邻的有序子序列R[l...m]R[l...m]R[l...m]和R[m1...n]R[m1...n]R[m1...n]归并为一个有序序列R[l...m]R[l...m]R[l...m]。 性能分析 时间效率O(nlogn)O(nlogn)O(nlogn);空间效率O(n)O(n)O(n) 稳定性 稳定。 #include iostream
#include vector
using namespace std;/**
* brief: 将有序序列vSrc[s...m]和vSrc[m1...t]合并到vDst[s...t]
* param vSrc: 源数组引用
* param vDst: 目标数组引用
* param s: start index
* param m: middle index, s m t
* param t: end index
*/
void merge(vectorint vSrc, vectorint vDst, int s, int m, int t)
{int i s, j m 1;int k s;while (i m j t){if (vSrc[i] vSrc[j]){vDst[k] vSrc[i];}else{vDst[k] vSrc[j];}}while (i m){vDst[k] vSrc[i];}while (j t){vDst[k] vSrc[j];}
}/*
* brief: 归并排序将vSrc[s...t]归并排序为vDst[s...t]
* param vSrc: 待排序序列引用
* param vDst: 排序结果序列引用
* param s: start index
* param t: end index
*/
void mergeSort(vectorint vSrc, vectorint vDst, int s, int t)
{if (s t){vDst[s] vSrc[s];return;}else{int m (s t) / 2;vectorint vTemp(vSrc.size());mergeSort(vSrc, vTemp, s, m);mergeSort(vSrc, vTemp, m 1, t);merge(vTemp, vDst, s, m, t);}
}/*
* brief: 打印元素
* param v: 待排序序列引用
*/
void printVec(vectorint v)
{for (size_t i 0; i v.size(); i){cout v[i] \t;}cout endl;
}int main(int argc, char* argv[])
{vectorint v { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout 排序前 endl;printVec(v);// 排序int length v.size();vectorint vRes(length);cout aa endl;mergeSort(v, vRes, 0, length - 1);cout 排序后 endl;printVec(vRes);
}五、各种排序方法比较
排序方法平均情况最好情况最坏情况辅助空间稳定性直接插入排序O(n2)O(n^2)O(n2)O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(1)O(1)O(1)稳定希尔排序O(nlogn)O(nlogn)O(nlogn)~O(n2)O(n^2)O(n2)O(n1.3)O(n^{1.3})O(n1.3)O(n2)O(n^2)O(n2)O(1)O(1)O(1)不稳定冒泡排序O(n2)O(n^2)O(n2)O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(1)O(1)O(1)稳定快速排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n2)O(n^2)O(n2)O(logn)O(logn)O(logn)~O(n)O(n)O(n)不稳定简单选择排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(1)O(1)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n)O(n)O(n)稳定
参考链接
青岛大学数据结构-王卓
