汇总：
数据结构笔记|C++
1.三个时间复杂度为O(n
2)的排序算法
1.1插入排序
1.1.1直接插入排序
//插入排序
void insertSort(int* d){//递增
int N=sizeof(d)/sizeof(int);
for(int i=0;i
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| O(n2) | O(n2) | 初始逆序 | O(n) | 初始正序 | n2 | n2 | n | O(1) | 稳定 | 全局有序 |
1.2冒泡排序
使最小的元素一直上浮
//冒泡排序
void bubbleSort(int* d){
int N=sizeof(d)/sizeof(int);
for(int i=0;ii;j++){
if(d[j-1]>d[j])
swap(d[j-1],d[j]);
}
}
}
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| O(n2) | O(n2) | 初始反序 | O(n) | 初始正序 | n2 | n2 | n | O(1) | 稳定 | 全局有序 |
1.3选择排序
每步从待排序的元素中选出关键字最小的元素，放到已排序的序列的最后
//选择排序
void selectSort(int* d){
int N=sizeof(d)/sizeof(int);
for(int i=0;i
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| O(n2) | O(n2) | 无 | O(n2) | 无 | n2 | n | n | O(1) | 不稳定 | 全局有序 |
- 简单选择排序的效率与初始数据的顺序性无关(就算正序逆序，都需要每次比较剩余全部未比较元素)，每进行一趟排序归位一个元素
- 由于每次都在选，所以不稳定，eg.
排序前：
2,4,4*，3
排序后：
2,3,4*，4
2.Shell排序
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| – | – | – | – | – | – | – | – | – | – | – |
3.归并排序
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| – | – | – | – | – | – | – | – | – | – | – |
4.快速排序
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| – | – | – | – | – | – | – | – | – | – | – |
5.堆排序
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| – | – | – | – | – | – | – | – | – | – | – |
6.分配排序和基数排序
分配排序
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| – | – | – | – | – | – | – | – | – | – | – |
基数排序
| 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| – | – | – | – | – | – | – | – | – | – | – |
7.对各种排序算法的实验比较
总结
| 算法名称 | 平均 | 最坏 | 最坏条件 | 最好 | 最好条件 | 比较次数 | 移动次数 | 排序趟数 | 空间复杂度 | 稳定性 | 有序区 |
|---|
| 插入 | – | – | – | – | – | – | – | – | – | – | – |
| 冒泡 | – | – | – | – | – | – | – | – | – | – | – |
| 选择 | – | – | – | – | – | – | – | – | – | – | – |
| Shell | – | – | – | – | – | – | – | – | – | – | – |
| 归并 | – | – | – | – | – | – | – | – | – | – | – |
| 快排 | – | – | – | – | – | – | – | – | – | – | – |
| 堆 | – | – | – | – | – | – | – | – | – | – | – |
| 分配 | – | – | – | – | – | – | – | – | – | – | – |
| 基数 | – | – | – | – | – | – | – | – | – | – | – |
8.排序问题的下限
