直接插入排序 (Insertion Sort)基本思想将待排序序列分为已排序和未排序两部分。每次从未排序区取出第一个元素在已排序区中从后向前扫描找到合适位置并插入。算法步骤从第一个元素开始该元素可以认为已经被排序。取出下一个元素在已经排序的元素序列中从后向前扫描。如果已排序的元素大于新元素将该元素移到下一位置。重复步骤 3直到找到已排序的元素小于或等于新元素的位置。将新元素插入到该位置后。重复步骤 2~5直到所有元素均排序完毕。动态演示时间复杂度最好情况输入数组已有序。每轮仅需 1 次比较无元素移动总比较次数为n−1n-1n−1时间复杂度为O(n)O(n)O(n)。最坏情况输入数组逆序。第iii轮需比较iii次移动iii次总比较和移动次数约为n(n−1)/2n(n-1)/2n(n−1)/2时间复杂度为O(n2)O(n^2)O(n2)。平均情况时间复杂度为O(n2)O(n^2)O(n2)。空间复杂度算法仅使用了常数个辅助变量key、j等不需要额外数组因此是原地排序空间复杂度为O(1)O(1)O(1)。稳定性当遇到与key相等的已排序元素时不会插入到其前面循环条件为arr[j] key因此相等元素的相对顺序保持不变直接插入排序是一种稳定排序。代码实现 (C语言)#includestdio.hvoidinsertion_sort(intarr[],intn){for(inti1;in;i){intkeyarr[i];// 当前待插入的元素intji-1;// 将比 key 大的元素都向后移动一位while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;// 插入到正确位置}}
直接插入排序 (Insertion Sort)基本思想将待排序序列分为已排序和未排序两部分。每次从未排序区取出第一个元素在已排序区中从后向前扫描找到合适位置并插入。算法步骤从第一个元素开始该元素可以认为已经被排序。取出下一个元素在已经排序的元素序列中从后向前扫描。如果已排序的元素大于新元素将该元素移到下一位置。重复步骤 3直到找到已排序的元素小于或等于新元素的位置。将新元素插入到该位置后。重复步骤 2~5直到所有元素均排序完毕。动态演示时间复杂度最好情况输入数组已有序。每轮仅需 1 次比较无元素移动总比较次数为n−1n-1n−1时间复杂度为O(n)O(n)O(n)。最坏情况输入数组逆序。第iii轮需比较iii次移动iii次总比较和移动次数约为n(n−1)/2n(n-1)/2n(n−1)/2时间复杂度为O(n2)O(n^2)O(n2)。平均情况时间复杂度为O(n2)O(n^2)O(n2)。空间复杂度算法仅使用了常数个辅助变量key、j等不需要额外数组因此是原地排序空间复杂度为O(1)O(1)O(1)。稳定性当遇到与key相等的已排序元素时不会插入到其前面循环条件为arr[j] key因此相等元素的相对顺序保持不变直接插入排序是一种稳定排序。代码实现 (C语言)#includestdio.hvoidinsertion_sort(intarr[],intn){for(inti1;in;i){intkeyarr[i];// 当前待插入的元素intji-1;// 将比 key 大的元素都向后移动一位while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;// 插入到正确位置}}
