一.插入排序 InsertSort
基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
当插入第i(i>=1)个元素时，前面的arr[0],arr[1],…,arr[i-1]已经排好序，此时用arr[i]的排序码与arr[i-1],arr[i-2],…的排序码顺序进行比较，找到插入位置即将arr[i]插入，原来位置上的元素顺序后移。
动图演示
特性总结
1. 元素集合越接近有序，直接插入排序算法的时间效率越高；
2. 时间复杂度：
a.最坏情况下是O(N^2)；
b.最好情况下，也就是说数据是有序的，这时是O(N)；
3. 空间复杂度：O(1)，它是一种稳定的排序算法；
4. 稳定性：稳定；
1. void InsertSort(Sdatatype* arr, int n) 2. { 3. int end = 0, tmp = 0; 4. int i = 0; 5. for (i = 1; i < n; i++) 6. { 7. end = i - 1; 8. tmp = arr[i]; 9. while (end >= 0) 10. { 11. if (tmp < arr[end]) 12. { 13. arr[end + 1] = arr[end]; 14. end--; 15. } 16. else 17. break; 18. } 19. arr[end + 1] = tmp; 20. } 21. 22. 23. }
二.希尔排序 ShellSort
基本思想
希尔排序分为预排序（即分组插排，让数组接近有序）和直接插入排序；
希尔排序是把数据分成gap组，每隔gap距离的属于一组数据，对每一组内的数据进行插入排序，这样就可以让整体数据更接近有序状态，这样其内部的插入排序的时间复杂度就接近于O(N)；
假设要排升序：
gap越大，跳的越快，循环的次数越少，大的数据能更快的到后面去；
gap越小，跳的越慢，循环的次数越多。
那这个gap取多少合适呢？
我们可以采用动态的gap，当一组gap跑完时，让gap/2，以此类推，因为是/2，所以gap最后的值一定是1，gap==1时就是直接插入排序了。
我们既可以采用一组一组排的方式，也可以采用多组同时进行的方式。
图例
特性总结
1. 希尔排序是对直接插入排序的优化；
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比；
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：但是我们一般认为是O(N^1.3)；
4.稳定性：不稳定。
1. void ShellSort(Sdatatype* arr, int n) 2. { 3. int i = 0, j = 0; 4. int end = 0, tmp = 0; 5. int gap = n; 6. //一组一组地排 7. /*while (gap > 1) 8. { 9. gap /= 2; 10. for (j = 0; j < gap; j++) 11. { 12. for (i = 0; i < n - gap; i += gap) 13. { 14. end = i; 15. tmp = arr[end + gap]; 16. while (end >= 0) 17. { 18. if (tmp < arr[end]) 19. { 20. arr[end + gap] = arr[end]; 21. end -= gap; 22. } 23. else 24. break; 25. } 26. arr[end + gap] = tmp; 27. } 28. } 29. }*/ 30. 31. //同时进行排序 32. while (gap > 1) 33. { 34. gap /= 2; 35. for (i = 0; i < n-gap; i++) 36. { 37. end = i; 38. tmp = arr[end + gap]; 39. while (end >= 0) 40. { 41. if (tmp < arr[end]) 42. { 43. arr[end + gap] = arr[end]; 44. end -= gap; 45. } 46. else 47. break; 48. } 49. 50. arr[end + gap] = tmp; 51. } 52. } 53. }
🐬🤖本篇文章到此就结束了，若有错误或是建议的话，欢迎小伙伴们指出；🕊️👻
😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩
😍😁谢谢你的阅读。😸😼
