排序时间的复杂度和稳定性
目录
七大排序的实现
时间复杂度
冒泡排序
简单选择排序
直接插入排序
希尔排序
堆排序
归并排序
快速排序
稳定性
冒泡排序
简单选择排序
直接插入排序
希尔排序
堆排序
归并排序
快速排序
七大排序的实现
七大排序思想-CSDN博客运用动图让读者快速理解不同排序算法的底层逻辑，让读者可以直观的看到各种排序的步骤，帮助读者迅速理解，掌握排序算法https://blog.csdn.net/2401_87944878/article/details/145403473
关于七大排序各有优劣，此处我们对这七大排序的时间复杂度和空间复杂度，稳定性进行初步的讨论。
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
时间复杂度
冒泡排序
冒泡排序是对数组相邻元素进行比较，将大的向后进行交换，最坏的情况就是原数组是逆序的，需要对每一个相邻元素进行交换，次数就是1+2+3+4+5+....+n，所以时间复杂度就是N^2；最好的情况就是原数组就是正序的，当遍历一边原数组没有交换就可以结束排序，此时时间复杂度是N；
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 0;
for (int m = 0; m < n - 1 - i; m++)
{
if (a[m] > a[m + 1])
{
int tmp = a[m];
a[m] = a[m + 1];
a[m + 1] = tmp;
flag = 1;
}
}
if (flag == 0)
break;
}
}上面代码用flag来记录遍历一次原数组是否进行了交换。
简单选择排序
简单选择排序，每一次循环都是遍历未排序数组中的所有元素，所以其循环次数是1+2+3+...n，时间复杂度就是N^2；
直接插入排序
直接插入排序，将数组中的元素向前找到其目标位置。最坏情况就是数组逆序，每一次向前找都要找到头，次数是1+2+3+4+5+...n，时间复杂度就是N^2。最好的情况就是原数组恰好正序，每次向前找目标位置的时候，都只需要比较一次就行了，时间复杂度是N。
希尔排序
希尔排序分为两个部分：预排序和插入排序。数组越有序，插入排序越快。与简单插入排序不同的是其每一次预排序都会让数组越来越趋于有序，所以希尔排序的每一次循环都会影响下一次循环的排序。关于希尔排序的时间复杂度需要涉及到更深的数学知识，不同的计算机教授的观点也是不同的，一般认为其时间复杂度是N^1.6。
堆排序
关于堆排序在二叉树中详细介绍，有需要可以自行去看。二叉树（C语言）-CSDN博客文章浏览阅读1.4k次，点赞19次，收藏18次。帮助读者快速掌握树这一数据结构，了解堆的功能，能够实现堆排序，以及如何再大量数据中快速找到前K个最大元素，如何处理普通二叉树，普通二叉树的遍历等知识。https://blog.csdn.net/2401_87944878/article/details/145262931
https://blog.csdn.net/2401_87944878/article/details/145262931
归并排序
归并排序是向2个进行归并，再4个，在8个，一直到n个，每一次*2，所以其深度是logn。不论是2个一起，4个一起，还是8个一起，每个数据都要被处理到，所以每层的时间复杂度是n，则总的时间复杂度是N*logN。
快速排序
快排在一般情况下是，一个数组找到key的位置后，递归成左右两个，依次向下递归*2，所以其深度是logN，每次找key的位置时，左右指针都要遍历原数组，所以一般其时间复杂度时N*logN；但是快速排序也有其最坏情况，当大量数据相同的时候，每一次key的位置还是最左边，这就会导致数组向下递归后还是只有一个，就变成了简单选择排序，时间复杂度变成了N^2。
稳定性
稳定性指的是原数组中的相同数据的相对位置是否稳定。
简单来说，就是原数组中a位置的5在b位置5的前面，经过排序后，a位置的5如果还在b位置5的前面，则排序稳定，否则排序不稳定。
冒泡排序
冒泡排序是一次次的交换，当两个数相等的时候不会交换，所以冒泡排序是稳定的。
简单选择排序
简单选择排序是不稳定的，其是先选前一个数放到后面，再将后一个数也放到后面，所以两数的位置非颠倒。
直接插入排序
直接插入排序与冒泡一样，在后一个数向前找到与其相同的数时停止，放在它后面，顺序不变，所以直接插入排序稳定。
希尔排序
希尔排序是将数组分成多组，相同的数被分到不同的组后，可能导致其前后顺序发生变化，所以希尔排序是不稳定的。
堆排序
堆排序与希尔排序类似，堆排序也分成所有两个子树，当相同的数不在同一个子树上的时候就可能会导致逆序，所以堆排序是不稳定的。
归并排序
归并排序是两组数据分开比较，再填到一个新数组中去，所以相同数据在前面的会先进入新数组，所以归并排序是高效排序中唯一一个稳定的。
快速排序
快速排序找key的时候，对于数组中左右两边的交换可能会导致顺序颠倒，如下图所示。
可以看到经过左右两边的交换后，9的相对位置就发生了变化，所以快速排序是不稳定的。