十大排序之插入排序
汇总在这里 十大排序汇总
插入排序(Insertion Sort)
算法介绍:
插入排序的代码实现虽然没有选择排序和冒泡排序那么简单粗暴,但它的原理应该是最容易理解的了,因为插入排序在我们的日常生后中就经常用到,他的排序方式就向我们打扑克时抽牌插牌的过程。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
原理:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤2~5。
代码实现:
void insert_sort(int arr[],int len){
for(int i = 1;i <= len-1;i++){ //初始状态为arr[0]在手中,[1~len-1]待插入
int new_insertion = arr[i]; //将新插入的值存下来,命名为new_insertion
int j = i - 1; //j为插入值前的值的引索
while(j >= 0 && arr[j] > new_insertion){
arr[j+1] = arr[j]; //比插入值大,往后移一位
j--; //比下一个值
}
arr[j+1] = new_insertion; //找到了合适的位置,把新插入的值放进去
}
}
代码中使用一个外循环来迭代未排序区域,从第二个元素开始(索引为1)。内循环使用变量j来比较已排序区域中的元素,如果找到比new_insertion大的元素,则将该元素向后移动一位。内循环继续直到找到合适的位置将new_insertion插入其中。最后,将new_insertion插入到正确的位置后,外循环继续迭代下一个未排序元素。
这样,经过整个循环,数组中的元素将按升序排列。
插入排序的优化
插入排序有一种优化算法,叫做拆半插入。折半插入排序是一种对插入排序的改进,通过利用二分查找来确定插入位置,以减少比较和移动的次数,从而提高排序效率。
void binary_insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int new_insertion = arr[i]; // 将新插入的值存储在变量new_insertion中
int left = 0; // 已排序区域的左边界
int right = i - 1; // 已排序区域的右边界
// 使用二分查找确定插入位置
while (left <= right) {
int mid = (left + right) / 2; // 中间位置
if (arr[mid] > new_insertion)
right = mid - 1;
else
left = mid + 1;
}
// 将插入位置后的元素依次向后移动
for (int j = i - 1; j >= left; j--) {
arr[j+1] = arr[j];
}
// 将新插入的值放入正确的位置
arr[left] = new_insertion;
}
}
在这个优化版本中,我们使用了二分查找来确定插入位置。通过不断将已排序区域的范围缩小一半,最终找到了合适的插入位置。然后,我们需要将插入位置后的元素依次向后移动,为新插入的元素腾出空间。最后,将新插入的值放入正确的位置。
这种优化可以减少比较和移动的次数,从而提高插入排序的效率。请注意,折半插入排序仍然属于比较简单的排序算法,而在某些情况下,其他更高级的排序算法可能会更加高效。
时间复杂度:
最佳情况时间复杂度:如果输入数组已经按升序排列(或者近乎有序),那么插入排序的最佳情况时间复杂度为O(n),其中n是数组的长度。这是因为在这种情况下,内循环中的比较操作很少执行,每个元素只需要比较一次就可以确定其位置。
最坏情况时间复杂度:如果输入数组是按降序排列的,那么插入排序的最坏情况时间复杂度为O(n^2)。在这种情况下,每个元素都需要与已排序的部分进行比较和移动,导致内循环中的比较和移动操作都被执行。
平均情况时间复杂度:在平均情况下,插入排序的时间复杂度也为O(n^2)。虽然在某些特定的输入情况下,插入排序的性能可能会比较好,但在平均情况下,仍然需要执行大量的比较和移动操作。
空间复杂度:
插入排序的空间复杂度为O(1),即不需要额外的空间来存储数据。
稳定性:
插入排序是一种稳定的排序算法。在插入排序中,当遇到相等元素时,不会改变它们的相对顺序。具体来说,当需要将一个元素插入已排序序列的合适位置时,如果有多个相等元素,算法会将当前元素插入到相等元素的最后一个位置,从而保持它们的相对顺序不变。