一、前言
排序是日常中最常见的一种算法，常见的算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、快速排序、基数排序、桶排序。那么该怎样分析和学习排序算法呢？
二、算法的分析课
在上述的八种排序方法中，根据时间复杂度和是否基于比较可以为三种：
排序算法时间复杂度是否基于比较冒泡、插入、选择 O（n2） 是归并、快排
O（nlogn） 是桶、基数、计数 O（n） 否在学习算法的实现原理和实现方法时，还应掌握哪些技能呢？
1）、排序算法的执行效率：排序算法的执行执行效率主要从时间复杂度和时间复杂度的系数、常阶、低阶；比较次数和交换次数三个方面来体现。
时间复杂度：主要包括最好情况时间复杂度，最坏情况时间复杂度和平均情况时间复杂度三种情况来分析
时间复杂度的系数、常阶、低阶：时间复杂度时表示数据规模为n很大的时候的一个增长趋势，所以系数、常阶、低阶都会忽略，不过在开发过程中，一般数据规模是已知的，这时候系数、常阶、低阶的影响是应该考虑进来的。
比较次数和交换次数：在排序过程中，一般会涉及比较和交换两种操作，而了解算法的比较次数和交换次数也是学习排序算法的一个重要指标。
2）排序算法的内存消耗：在了解完排序算法的执行效率后，性能消耗也是算法的一个重要的考量指标。而内存消耗的一个重要体现就是空间复杂度。原地排序就是特指空间复杂度的为O（1）的排序算法。
3）排序算法的稳定性：稳定性是指在待排序的元素中存在相同的元素，经过排序后，相等元素之间原有的先后顺序不变。
三、冒泡排序：
实现原理：冒泡排序只会操作相邻的两个元素，每次冒泡只会比较两个相邻元素的大小。根据大小关系要求，如果不满足大小要求，就让两个元素互换，也就是一次冒泡。一次冒泡至少会让一个元素移动，一直重复n次，直到完成排序。
代码实现：
//正序排序:让数组的每一个元素与相邻的对比,如果满足条件，则两个数据交换,依次直到排序完成。每次冒泡都会把最大的值放到最后，完成冒泡的值不需要在进行排序。 int[] a = { 15, 12, 14, 1, 3 }; for (int j = 0; j < a.length; j++) { boolean flag = false; for (int i = 0; i < a.length - 1 - j; i++) { if (a[i] > a[i + 1]) { int temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; flag = true; } } if (!flag) { break; } } for (int k = 0; k < a.length; k++) { System.out.println(a[k]); } } //倒序排序：与正序排序相同,只是遍历的过程和比较条件相反。 int[] a = { 15, 12, 14, 1, 3 }; for (int j = a.length; j >= 0; j--) { boolean flag = false; for (int i = 0; i < a.length-1; i++) { if (a[i] < a[i + 1]) { int temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; flag = true; } } if (!flag) { break; } } for (int k = 0; k < a.length; k++) { System.out.println(a[k]); }我们可以从三个方面来分析冒泡算法：
1、 排序算法的执行效率：最好情况只进行一次冒泡时间复杂度为O（n）,最坏情况是元素与要排序的方向完全相反，时间复杂度为O（n2）。平均时间复杂度可以用有序度和无序度来分析。有序度指定的要比较的两个元素与要排序的顺序相同，如数组a中（1，3）就是一个有序度，默认从小到大为有序。当一个完全排序的数组，它的有序度为n*(n-1)/2，称之为满有序度。而与有序相反的也就是逆序度， 逆序度=满有序度-有序度。排序的过程就是增加有序度，减少逆序度的过程，达到满有序度，排序也就完成了。满有序度-初始有序度就等于逆序度也就是数据交换的次数，例子中等于10-2=8。平均时间复杂度取个中间值也就是n*(n-1)/4,也就是O(n2)。
2、算法的性能消耗：从代码中，我们可以看出冒泡排序只涉及相邻数据的交换操作，所以空间复杂度为O（1），也就是说冒泡排序是一个原地排序算法。
3、稳定性：冒泡排只有在两个元素满足比较条件是才会进行交换，两个相同的元素不会进行交换，所以冒泡排序是一个稳定的排序算法。
四、插入排序：
实现原理：在有序数组中插入一个元素，如何保证元素的顺序？其实很简单，只要遍历整个数组，找到数据应该插入的位置将元素插入即可。插入排序算法正式借助上面的思路。首先，将数组分为两个区域，已排序区域和未排序区域。初始的已排序区域只有一个元素，也就是数组的第一个元素。而插入算法的核心思想就是取未排序的区域的元素，在已排序的区域中找到合适的位置将元素插入，并且保证已排序区域一直有序。重复这个过程，直到排序结束。
代码实现：
//正序排序 int [] a={21,14,2,5,16}; for (int i = 0; i < a.length; i++) { //已排序区域 int temp = a[i]; //未排序区域取值 int j=i-1; for(;j>=0;j--){ if(a[j]> temp){ a[j+1]=a[j];//移动 }else{ break; } } a[j+1]=temp; } for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } //逆袭排序 int [] a={21,14,2,5,16}; for (int i = 0; i < a.length; i++) { //已排序区域 int temp = a[i]; //未排序区域取值 int j=i-1; for(;j>=0;j--){ if(a[j]< temp){ a[j+1]=a[j];//移动 }else{ break; } } a[j+1]=temp; } for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } }算法分析（正向排序）：
插入排序也涉及两个动作：比较和移动。其实实质也是相邻两个元素间的移动，并不会产生额外的存储空间，所以插入排序的空间复杂度是O（1），是一个原地排序算法。
插入排序中，如果有相同的元素，我们可以选择后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，从而插入排序是稳定的排序算法。
插入排序的时间复杂度，及时是一个已经排序的数组，它执行的时间复杂度也是O（n）,如果是一个逆序排序的数组，那么正序排序的时间复杂度就是O（n2）。而平均时间复杂度也是O（n2），因为每次插入的操作都相当于在数组中插入一个元素，执行n次结束。还可以根据有序度来得到数组元素移动的次数是：8次。
五、选择排序：
实现原理：选择排序的实现原理与插入排序类型，也是分为已排序区域和未排序区域。不过选择排序是每次从未排序中选择最小的元素找到最小的元素，将其放到已排序区域的末尾，直到排序完成。
代码实现：
int [] a={12,3,23,25,14}; for (int i = 0; i < a.length; i++) { int min=i;//最小值的下标 for (int j = i+1; j < a.length; j++) { //如果已排序区的最小值比未排序的区域的值小，则将该值赋值为最小值 if(a[min]>a[j]){ min=j; } } //获取最小值 int temp=a[min]; //将已排区域的值放置到最小值的位置 a[min]=a[i]; //将最小值放到已经排序区域末尾 a[i]=temp; } for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } }性能消耗：选择排序的空间复杂度为O（1），是一种原地排序算法。
稳定性：选择排序不是一种稳定的排序算法，每次排序时都会选择剩余元素中最小的值，并和前面的元素交换位置，相同数值的元素位置也会变化，这样就是破坏了稳定性。比如6,3,2,6,5,在找到最小值时，2会和第1个6交换位置，那么6和6之位置也发生了变化。
时间复杂度：从代码中可以看出，无论是最好还是最坏情况，选择的排序的时间复杂度都为O（n2）。
以上就是三种比较常见的排序算法，下面用图表来做下总结：
排序算法时间复杂度（最好，最坏，平均）空间复杂度原地算法稳定性冒泡排序O(n),O(n2),O(n2)O(1)是是插入排序O(n),O(n2),O(n2)O(1)是是选择排序O(n2),O(n2),O(n2)O(1)是否
