各种排序算法（各种排序算法所需辅助空间是多少）
本文目录
各种排序算法所需辅助空间是多少
1、 所有的简单排序方法（包括：直接插入、起泡和简单选择）和堆排序的空间复杂度为O(1)；
2、 快速排序为O(logn )，为栈所需的辅助空间；
3、 归并排序所需辅助空间最多，其空间复杂度为O(n )；
4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
都不知道怎么回答，各种排序说的也太多了，这里讲几种简单的吧，希望对你有帮助！
比如n个顺序存储元素进行排序，a不存数据，而是用作辅存空间使用）的情况
1 、直接插入排序：比较次数 最少n-1次；最多(n-1)(n+2)/2
移动次数 最少0； 最多(n-1)(n+4)/2
使用一个辅助存储空间，是稳定的排序；
2 、折半插入排序：比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），
移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
使用一个辅助存储空间，是稳定的排序；
3 、冒泡排序： 比较最少为：n-1次，最多时间复杂度表示为o(n2);
移动次数最少为0，最多时间复杂度表示为O(n2);
使用一个辅存空间，是稳定的排序；
4 、简单选择排序： 比较次数没有多少之分，均是n(n-1)/2;
移动次数最少为0，最多为3(n-1);
使用一个辅存空间，是稳定的排序；
5 、快速排序：比较和移动次数最少时间复杂度表示为O(n*log2n);
比较和移动次数最多的时间复杂度表示为O(n2);
使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；
6、 堆排序： 比较和移动次数没有好坏之分，都是O(n*log2n);
使用一个辅存空间，是不稳定的排序；
7、2-路归并排序：比较和移动次数没有好坏之分，都是O(n*log2n);
需要n个辅助存储空间，是稳定的排序；
C语言大牛推荐七大排序算法学生来看
C语言7种排序算法附代码
1.冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换它们两个对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数:针对所有的元素重复以上的步骤，除了最后一个;重复步骤1~3，直到排序完成。
2.选择排序
在未排席序列中找到最小(大)元素，存放到排序序列的起始位置从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末,以此类推，直到所有元素均排序完毕
3.插入排序
从第一个元素开始，该元素可以认为已经被排序;
取出下一个元素，在已经排序的元素序列中从后向前扫描:如果该元素(已排序)大于新元素，将该元素移到下一位置;
4.快速排序
快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5.希尔排序
选择一个增量序列t1,t2,"”,tk，其中ti》tj,tk=1;按增量席列个数k，对序列进行k 趟排序;
6.桶排序
设置一个定量的数组当作空桶子
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
7.基数排序
取得数组中的最大数，并取得位数:
arr为原始数组，从最低位开始取每个位组成radix数组;对radix进行计数排序(利用计数排序适用于小范围数的特点)从不是空的桶子里把项目再放回原来的序列中
稳定的排序算法有哪些
1.稳定的排序
冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体
2.不稳定的排序
选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）
简述各种排序算法的优缺点
1、冒泡排序法：优点是数据稳定误差小。缺点是速度慢。
2、选择排序法：优点是移动数据的次数少。缺点是比较数据的次数多。
3、插入排序法：优点是数据稳定且速度快。缺点是比较次数浮动较大。
4、缩小增量排序法：优点是速度快且数据可以按一定顺序排列。缺点是数据不稳定。
