实际应用中最常用的排序是快速排序和堆排序。所谓堆排序，就是将最小的一个值放到堆栈的顶部，这样就可以使最后出来的数完成排序。快速排序是不稳定的，堆排序是稳定的。所谓稳定，就是当两个值相等时，排序后两个值的顺序和排序前相同。以上两种排序使用的范围和情况是不同的，一般对于自然生成序列排序使用快速排序效率比较高，而对于已经有一定顺序的序列，使用堆排序比较合适，而且稳定的。

这里主要总结常用的5种排序，分别是快速排序，冒泡排序（也叫交换排序），选择排序，shell排序，插入排序。

下边分别介绍：

1快速排序，就是从一个序列中随意取一个数，然后对剩下的数进行分类，小的放到左边，大的放到右边。如此进行下去知道最后。N(n-1)/2.空间复杂度是o（n）.

2冒泡排序，就是从第一个数开始和后一个数比较，然后依情况交换，然后再用第二个和第三个比较交换，如此反复，直到最后一个。一直进行n轮就可以完成排序。

3选择排序，就是将一个序列中的最小的放到第一个，然后再将剩下的数据用相同的方式分别放到后一位。它的空间复杂度是O(1).

4shell排序，就是将有一定间隔的数进行排序，并且间隔变小，也就是开始是n/2,然后继续变小，一般都是以一半为标准，直到最后间隔只有1，也就完成了排序。需要的空间复杂度是O(1).

5插入排序，就比如平时玩的扑克排，一般整理排的时候需要将排排序，当你拿到一张新排的时候，就要比较左边和右边，只有在左右中间的那个值的时候才说明排序成功。它需要的空间复杂度也是O(1).

Ps:空间复杂度就是需要另外占用的空间。

以上排序中，只有快速排序是O（n），其他都是O（1），因为只有快速排序需要另外再起存储空间，而其他都是在原来空间中增加一个空间就可以。