数据结构（C语言）里的辅助空间究竟怎样理解？

严格地说就是除了源数据外其他所有变量.但一般来说,循环变量好像不算在内.

比如将包含n个数据的数组右循环移一个数,除了循环变量外,肯定要用1个变量来保存数组中最后一个数,最后把这个数放到第一位去.这个变量就是辅助的.

现在的计算机内存都很大,一般都考虑用空间来换时间,空间只要不浪费即可,不用追求最优.

1、 所有的简单排序方法（包括：直接插入、起泡和简单选择）和堆排序的空间复杂度为O(1)；

2、 快速排序为O(logn )，为栈所需的辅助空间；

3、 归并排序所需辅助空间最多，其空间复杂度为O(n )；

4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。

都不知道怎么回答，各种排序说的也太多了，这里讲几种简单的吧，希望对你有帮助！

比如n个顺序存储元素进行排序，a[0]做“哨兵”（即a[0]不存数据，而是用作辅存空间使用）的情况

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个辅助存储空间，是稳定的排序；

---