排序算法1--插入排序

目录

1.常见排序算法

2.排序算法的预定函数

2.1交换函数

2.2测试算法运行时间的函数

3.插入排序

3.1直接插入排序

3.2希尔排序

3.3插入排序的时间复杂度分析

4.总结

---

1.常见排序算法

我将分别讲解五种排序算法，但是不代表只有五种固定的代码，之后会进行延伸扩展出很多种，每一个我都将分为一篇来进行讲解。但是有些算法的实现将依靠之前的数据结构知识，所以如果想要看懂这些算法的实现需要打牢数据结构的基础。每一个算法都需要一定的测试函数，所以我们需要给定一些测试用例来测试该算法是否适用于每一个算法，我们现在给定一些测试用例：1 2 3 4 5 6 7 8 9；9 8 4 2 4 1 3 7 5 ；2 3 4 3 4 2 7 9 2 4；100 101 195 124 125 129；以上四种测试用例对于不同的排序算法每一个测试用例可能会表现出不同的时间复杂度，每一个测试用例也有每一个测试用例对应的时间复杂度最好的一种或几种算法，我们在实现排序时我们需要一些预定的函数，如：交换函数，测试运行时间的函数等。

2.排序算法的预定函数

2.1交换函数

我们需要两个整型类型的指针（之后我们排序排列的都是整型），我们暂时不用typedef了，否则这样比较难理解。

//交换函数
void Swap(int* a, int* b)
{int p = *a;*a = *b;*b = p;
}

2.2测试算法运行时间的函数

这个函数我们权当只是用来测试每一个排序算法最终在实际运用时的表现，我们先进行自己的测试用例的测试，代码无误了再进行实际运用的测试。我们每一次学完这个算法就把这个算法的注释删除即可。

// 测试排序的性能对⽐
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}

上面的排序算法除了冒泡排序外我们之前基本上没学过，所以每一次我们都和冒泡排序进行比较。

3.插入排序

插入排序是把待排序的记录按照其关键码值的大小逐个插入奥一个已经排好序的序列中，直到所有的记录插完为止。就和我们平时打扑克牌的时候进行一张张插入。

3.1直接插入排序

当插入第i(i>=1)个元素是，前面的arr[0]到arr[i-1]已经排好序，我们把arr[i]和arr[i-1]进行比较，我们假设是排成升序，则如果arr[i]>arr[i-1]，我们就把arr[i]插入到arr[i-1]后面一位；如果小于或等于，则arr[i-1]后移一位，然后arr[i]和arr[i-2]进行相同的操作，直至arr[0]为止。所以最终代码如下：

//直接插入排序(升序)
void InsertSort1(int* arr, int n)
{for (int i = 0; i < n - 1; i++){//我们把需要比较的数放入tmp中，然后先与第i个数据比较，依次往前进行比较插入int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}//如果end=-1我们不能进行数组越界，所以要进行+1操作arr[end + 1] = tmp;}
}
int main()
{int a[] = { 5,3,9,6,2,4,7,1,8 };//int a[] = { 1,2,3,4,5,6,7,8,9 };//int a[] = { 9,8,4,2,4,1,3,7,5 };//int a[] = { 2,3,4,3,4,2,7,9,2,4 };//int a[] = { 100,101,195,124,125,129 };int n = sizeof(a) / sizeof(a[0]);printf("排序之前： ");for (int i = 0; i < n; i++){printf("%d ", a[i]);}InsertSort1(a, n);printf("\n排序之后： ");for (int i = 0; i < n; i++){printf("%d ", a[i]);}return 0;
}

由于我们包含的头文件中含有InsertSort所以我定义的时候我们需要把名字改一下（我们需要手动实现，不能用头文件的）

在VS2022编译器上我们需要把之前的函数TestOP注释掉，否则会报错哦。我们发现每一个排序都没有问题，所以代码无误。我们用测试函数测试一下：

记得把其他没用的函数先注释掉并且把TestOP中的函数名字改为InsertSort1。代码就不放在这里了。我们发现：100000个数据竟然排了13秒的时间，所以这个算法时间复杂度比较高，但是很好理解，所以这个算法只起到教学的作用。

3.2希尔排序

希尔排序又称为缩小增量法。希尔排序法基本思想是：先选定一个整数通常是gap=n/3+1，把待排序的数据分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。比如有一组数据为9 1 2 5 7 4 8 6 3 5,这个gap就相当于我们每隔gap个数据进行取数，比如gap=2，就把9 2 7 8 3放入一个数组中，然后在这个数组中进行排序，这样使这个原数组基本上有序了，所以我们之后到gap=1时就会少循环次数，至于gap开始取多少，我们一般取n/3+1，后面我们取gap/3+1这样最后一次一定是直接插入排序，所以能这样进行排序，但是相当于直接插入排序我们的for循环要进行i+=gap吗？并且后面我们交换的时候是直接进行gap+end和end进行交换吗？至于解释我们要看代码才能理解，每一次调整的时候我们也需要让end-=gap，并且我们最外层需要多添加一个while循环来判断gap是否为1，所以最终代码如下：

//希尔排序
void ShellSort1(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

运行结果为

运行结果没有问题，解决一下为什么里面还是i++，因为我们分为了n/gap组，我们每次都是先从第一个组进行排序，再是第二个组，我们是先排序第一个数组的第一个元素，后面是第二个数组的第一个元素，依次类推，这就是原因，之后我们来测试希尔排序的时间：

可以发现：虽然我们有三层循环，但是时间复杂度降低了很多，所以说希尔排序在特定情况下是一种好的算法。

3.3插入排序的时间复杂度分析

直接插入排序的时间复杂度比较高，我们发现在最好的情况下，就是如果数组已经是升序的情况下，内层循环需要1次，而外层循环需要n次，所以最好情况下的时间复杂度为O(n)，但是一般条件下我们是看其最坏的情况下，是降序排列的话，里面循环1+2+3+4+……+n次，而外层循环为n-1次，大概是O(n^2)所以直接插入排序不是很好的算法。但是希尔排序我们无法估计，通过很多测试得到的是其近似值，一般为O(n^1.3)，这是平均情况，最好的当然是O(n)，我们只要知道希尔排序时比较好的即可，因为gap的值可以取的情况很多，我们无法估计！

4.总结

插入排序理解和实现相对简单，但是之后的排序相对于这个排序更好一些，所以还要多知道一些排序算法更好一点，我们遇到的题目很多，我们也要很多的手段来应对每一种题目，所以继续加油吧！