Java常见排序基础 - 上
本篇文章主要介绍的是Java和Android开发中常见的排序概念，由于篇幅的问题我将其分成了几篇。主要有基础篇和实战篇。本篇主要学习的是基础排序的内容，主要学习以下四种基础排序：冒泡排序、选择排序、插入排序。
冒泡排序：
对于冒泡排序，我们不是很陌生，因为这种排序很基础且面试出现的频率比较大。 对于冒泡排序比较好的理解是： 对比数组内相邻的两个元素，如果 元素值 [i] 大于 [i+1] 那么，这两个元素就需要交换位置......直到数组最后一个索引对应的元素值最大。
根据上面的描述，我们可以思考，如果数组元素值 [i] 大于 [i+1] 才去交换位置，那么交换位置以后我们需要将其属性值给记录下来，常见的做法是 使用第三方来记录变化的值
首先，我们定义一个数组，然后根据上面的描述，不断去判断数组内两个相邻的属性值，然后通过临时变量去记录，于是，就有了下面的参考代码：
通过这样一遍操作以后，数组内的最大值就已经在最后的索引位置了，但这样达不到我们对数组进行整体排序的要求。因此还要对数组进行继续判断，由于上面的一次排序已经将最大值给找出来了，所以最后一个索引对应的值我们就不需要在对其进行排序了，因此第二次排序有以下的参考思路代码：
关于以上参考代码的思考：
如果我们的数组有4个属性值：
那么第一趟需要比较3次，分别是 [0] [1] 、 [1] [2] 、 [2] [3] 这一趟排序比较出来的最大值:[3]
第二趟需要比较2次 ，分别是 [0] [1] 、 [1] [2] 这一趟排序比较出来的较大值:[2]
第三趟需要比较1次，也就是 [0] [1] 这一趟排序比较出来的较大值:[1]
因此，通过以上试验步骤可以了解这种排序的比较趟数规律以及每一趟需要比较的次数，所以就可以通过循环去操作，下面是冒泡排序比较熟悉的写法
冒泡排序优化：
试想有下面这样一个数组：int arr[ ] = { 1,2,3,4,6,5 } ; 根据对这个数组的直观判断，我们只需遍历判断一趟就可以将数组进行整体排序，但是上面的写法对于这种情况下的数组就会显得有些冗余（判断5趟，每一趟依次递减）。那有没有比较好的方案去优化这种情况？答案是有的，我们可以定义一个TAG，来判断是否发生变化。我们知道发生位置变化的时机是在内层循环里面进行操作的，因此我们可以这样操作：
关于冒泡排序的内容基本上就介绍到这里。
选择排序：
选择排序对Java开发来说也不是那么陌生，因为Java内置了API方便我们快速调用，那么关于选择排序的解释是（来自百度百科）：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）。
简单选择排序的基本思想：给定数组：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
举例：首先定义一个数组 int [ ] arr = { 5,2,8,4,9,1 } ; 那么根据上面的定义，选择排序的逻辑就应该按照以下步骤去执行：
第一趟排序： 原始数据：5 2 8 4 9 1 最小数据1，把1放在首位，也就是1和5互换位置，排序结果：1 2 8 4 9 5
第二趟排序：第1以外的数据{ 2 8 4 9 5 }进行比较，2最小。排序结果：1 2 8 4 9 5
第三趟排序：除1、2以外的数据{ 8 4 9 5 }进行比较，4最小，8和4交换。排序结果：1 2 4 8 9 5
第四趟排序：除第1、2、4以外的其他数据{8 9 5}进行比较，5最小，8和5交换。排序结果：1 2 4 5 9 8
第五趟排序：除第1、2、4、5以外的其他数据{9 8}进行比较，8最小，8和9交换。排序结果：1 2 4 5 8 9
通过以上试验步骤有以下结论：
A：一个数组是需要n-1趟排序的(因为直到剩下一个元素时，才不需要找最大值)
B：每交换1次，再次找最大值时就将范围缩小1
C：查询当前趟数最大值实际不用知道具体的属性值是多少，也就是我们只需知道其索引即可，交换也可以根据角标来进行交换
根据以上结论结合循环的使用，我们可以有以下选择排序的代码：
在上面关于选择排序的概念提到，这是一种不稳定的排序方法，那么什么叫排序的稳定性？为了更好的理解这一概念，首先看下这个数组 int [ ] arr = { 6,6,2 } ; 排序的稳定性是指：排序前2个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，如果相同，则是稳定的排序方法；如果不相同，则是不稳定的排序方法。假定我们使用选择排序的话，那第一趟排序后结果就是[2,6,6]。因为这个数组在定义之初就有两个相同的值，属性值对应的索引分别是array [0] 和array [1]，结果经过排序，array[0]的跑到了array[2]上了。
那么这导致了：2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同，因此，我们就说它是不稳定的
再回到上面的问题，为什么冒泡排序是稳定的，主要原因是：冒泡排序进行俩俩比较的时候，没有对相等的数据进行交换(因为没必要)。因此它不存在2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同。
那么稳定排序的好处是什么？一种说法如下：如果我们只对一串数字排序，那么稳定与否确实不重要，因为一串数字的属性是单一的，就是数字值的大小。但是排序的元素往往不只有一个属性，例如我们对一群人按年龄排序，但是人除了年龄属性还有身高体重属性，在年龄相同时如果不想破坏原先身高体重的次序，就必须用稳定排序算法。
关于选择排序和排序的稳定性的内容基本上就介绍到这里。
插入排序：
什么是插入排序？插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。插入排序是一种稳定的排序方法。那么如何更好的去理解插入排序？玩过斗地主的小伙伴都知道，我们起手第一张手牌以后，然后抽到第二张牌一般都会放到第一张手牌的左边或者右边，类似下图：
插入排序就是借用了这种思想，先给定一个排好序的序列（通常设定为 给定要排序序列的第一个值），然后陆续将后面的值与前面排好序的比较，如果是小于前面的值，就插到前面去。就这样一直比较，然后最后总会插入到合适的位置，当然啦，如果是插入到第一位了，也算完成了插入。
插入排序执行流程如下：
现在假设有一个数组，n是数组的长度。
首先假设第一个元素被放置在正确的位置上，这样仅需从1 —— n-1 范围内对剩余元素进行排序。对于每次遍历，从0 —— i-1 范围内的元素已经被排好序。每次遍历的任务是：通过扫描前面已排序的子列表，将位置 i 处的元素定位到从0 到 i 的子列表之内的正确的位置上。
我们可以 arr[ i ] 赋值给名为target的临时元素。向下扫描列表，比较这个目标值target 与 arr[ i-1 ]、arr[i-2]的大小，依次类推。这个比较过程在小于或等于目标值的第一个元素( arr[ j ] )处停止，或者在列表开始处停止（j = 0）。
如果出现arr[ i ]小于前面任何已排序元素时，后一个条件（j = 0）为true，因此，这个元素会占用新排序子列表的第一个位置。在扫描期间，大于目标值target的每个元素都会向右滑动一个位置（arr[ j ] = arr[ j-1 ]）。一旦确定了正确位置 j，目标值target（即原始的arr [ i ]）就会被复制到这个位置。
与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换。
有了上面的流程，可以有以下的代码：
本篇文章主要学习的是基础排序中的冒泡排序、选择排序、插入排序，下一篇学习快速排序、归并排序。
如果这篇文章对你有帮助，希望各位看官留下宝贵的star，谢谢。
Ps:著作权归作者所有,转载请注明作者, 商业转载请联系作者获得授权，非商业转载请注明出处(开头或结尾请添加转载出处，添加原文url地址),文章请勿滥用,也希望大家尊重笔者的劳动成果。
