空间复杂度为on的排序算法（快速排序空间复杂度计算）

空间复杂度为O(n)的排序算法是指在排序过程中，所需的额外空间大小与待排序元素个数之间的关系是线性的。也就是说，随着待排序元素个数的增加，所需的额外空间也会以线性的方式增加。

有许多排序算法可以满足空间复杂度为O(n)的要求，其中最常见的是计数排序和桶排序。

计数排序是一种非比较排序算法，其基本思想是通过统计待排序元素中每个元素出现的次数，然后根据统计结果将元素排列到正确的位置上。计数排序适用于待排序元素都是非负整数且取值范围不大的情况。在计数排序中，我们首先需要确定待排序元素的最大值max，然后创建一个大小为max+1的辅助数组count，用于统计每个元素的出现次数。接下来，通过累计count中元素的值，我们可以确定待排序元素在结果数组中的位置。最后，根据结果数组将待排序元素排序完成。计数排序的空间复杂度为O(n)，其中n为待排序元素的个数。

桶排序是一种将待排序元素划分成有限数量的块（桶）并分别对每个桶进行排序的算法。桶排序适用于待排序元素满足一定条件的情况。在桶排序中，我们首先需要确定待排序元素的范围，并将这个范围划分为一定数量的桶。然后，我们将待排序元素分别放入对应的桶中。接着，对每个桶中的元素进行排序，可以使用其他排序算法如插入排序或快速排序。最后，按照从小到大顺序将每个桶中的元素依次取出，即可得到排序结果。桶排序的空间复杂度为O(n)，其中n为待排序元素的个数。

虽然计数排序和桶排序都满足空间复杂度为O(n)的要求，但是它们对待排序元素的取值范围有一定的限制。计数排序要求待排序元素都是非负整数且取值范围不大，而桶排序要求待排序元素满足一定条件。因此，在实际使用时，我们需要根据具体情况选择合适的排序算法。

总结起来，空间复杂度为O(n)的排序算法有计数排序和桶排序。它们通过使用额外的辅助数组或桶来统计待排序元素的出现次数或者划分待排序元素，并在合适的位置上放置或排序这些元素。虽然这些算法对待排序元素的限制有一定要求，但是它们在合适的情况下可以以O(n)的空间复杂度实现对待排序元素的高效排序。