07 |排序

一、什么是排序

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。

二、怎么分析一个排序算法

一.排序算法的执行效率

1、最好情况，最坏情况，平均情况时间复杂度分析

为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，所以最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，要知道排序算法在不同数据下的性能表现。

2、时间复杂度的系数、常数 、低阶

对于不同规模的数据，排序算法的性能不同。

3、比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

4、有序度和逆序度

有序度是数组中具有有序关系的元素对的个数。
逆序度的定义正好跟有序度相反（默认从小到大为有序）
逆序度 = 满有序度 - 有序度
比如一个数组[0,1,2,3,4,5,6,7,8,9]，从小到大排列，这个就是完全有序的数组，有序度是9+8+…+3+2+1=N*(N-1)/2=45

二.排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量

三.排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

三、常见排序算法

排序算法	是否原地排序	是否稳定	最好	最坏	平均	适用于
冒泡排序	是	是	O(N)	O(N^2)	O(N^2)	小数据量