插入排序算法描述将数组分为两部分左边为有序的部分右边为无序的部分。每次从无序部分的最左边元素插入到有序部分。代码实现voidInsertionSort(intA[],intN){inti,Pos;//插入位置intTmp;for(i1;iN;i){TmpA[i];//待插入的元素的值for(Posi;A[Pos-1]TmpPos0;Pos--)A[Pos]A[Pos-1];A[Pos]Tmp;}}算法分析(复杂度)插入排序的时间开销可以看成由两部分组成固定时间开销O(N)O(N)O(N)消除逆序的时间开销O(I)O(I)O(I)T(N)O(NI) T(N) O(N I)T(N)O(NI)最坏情况分析当数组完全逆序时对于每一个位置PosPosPos都要做Pos1Pos 1Pos1次的比较 :A[Pos−1]TmpA[Pos - 1] TmpA[Pos−1]Tmp和Pos0Pos 0Pos0同时要做PosPosPos次右移数组元素的操作:A[Pos]A[Pos−1]A[Pos] A[Pos - 1]A[Pos]A[Pos−1]所以可以得到时间复杂度的一个上界:I∑Pos1N−1(Pos1)(2N)(N−1)2O(N2) I \sum_{Pos 1}^{N - 1} (Pos 1) \dfrac{(2 N)(N - 1)}{2} O(N^2)IPos1∑N−1(Pos1)2(2N)(N−1)O(N2)此时插入排序总的复杂度为T(N)O(IN)O(N2N)O(N2) T(N) O(I N) O(N^2 N) O(N^2)T(N)O(IN)O(N2N)O(N2)最好情况分析当数组完全有序时此时不需要消除逆序所以总的时间复杂度为T(N)T(NI)O(N) T(N) T(N I) O(N)T(N)T(NI)O(N)平均情况分析插入排序就是不断消除逆序的过程 其在O(1)O(1)O(1)的时间只可以消除一个逆序所以我们必须要关注数组的平均逆序的个数我们必须假设数组中没有重复的元素因为逆序的概念要成立定理一个有NNN个互不相同的元素的数组numsnumsnums的平均逆序的个数为N(N−1)4\frac{N(N-1)}{4}4N(N−1)证明过程也很简单。我们该数组的倒序数组为nums−nums^-nums−, 对于下标xxx,yyy满足xyx yxy,那么就有{nums[x]nums[y]nums−[x]nums−[y]\begin{cases} nums[x] nums[y] \\ nums^-[x] nums^-[y]\end{cases}{nums[x]nums[y]nums−[x]nums−[y]或{nums[x]nums[y]nums−[x]nums−[y]\begin{cases} nums[x] nums[y] \\ nums^-[x] nums^-[y]\end{cases}{nums[x]nums[y]nums−[x]nums−[y]也就是说两个数组有且仅有一个逆序而这样的下标(x,y)(x, y)(x,y)总共有N(N−1)2\frac{N(N - 1)}{2}2N(N−1)个 所以numsnumsnums数组平均有N(N−1)4\dfrac{N(N-1)}{4}4N(N−1)个逆序因此插入排序平均要消除的逆序的开销为IO(N(N−1)4)O(N2) I O(\frac{N(N-1)}{4}) O(N^2)IO(4N(N−1))O(N2)因此插入排序的平均复杂度为T(N)O(NN(N−1)4)O(N2) T(N) O(N \frac{N(N-1)}{4}) O(N^2)T(N)O(N4N(N−1))O(N2)推论只通过交换相邻元素的排序算法的平均时间复杂度为O(N2)O(N^2)O(N2)因为该类排序算法本质就是在不断的消除逆序并且在O(1)O(1)O(1)的时间内只能消除一个逆序可以很明显的感觉到交换的元素相距近对于消除逆序并没有好处。逆序的平均个数为(N(N−1)4\frac{(N(N-1)}{4}4(N(N−1), 所以该类算法的时间复杂度为O(N2)O(N^2)O(N2)所以要想突破O(N2)O(N^2)O(N2)的时间界 就要在O(1)O(1)O(1)的时间内消除多个逆序插入排序是一种非显式通过交换相邻元素的算法 因为在O(1)O(1)O(1)的时间内只能消除一个逆序插入排序有两个突出的优点 在数组很小或数组趋于有序时 其时间复杂度趋于O(N)O(N)O(N)
插入排序算法分析
插入排序算法描述将数组分为两部分左边为有序的部分右边为无序的部分。每次从无序部分的最左边元素插入到有序部分。代码实现voidInsertionSort(intA[],intN){inti,Pos;//插入位置intTmp;for(i1;iN;i){TmpA[i];//待插入的元素的值for(Posi;A[Pos-1]TmpPos0;Pos--)A[Pos]A[Pos-1];A[Pos]Tmp;}}算法分析(复杂度)插入排序的时间开销可以看成由两部分组成固定时间开销O(N)O(N)O(N)消除逆序的时间开销O(I)O(I)O(I)T(N)O(NI) T(N) O(N I)T(N)O(NI)最坏情况分析当数组完全逆序时对于每一个位置PosPosPos都要做Pos1Pos 1Pos1次的比较 :A[Pos−1]TmpA[Pos - 1] TmpA[Pos−1]Tmp和Pos0Pos 0Pos0同时要做PosPosPos次右移数组元素的操作:A[Pos]A[Pos−1]A[Pos] A[Pos - 1]A[Pos]A[Pos−1]所以可以得到时间复杂度的一个上界:I∑Pos1N−1(Pos1)(2N)(N−1)2O(N2) I \sum_{Pos 1}^{N - 1} (Pos 1) \dfrac{(2 N)(N - 1)}{2} O(N^2)IPos1∑N−1(Pos1)2(2N)(N−1)O(N2)此时插入排序总的复杂度为T(N)O(IN)O(N2N)O(N2) T(N) O(I N) O(N^2 N) O(N^2)T(N)O(IN)O(N2N)O(N2)最好情况分析当数组完全有序时此时不需要消除逆序所以总的时间复杂度为T(N)T(NI)O(N) T(N) T(N I) O(N)T(N)T(NI)O(N)平均情况分析插入排序就是不断消除逆序的过程 其在O(1)O(1)O(1)的时间只可以消除一个逆序所以我们必须要关注数组的平均逆序的个数我们必须假设数组中没有重复的元素因为逆序的概念要成立定理一个有NNN个互不相同的元素的数组numsnumsnums的平均逆序的个数为N(N−1)4\frac{N(N-1)}{4}4N(N−1)证明过程也很简单。我们该数组的倒序数组为nums−nums^-nums−, 对于下标xxx,yyy满足xyx yxy,那么就有{nums[x]nums[y]nums−[x]nums−[y]\begin{cases} nums[x] nums[y] \\ nums^-[x] nums^-[y]\end{cases}{nums[x]nums[y]nums−[x]nums−[y]或{nums[x]nums[y]nums−[x]nums−[y]\begin{cases} nums[x] nums[y] \\ nums^-[x] nums^-[y]\end{cases}{nums[x]nums[y]nums−[x]nums−[y]也就是说两个数组有且仅有一个逆序而这样的下标(x,y)(x, y)(x,y)总共有N(N−1)2\frac{N(N - 1)}{2}2N(N−1)个 所以numsnumsnums数组平均有N(N−1)4\dfrac{N(N-1)}{4}4N(N−1)个逆序因此插入排序平均要消除的逆序的开销为IO(N(N−1)4)O(N2) I O(\frac{N(N-1)}{4}) O(N^2)IO(4N(N−1))O(N2)因此插入排序的平均复杂度为T(N)O(NN(N−1)4)O(N2) T(N) O(N \frac{N(N-1)}{4}) O(N^2)T(N)O(N4N(N−1))O(N2)推论只通过交换相邻元素的排序算法的平均时间复杂度为O(N2)O(N^2)O(N2)因为该类排序算法本质就是在不断的消除逆序并且在O(1)O(1)O(1)的时间内只能消除一个逆序可以很明显的感觉到交换的元素相距近对于消除逆序并没有好处。逆序的平均个数为(N(N−1)4\frac{(N(N-1)}{4}4(N(N−1), 所以该类算法的时间复杂度为O(N2)O(N^2)O(N2)所以要想突破O(N2)O(N^2)O(N2)的时间界 就要在O(1)O(1)O(1)的时间内消除多个逆序插入排序是一种非显式通过交换相邻元素的算法 因为在O(1)O(1)O(1)的时间内只能消除一个逆序插入排序有两个突出的优点 在数组很小或数组趋于有序时 其时间复杂度趋于O(N)O(N)O(N)
