几种排序算法的原理以及 Java 实现( 二 ) _排序算法

第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,_,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成_,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1 。

第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9 。

（3）编码分析：
需要两层循环，第一层循环index表示上述例子中的指针，即遍历从坐标为1开始的每一个元素；第二层循环从leftindex=index-1开始，leftindex--向左遍历，将每一个元素与i处的元素比较，直到j处的元素小于i出的元素或者leftindex<0；遍历从i到j的每一个元素使其右移，最后将index处的元素放到leftindex处的空位处。
（4）代码实现：
实例
package com.test.insertsort;/** * 插入排序算法： * 1、以数组的某一位作为分隔位，比如index=1，假设左面的都是有序的. * * 2、将index位的数据拿出来，放到临时变量里，这时index位置就空出来了. * * 3、从leftindex=index-1开始将左面的数据与当前index位的数据（即temp）进行比较，如果array[leftindex]>temp, * 则将array[leftindex]后移一位，即array[leftindex+1]=array[leftindex],此时leftindex就空出来了. * * 4、再用index-2(即leftindex=leftindex-1)位的数据和temp比，重复步骤3， * 直到找到<=temp的数据或者比到了最左面（说明temp最小），停止比较，将temp放在当前空的位置上. * * 5、index向后挪1，即index=index+1，temp=array[index],重复步骤2-4，直到index=array.length,排序结束， * 此时数组中的数据即为从小到大的顺序. * * @author bjh * */public class InsertSort { private int[] array; private int length; public InsertSort(int[] array){ this.array = array; this.length = array.length; } public void display{ for(int a: array){ System.out.print(a+" "); } System.out.println; } /** * 插入排序方法 */ public void doInsertSort{ for(int index = 1; index<length; index++){//外层向右的index，即作为比较对象的数据的index int temp = array[index];//用作比较的数据 int leftindex = index-1; while(leftindex>=0 && array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环 array[leftindex+1] = array[leftindex]; leftindex--; } array[leftindex+1] = temp;//把temp放到空位上 } } public static void main(String[] args){ int[] array = {38,65,97,76,13,27,49}; InsertSort is = new InsertSort(array); System.out.println("排序前的数据为："); is.display; is.doInsertSort; System.out.println("排序后的数据为："); is.display; }}
（5）插入排序分析：
时间复杂度，由于仍然需要两层循环，插入排序的时间复杂度仍然为O(n*n) 。
比较次数：在第一轮排序中，插入排序最多比较一次；在第二轮排序中插入排序最多比较二次；以此类推，最后一轮排序时，最多比较N-1次，因此插入排序的最多比较次数为1+2+...+N-1=N*(N-1)/2 。尽管如此，实际上插入排序很少会真的比较这么多次，因为一旦发现左侧有比目标元素小的元素，比较就停止了，因此，插入排序平均比较次数为N*(N-1)/4 。
移动次数：插入排序的移动次数与比较次数几乎一致，但移动的速度要比交换的速度快得多。
综上，插入排序的速度约比冒泡排序快一倍（比较次数少一倍），比选择排序还要快一些，对于基本有序的数据，插入排序的速度会很快，是简单排序中效率最高的排序算法。
快排、冒泡排序、选择排序、插入排序、归并排序
一、概述：
上文介绍了常见简单算法：冒泡排序、选择排序和插入排序。本文介绍高级排序算法：快速排序和归并排序。在开始介绍算法之前，首先介绍高级算法所需要的基础知识：划分、递归，并顺带介绍二分查找算法。
二、划分：
划分是快速排序的前提，即把数据分为两组，大于特定值的数据在一组，小于特定值的数据在另一组。快速排序即是由划分和递归操作来完成的。
（1）原理：
【几种排序算法的原理以及 Java 实现】定义一个阈值，分别从最左面和最右面向中间遍历元素，左面找到一个大于阈值的数据便停止，右边找到一个小于阈值的数据便停止，如果此时左右两边都还没有走到中间，则交换左面大于阈值的数据和右面小于阈值的数据；重复上述过程，直到左面指针和右面指针相遇，此时左面数据均小于阈值，右面数据均大于阈值，划分结束。划分结束后，数据仍然是无序的，但更接近于有序。
（2）例子：
待划分数据：7, 6, 9, 8, 5,1，假设阈值为5
第一轮：左指针指向7，右指针指向1，左指针向后移，右指针向左移，发现左面第一个大于5的元素7，右面第一个小于5的元素1，交换7和1的位置，结果：1,6,9,8,5,7；