1 交换排序
基本思想就是：两两进行比较，如果发生逆序则进行交换，直到所有的记录都排好为止。
常见的交换排序方法：
- 冒泡排序 O ( n 2 ) O(n^2) O(n2)
- 快速排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
1.1 冒泡排序
冒泡排序就是基于简单的交换思想。每趟不断将记录两两比较，并按前小后大规则交换。
一些结论：
- n n n个记录，总共需要 n − 1 n-1 n−1趟
- 第 m m m趟需要比较 n − m n-m n−m次
1.1.1 冒泡排序算法
void bubble_sort(SqList &L)//冒泡排序算法
{
int m,i,j;
RedType x;//交换时临时存储
for(m=1; m<=n-1; ++m)//总共需要m趟
{
for(j=1; j<=n-m; ++j)//交换需要n-m次
{
if (L.r[j].key > L.r[j+1].key)
//两个相邻元素进行比较
//发生逆序
{
x = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = x;//交换
}
}
}
}
已经排好序后，就无需做无用的交换了。
算法的改进：
void bubble_sort(SqList &L)//冒泡排序算法
{
int m,i,j;flag = 1;//flag作为是否交换的标记
RedType x;//交换时临时存储
for(m=1; m<=n-1 && flag==1; ++m)//总共需要m趟
{
flag = 0;
for(j=1; j<=n-m; ++j)//交换需要n-m次
{
if (L.r[j].key > L.r[j+1].key)
//两个相邻元素进行比较
//发生逆序
{
flag = 1;//发生交换，flag置为1
x = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = x;//交换
}
}
}
}
1.1.2 性能分析
1.2 快速排序
基本思想：任意取一个元素，如第一个元素，为中心。
采用递归的思想，结束条件是子表只剩一个元素。
-
基本思想： 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。
-
具体实现： 选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。
-
(枢轴)中间数： 可以是第一个数、最后一个数、最中间一个数、任选一个数等。
1.2.1 快排的算法
1.2.2 性能分析
1.2.3 快排的特点
- 每一趟的子表的形成是采用从两头向中间交替式逼近法
- 由于每趟中对各子表的操作都相似，可采用递归算法
- 快排是个不稳定的算法
2 简单选择排序
示意图：
2.1 简单排序算法
2.1.1 性能分析
2.2 堆排序
堆的实质是完全二叉树。
小根堆就是每一个根节点都比左右孩子来的小；大根堆就是每一个根节点都比左右孩子来的大。即一个根是最大值，一个根是最小值，就可以用来排序。
2.2.1 堆的调整
大根堆就找大的数值。
可以看出：
对一个无序序列反复“筛选”就可以得到一个堆；
即：从一个无序序列建堆的过程就是一个反复“筛选”的过程。
显然：
单结点的二叉树是堆；在完全二叉树中所有以叶子结点（序号
ⅰ
>
/
2
ⅰ>/2
ⅰ>/2）为根的子树是堆。
由于堆实质上是一个线形表，那么我们可以顺序存储一个堆。
2.2.2 筛选过程算法
2.2.3 堆的建立算法
2.2.4 性能分析
3 归并排序
基本思想：将两个或两个以上的有序子序列归并为一个有序序列。
两个两个来。（或两个以上）
总共需要
l
o
g
2
n
log_2n
log2n趟。
线性表，双指针，即可比较合并。
现在两个子序列是相邻的。也是两个指针。
3.1 性能分析
4 基数排序
不需要比较，思想就是分配和收集。也叫桶排序或箱序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。
基数排序： 数字是有范围的，均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百.…进行排序。
以上就个位就有序了。之后按十位分：
十位有序，按照百位分：
发现排序完成。
4.1 性能分析
文章来源：https://www.toymoban.com/news/detail-612381.html
5 各种排序算法的比较
文章来源地址https://www.toymoban.com/news/detail-612381.html
到了这里，关于归并交换基数简单选择排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
