算法笔记（三）插入排序

算法背景前面我们讨论了冒泡排序。其算法的核心是：依次比较相邻的两个数，让较大的值慢慢浮出水面，达到其合适的值。使数组排序的位置。也可以说冒泡排序就是按照从高到低的顺序确定元素的位置。稳定的O(n2)选择排序方法在时间复杂度上也是稳定的O(n2)排序方法。其算法的核心是：从第一次排序的数据元素中选择最小（或最大）的一个元素存储在序列的开头，然后从中找到最小（最大）的元素剩余的未排序元素，然后放在已排序序列的末尾。以上两种算法的局限性在于，它们忽略了原数组是否在某一段排序，例如int[]arr={0,1,2,3,5,4,3}，在这种排序中process，某时刻前3项已经有序，无需再关注。再来看看插入排序：插入排序，一般也称为直接插入排序。它是一种对少量元素进行排序的高效算法。插入排序是最简单的排序方法。它的基本思想是在一个已经排好序的有序表中插入一条记录，创建一个新的有序表，记录数增加1。在实现过程中使用了双层循环。外层循环查找除第一个元素以外的所有元素，内层循环查找当前元素前面的有序列表中要插入的位置并移动。------百度百科算法思想插入排序就像很多人排序一手扑克一样。我们从空着的左手开始，牌面朝下放在桌子上。然后，我们一次从桌子上拿一张牌，把它插在左手的正确位置上。为了找到一张牌的正确位置，我们将它与手中已有的每张牌进行比较，从右到左。左手拿着的牌总是排序的，原来这些牌就是桌上牌堆里最上面的牌。插入排序的意思是在待排序的元素中，假设前面的n-1（其中n>=2）个数已经排好序，现在把第n个数插入到前面排好的数列中，然后找到适合自己的位置，使得第n个数插入的数列也是有序的。按照这种方法，插入所有元素，直到整个序列排序完毕，称为插入排序。图算法的二层循环，我们先保证0-i是有序的，然后得到数组中的第i+1个元素，从后往前插入到0-i中合适的位置，在这次0-i+1也是有顺序的，然后得到第0-i+2个元素插入到0-i+1中合适的位置。直到0-n都是有序的。第一类JAVA代码：publicstaticvoidinsertSorting(int[]arr){for(inti=1;i=0&&arr[j]>arr[j+1];j--){swap(arr,j,j+1);}}}publicstaticvoidswap(int[]arr,inti,intj){arr[i]=arr[i]^arr[j];arr[j]=arr[i]^arr[j];arr[i]=arr[i]^arr[j];}上面的实现会将exchange条件和for循环是否继续，合并到合适的位置。第二个实现不合并。第二种：publicstaticvoidinsertSorting(int[]arr){for(inti=1;i=0;j--){如果(arr[j]>arr[j+1])交换(arr,j,j+1);否则中断；}}}publicstaticvoidswap(int[]arr,inti,intj){arr[i]=arr[i]^arr[j];arr[j]=arr[i]^arr[j];arr[i]=arr[i]^arr[j];}两段代码的执行是一样的，只是写法不同而已。第二段代码的elsebreak一定要加上，否则时间会增加，违背了插入排序的思想。算法BestTimeWorstTimeAverageTimeExtraSpaceInsertionO(n)O(n2)O(n2)0/1在排序算法中，我们一般要关注最坏时间复杂度，可以看到，选择排序最坏时间复杂度of、冒泡排序和插入排序是O(n2)。