如何创建自己的网站链接,百度官网入口链接,企业自建网站平台有哪些,ftp上传php网站简介
排序#xff08;Sorting#xff09;#xff1a;将一个数据元素#xff08;或记录#xff09;的任意序列#xff0c;重新排列成一个按关键字有序的序列
排序算法分为内部排序和外部排序
内部排序#xff1a;在排序期间数据对象全部存放在内存的排序
外部排序Sorting将一个数据元素或记录的任意序列重新排列成一个按关键字有序的序列
排序算法分为内部排序和外部排序
内部排序在排序期间数据对象全部存放在内存的排序
外部排序在排序期间全部对象个数太多不能同时存放在内存必须根据排序过程的要求不断在内、外存之间移动的排序
排序方法的稳定性
如果在记录序列中有两个记录r[i]和r[j], 它们的关键字key[i]key[j]且在排序之前, 记录r[i]排在r[j]前面。
如果在排序之后, 记录r[i]仍在记录r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的
排序常用的数据结构是数组、顺序表、结构体 排序算法的应用非常广泛商业领域、生活领域、科研领域都几乎离不开排序
淘宝商品价格排序海量数据排序
微博热搜排行榜点击量动态排序
QQ好友列表字符排序
数列相似度将数列元素排序后对比
元素唯一性排序后找出重复项
凸包问题例如图像识别手势采点绘制轮廓 排序介绍
排序包含两种基本操作
比较比较两个关键字的大小
移动将记录从一个位置移动至另一个位置
排序算法的时间复杂度用算法执行中的记录关键字比较次数与记录移动次数来衡量
根据排序思想来划分内部排序算法分为五类
插入排序直接插入排序、希尔排序
交换排序冒泡排序、快速排序
选择排序简单选择排序、堆排序
归并排序两路归并排序
基数排序k进制位数排序
判断排序好坏的方法
算法的时间复杂度、空间复杂度
算法的稳定性
排序算法的最好情况比较和移动次数最少
排序算法的最坏情况比较和移动次数最多
初始待排序序列是否会影响排序算法性能
排序次数是否固定
每一趟排序能否确定一个元素的最终排序位置 插入排序
插入排序的思想假设前k-1个记录已经排序第k个元素找到合适位置插入。分为
直接插入排序
希尔排序
直接插入排序
1. 直接插入排序是最简单的排序方法操作
每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的有序表的适当位置上, 直到对象全部插入为止
2. 直接插入排序的算法步骤
当插入第i(i≥1)个对象时, 前面的r[0], r[1], …, r[i-1]已经排好序。
用r[i]的关键字与r[i-1], r[i-2], …的关键字顺序进行比较(和顺序查找类似)如果小于则将r[x]向后移动(插入位置后的记录向后顺移)
找到插入位置即将r[i]插入
3. 直接插入排序的算法分析
直接插入排序的时间复杂度为O(n2)空间复杂度O(1)
直接插入排序是一种稳定的排序方法
直接插入排序最大的优点是简单在记录数较少时是比较好的办法
4.其他
算法性能与关键字的初始排列有关成正比关系。初始排列越有序比较和移动次数越少
最好情况排序前已经有序总比较次数n-1移动次数0
最坏情况排序前是逆序每趟排序都要比较i-1次和移动i-1次总比较次数n2/2总移动次数n2/2
每趟排序不能确定一个元素的最终排序位置例如最后一个元素是最小值插入到第一个元素位置导致前n-1个元素都要后移
//直插排序
/*
因为直接插入排序过程中前i-1个元素是有序的所以可以改进为折半插入排序
折半插入排序是指在查找记录插入位置时采用折半查找算法折半查找比顺序查找快所以折半插入排序在查找上性能比直接插入排序好
由于需要移动的记录数目与直接插入排序相同(为O(n2))所以折半插入排序的时间复杂度为O(n2)
*/
void insert(int *a)
{for(int i1;il;i){int tmpa[i];int ji;while(j0){if(a[j-1]tmp)break;a[j]a[j-1];j--;}a[j]tmp;}
} 希尔排序
1.希尔排序的思想先将待排序列分成若干子序列对其分别进行插入排序待整个序列基本有序时再对全体记录进行一次直接插入排序希尔排序Shell Sort又称为缩小增量排序
2. 希尔排序的算法设计
首先取一个整数 gap n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中
在每一个子序列中分别施行直接插入排序。
然后缩小间隔 gap, 例如取 gap gap/2
重复上述的子序列划分和排序工作直到最后取gap 1, 将所有记录放在同一个序列中排序为止。
3. 排序举例 4. 希尔排序的算法分析
开始时gap的值较大子序列中的记录较少排序速度较快
随着排序进展gap值逐渐变小子序列中记录个数逐渐变多由于前面大多数记录已基本有序, 所以排序速度仍然很快。
gap的取法有多种一般取法gapn/2gapgap/2直到gap 1
代码实现
//希尔排序
/*
希尔排序的算法分析
希尔排序所需的比较次数和移动次数约为n1.3
当n趋于无穷时可减少到n×(log2n)2
希尔排序的时间复杂度约为O(n(log2n)2)
希尔排序是一种不稳定的排序方法
*/
void Xier(int *a)
{int gap l / 2;while (gap 1) {for (int i 0; i l-gap; i) {for (int j i; j l; j gap) {if (a[i] a[j ])swap(a[i], a[j]);}}gap / 2;show(a);}
} 交换排序 交换排序的思想比较序列中前后两个位置的元素如果符合前小后大或前大后小则继续比较如果不符合则交换两个位置的元素再继续比较。 交换排序的算法有起泡排序 快速排序
起泡排序
1. 起泡排序又称冒泡排序算法思想
设待排序记录序列中的记录个数为n
一般地第i趟排序从1到n-i1
依次比较相邻两个记录的关键字如果发生逆序则交换之
其结果是这n-i1个记录中关键字最大的记录被交换到第n-i1的位置上最多作n-1趟。
2. 冒泡排序的算法过程
i1为第一趟排序关键字最大的记录将被交换到最后一个位置
i2为第二趟排序关键字次大的记录将被交换到最后第二个位置
依此类推……
关键字小的记录不断上浮(起泡)关键字大的记录不断下沉(每趟排序最大的一直沉到底)
3.冒泡排序举例 4. 冒泡排序的算法分析
起泡排序的时间复杂度为O(n2)空间复杂度O(1)
起泡排序是一种稳定的排序方法 5. 冒泡排序的其他分析
算法性能与关键字的初始排列有关成正比关系。初始排列越有序比较和移动次数越少
最好情况排序前已经有序只执行一趟总比较次数n-1移动次数0
最坏情况排序前是逆序每趟排序都要比较i-1次和移动i-1次总比较次数n2/2总移动次数n2/2
冒泡排序能够提前结束最好情况下只要一趟比较就结束。
每趟排序能够确定一个元素的最终排序位置因为每一趟排序会把最大或最小元素排到末尾不再参与排序
代码实现
//冒泡排序
void maopao(int *a)
{for (int i 0; i l; i) {for (int j 0; j l - i-1; j) {if (a[j] a[j 1]) {swap(a[j], a[j 1]);}}}
} 快速排序
1.快速排序算法设计
任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列
左侧子序列中所有记录的关键字都小于或等于基准记录的关键字
右侧子序列中所有记录的关键字都大于基准记录的关键字
基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)
然后分别对这两个子序列重复施行上述方法直到所有的记录都排在相应位置上为止。
基准记录也称为枢轴或支点记录。 2. 快速排序算法过程 取序列第一个记录为枢轴记录其关键字为Pivotkey 指针low指向序列第一个记录位置 指针high指向序列最后一个记录位置
一趟排序(某个子序列)过程
①.从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low1
②.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-1
③.重复1,2直到lowhigh将枢轴记录放在low(high)指向的位置
对枢轴记录前后两个子序列执行相同的操作直到每个子序列都只有一个记录为止 3. 快速排序的算法分析
快速排序是一个递归过程, 其递归树如图所示利用序列第一个记录作为基准将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧
可证明快速排序的平均计算时间是O(nlog2n)
实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个
但快速排序是一种不稳定的排序方法
代码实现
//快速排序
int getpiot(int *a, int l, int r) {int tmp a[l];while (l r) {while (l r a[r] tmp)r--;swap(a[r], a[l]);while (l r a[l] tmp)l;swap(a[l], a[r]);}return l;
}
void quick_sort(int *a,int l,int r)
{if(lr)return;int p getpiot(a,l,r);show(a);quick_sort(a,l,p-1);quick_sort(a,p1,r);
} 选择排序
选择排序的思想每一趟选出第i小(大)的元素与第i个位置的元素交换
选择排序算法包括
简单选择排序
堆排序
简单选择排序
1.简单选择排序的算法设计
每一趟(例如第i趟,i1,2,…,n-1)在后面 n-i1个待排序记录中通过n-i次比较选出关键字最小的记录,与第i个记录交换
2.简单选择排序的算法分析
时间复杂度O(n2)
是一种不稳定的排序方法 3.其他 简单选择排序的其他分析
简单选择排序性能与记录的初始排列无关。无论是否有序都要每趟全部扫描找出第i小(大)的元素第i趟选择的比较次数总是 n-i次
每趟排序能够确定一个元素的最终排序位置因为每一趟排序后第i小(大)的元素放在第i个位置 当不需要全部排序只需要排序出前k个元素用简单选择排序是一种好的算法。
代码实现
//简单选择排序
void choose(int *a)
{for(int i0;il-1;i) {int mini i;for (int j i 1; j l; j) {if (a[j] a[mini]) {mini j;}}if (mini ! i)swap(a[i], a[mini]);}
} 堆排序
1. 堆排序算法流程
将初始序列从1至n按顺序创建一个完全二叉树
将完全二叉树调整为堆
最后结点与根结点交换
排除掉最后结点重复步骤2直到剩下一个结点
2. 堆排序的算法分析
对长度为n的序列排序最多需要做n-1次调整建新堆(筛选)。建初始堆时需要n/2次筛选因此共需要O(n×k)量级的时间
klog2n堆排序时间复杂度为O(nlog2n)
堆排序是一个不稳定的排序方法
代码实现
void HeapAdjust(int* arr, int start, int end)
{int tmp arr[start];for (int i 2 * start 1; i end; i i * 2 1){if (i end arr[i] arr[i 1])//有右孩子并且左孩子小于右孩子{i;}//i一定是左右孩子的最大值if (arr[i] tmp){arr[start] arr[i];start i;}else{break;}}arr[start] tmp;
}
void HeapSort(int* arr)
{//第一次建立大根堆从后往前依次调整for(int i(l-1-1)/2;i0;i--){HeapAdjust(arr, i, l - 1);}show(arr);//每次将根和待排序的最后一次交换然后在调整int tmp;for (int i 0; i l- 1; i){tmp arr[0];arr[0] arr[l - 1-i];arr[l - 1 - i] tmp;HeapAdjust(arr, 0, l - 1-i- 1);show(arr);}
} 归并排序
1. 归并排序的思想将两个或两个以上的有序表合并成一个新的有序表。 两个有序顺序表合并为新的有序表时借助多一倍空间使得记录无需移动直接插入新空间中。 两路归并将初始序列分成前后两组通过比较归并到目标序列中
2. 2路归并排序算法设计
将n个记录看成是n个有序序列
将前后相邻的两个有序序列归并为一个有序序列(两路归并)
重复做两路归并操作直到只有一个有序序列为止
3. 2路归并排序算法举例 4. 2路归并排序算法分析
如果待排序的记录为n个则需要做log2n趟两路归并排序每趟两路归并排序的时间复杂度为O(n)
2路归并排序的时间复杂度为O(nlog2n)
归并排序的空间复杂度是O(n)
归并排序是一种稳定的排序方法 5. 其他
归并排序优点时间复杂度为O(nlog2n)且是稳定的排序方法
缺点需要额外空间归并排序的空间复杂度是O(n)
归并排序性能与记录的初始排列无关。无论是否有序每趟都要逐个两子序列相互合并一定要log2n趟
每趟排序不能够确定一个元素的最终排序位置因为如果最后一个子序列包含最小元素在最后一趟排序时要插入到最前位置导致所有元素都要移动
6. 代码实现
可选择递归或非递归实现
//归并排序
void merge(string *a,string *b,int start,int mid,int left)
{int istart,kstart,jmid1;while(i!mid1j!left1){if(a[i]a[j])b[k]a[i];elseb[k]a[j];}while(i!mid1)b[k]a[i];while(j!left1)b[k]a[j];for(istart;ileft;i)a[i]b[i];
}void merge_sort(string *a,string *b,int start,int end) //递归实现归并排序
{if(startend){int midstart(end-start)/2;merge_sort(a,b,start,mid);merge_sort(a,b,mid1, end);merge(a,b,start,mid,end);}
}void merge_sort(string *a,string *b) //非递归实现归并排序
{int right,left,mid;for(int i1;il;i2*i){for(left0;leftl-1;left2*i){midlefti-1;if(midl-1)break;rightleft2*i-1;if(rightl)rightl-1;merge(a,b,left,mid,right);}}
} 基数排序
1. 基数排序通过“分配”和“收集”若干次操作对单逻辑关键字进行排序的一种方法。
2. 链式基数排序的算法设计
基于最低位优先法思想
用链表作存储结构的基数排序
以十进制为例
①.设置10个队列f[i]和e[i]分别为第i个队列的头指针和尾指针
②.第i趟分配根据第i位关键字的值改变记录的指针将链表中记录按次序分配至10个链队列中采用队尾插入法每个队列中记录关键字的第i位关键字相同
③.第i趟收集改变所有非空队列的队尾记录的指针域令其指向下一个非空队列的队头记录重新将10个队列链成一个链表 3. 链式基数排序的算法分析
若每个关键字有 d 位,关键字的基数为radix
需要重复执行d 趟“分配”与“收集”
每趟对 n 个对象进行“分配”对radix个队列进行“收集”
时间复杂度为O(d(nradix))
一般情况下radix表示k进制是一个很小的值
所以时间复杂度为O(dn)其中n是记录总数d是关键字长度d位
是一种稳定的排序方法
4. 代码实现
// 基数排序的搜索函数
int radixSearch(vectorint arr, int target) {// 找到数组中的最大值int maxVal *max_element(arr.begin(), arr.end());// 对每个位数进行基数排序for (int exp 1; maxVal / exp 0; exp * 10) {vectorint count(10, 0); // 10个数字的计数数组// 统计每个数字的出现次数for (int i 0; i arr.size(); i) {count[(arr[i] / exp) % 10];}// 计算累计出现次数for (int i 1; i 10; i) {count[i] count[i - 1];}// 构建排序后的数组std::vectorint sortedArr(arr.size());for (int i arr.size() - 1; i 0; i--) {sortedArr[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}// 更新原始数组arr sortedArr;}// 在排序后的数组中进行二分查找int left 0;int right arr.size() - 1;while (left right) {int mid left (right - left) / 2;if (arr[mid] target) {return mid;} else if (arr[mid] target) {left mid 1;} else {right mid - 1;}}// 如果未找到目标值返回-1return -1;
} 内部排序算法比较 快速排序、堆排序、归并排序三者比较 简单排序包含除希尔排序外的其他时间复杂度O(n2)的多种排序简单排序都是稳定的在初始基本有序或n较小时优先选择直接插入排序它可以和快排、归并结合使用 基数排序适用于多关键字排序在n很大且d较小的情况使用链式基数排序较好 从稳定性来看归并排序简单排序基数排序都是稳定的根据实际需要选择 总结
1. 排序内部排序在内存中进行、外部排序需要使用外存
算法复杂度包括比较次数KCN和移动次数RMN稳定性的概念
2. 排序分类插入排序、交换排序、选择排序、归并排序、基数排序
3. 插入排序假定前i-1个对象有序第i个数据找出合适位置插入
直接插入排序时间复杂度为O(n2)是稳定排序
希尔排序时间复杂度为O(n x(log2 n)2)是不稳定的排序方法
4. 交换排序两个位置元素不符合排序规则就交换两个元素
起泡排序时间复杂度为O(n2)是一种稳定排序方法。起泡排序可以提前结束。
快速排序时间复杂度为O(nlog2n)是一种不稳定排序方法
5. 选择排序每一趟选出第i小(大)的元素与第i个位置的元素交换
简单选择排序时间复杂度为O(n2)是一种不稳定排序方法
堆排序时间复杂度为O(nlog2n)是一种不稳定排序方法
要掌握堆判断
6. 归并排序将两个或两个以上的有序表合并成一个新的有序表。
两路归并排序时间复杂度为O(nlog2n)是不稳定排序空间复杂度O(n)
7. 基数排序多关键字排序,最低位优先法LSD
链式基数排序时间复杂度为O(dn)是稳定排序
