插入排序算法 插入排序算法c语言

声明：前面标题插入排序的文章，内容其实是选择排序，是笔者马虎了，请各位原谅。

0. 说明

最近工作中遇到了排序的需要，其实很简单，就是两个PO按照时间的字段排序后将结果返回前端，很简单的一个需求，但是却让我感觉应该将排序算法，整理一下。

今天在本文中，我们就先整理下插入排序的算法，分析下怎么交换两个数据将在后续的文章中详细解释。

1. 选择排序

插入排序的原理很简单，就是每次遍历将未排序的数组中第一个数按照大小顺序插入到已经有序的队列中。直到遍历后已排序的数组长度为原始数组的长度。这里主要是数字在往有序队列中插入的过程中的定位问题，一般情况下都是通过遍历比较待插入数据与已排序数据的大小。画个图下看下大概的流程。图中的测试数据数组为[6,4,2,8,3,5].

该示例是从小到大排序，这里就是待排序数据与已排序数据比较，当待排序数据大于等于已排序数据继续往后移动，直到某一个有序数据大于待排序数据，或者有序数据已经遍历完了，就确定待排序的数据位置，然后将原来待排序位置以及气候的所有有序数据往后移动一个位置。注意移动的比较多。

理论上需要遍历n-1次，而且每次遍历要找到最小值的平均比较次数为n/2，还有移动次数平均也是n/2，所以理论上的平均操作次数为(n-1) * (n/2 + n/2)， 也就是说平均的算法复杂度为O(n^2)。

2. Java 实现

笔者的主语言是Java，所以就用Java做一个简单的示例：

public class InsertSort {
 public static int[] sort(int[] arr) throws Exception {
 for (int i = 1; i < arr.length ; i++) {
 int j = 0;
 for (; j < i; j++) {
 if (arr[i] < arr[j]) {
 break;
 }
 }
 for (int k = i; k > j; k--) {
 int tmp = arr[k];
 arr[k] = arr[k - 1];
 arr[k - 1] = tmp;
 }
 }
 return arr;
 }
}

测试代码：

@Test
public void test_bubble_sort() throws Exception {
 int[] arr = {6,4,2,8,3,5};
 arr = InsertSort.sort(arr);
 System.out.println(Arrays.toString(arr));
 int[] arr2 = new int[100];
 Random random = new Random(10000);
 for (int i = 0 ; i < 100; i++) {
 arr2[i] = random.nextInt(10000);
 }
 System.out.println(Arrays.toString(arr2));
 arr2 = InsertSort.sort(arr2);
 System.out.println(Arrays.toString(arr2));
}

运行结果：

[2, 3, 4, 5, 6, 8]
[2208, 572, 9116, 3475, 4500, 9574, 5641, 9166, 9727, 7670, 3030, 6816, 2621, 2172, 8074, 7634, 7455, 3468, 5423, 4888, 3594, 3684, 5136, 363, 4111, 6762, 4480, 4705, 3924, 4626, 72, 6234, 9073, 2345, 6824, 9818, 616, 5521, 4831, 30, 1515, 6297, 3430, 7197, 5985, 8791, 9926, 9276, 2467, 165, 8650, 9054, 8881, 326, 479, 1079, 7714, 5235, 2119, 9051, 456, 6343, 1629, 2903, 4130, 1667, 1219, 4171, 2075, 3998, 1896, 8627, 2752, 205, 565, 9185, 718, 9435, 8710, 25, 473, 1909, 9798, 8473, 7050, 4229, 9859, 8290, 4896, 3176, 1808, 6647, 4743, 2942, 2249, 4657, 2598, 3790, 9841, 5276]
[25, 30, 72, 165, 205, 326, 363, 456, 473, 479, 565, 572, 616, 718, 1079, 1219, 1515, 1629, 1667, 1808, 1896, 1909, 2075, 2119, 2172, 2208, 2249, 2345, 2467, 2598, 2621, 2752, 2903, 2942, 3030, 3176, 3430, 3468, 3475, 3594, 3684, 3790, 3924, 3998, 4111, 4130, 4171, 4229, 4480, 4500, 4626, 4657, 4705, 4743, 4831, 4888, 4896, 5136, 5235, 5276, 5423, 5521, 5641, 5985, 6234, 6297, 6343, 6647, 6762, 6816, 6824, 7050, 7197, 7455, 7634, 7670, 7714, 8074, 8290, 8473, 8627, 8650, 8710, 8791, 8881, 9051, 9054, 9073, 9116, 9166, 9185, 9276, 9435, 9574, 9727, 9798, 9818, 9841, 9859, 9926]

3. 总结

插入排序算法是最简单的排序算法之一，它需要由于又嵌套遍历，外部遍历次数为n-1，内部遍历次数平均为n/2，插入移动次数也是平均为n/2，所以它的时间复杂度是O(n^2), 空间复杂度是O(1)，基本上只占有一个临时空间，但也可以做到不占用额外的空间，这个留作排序系列文章之后也就是[交换两个数据swap](./交换两个数swap.md)详细说明，如有兴趣可关注本公众号。该算法还是稳定的排序算法，因为两个相等的数据在遍历的时候，不会交换位置，而且所有的交换都是相邻两个数据的交换，所以该排序算法是稳定的排序算法。

希望本文对各位看官理解排序算法有所帮助。

求**评论、点赞、关注+转发**

限于笔者知识有限，如果不足之处请帮忙指正，不喜勿喷！

您的支持是我不懈努力的动力，请读者多支持下！

更多文章，请关注微信公众号 CS_Toper之路，或者头条号 CSToper。