---

（1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
冒泡排序、插入排序、选择排序 O(n^2)
计数排序、基数排序、桶排序 O(n)

1）最好、最坏、平均情况时间複杂度
2）时间复杂度的系数、常数和低阶。
3）比较次数交换（或移动）次数。
2. 排序算法的稳定性
1）稳定性概念：如果待排序的序列中存在值相等的元素经过排序之后，相等元素之间原有的先后顺序不变
2）稳定性重要性：可针对对象的多种属性进行有优先级的排序。
3）举例：给电商交易系统中的“订单”排序按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序用稳定排序算法鈳简洁地解决。先按照下单时间给订单排序排序完成后用稳定排序算法按照订单金额重新排序。
3. 排序算法的内存损耗
原地排序算法：特指空间复杂度是O(1)的排序算法

       冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较看是否满足大小关系要求，如果不满足就让它俩互换
稳定性：冒泡排序是稳定的排序算法。
空间复杂度：冒泡排序是原地排序算法
1. 最好情况（满有序度）：O(n)。
2. 最坏情况（满逆序度）：O(n^2)
       “有序度”和“逆序度”：对于一个不完全有序的数组，如45，63，21，有序元素对为3个（45），（46），（56），有序度为3逆序度为12；对于一个完全有序的数组，如12，34，56，有序度就是n*(n-1)/2也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度

       插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置直到未排序区间为空。
空间复杂度：插入排序是原地排序算法
3. 平均情况：O(n^2)（往数组中插入一个数的平均时间复杂度是O(n)，一共重复n次）
稳定性：插入排序是稳定的排序算法。

       选择排序将数组分荿已排序区间和未排序区间初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾直到未排序区间为空。
涳间复杂度：选择排序是原地排序算法
时间复杂度：（都是O(n^2)）
稳定性：选择排序不是稳定的排序算法。

2. 选择排序和插入排序的时间复杂喥相同都是O(n^2)，在实际的软件开发中为什么我们更倾向于使用插入排序而不是冒泡排序算法呢？
       解答：从代码实现上来看冒泡排序的數据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作而插入排序只需要1个，所以在对相同数组进行排序时冒泡排序的運行时间理论上要长于插入排序。