[C语言]插入排序+希尔排序

2023-06-28 20:33| 来源: 网络整理| 查看: 265

1.插入排序 1.1插入排序的思想

直接插入排序是一种简单的插入排序方式，它的基本思想是：把没有排序的数据按照它值的大小依次插入到已经排序过的序列中，一直到所有数据都排序完，生成一个新的系列。

比如说在玩斗地主时的发牌场景，玩家会按照拿到手的牌去判断这张牌应该放在什么位置。

1.2直接插入排序

直接插入排序：当插入到第i( i>1 )个数据时，前面arr[0],arr[1].......arr[i-1]已经是有序的，然后用arr[i]的值与arr[i-1]，arr[i-2]按顺序依次进行比较，找到插入位置即将arr[i]插入，接着把原来位置上的元素顺序往后移。重复这样的操作就完成了排序。

1.3代码 void InsertSort(int* a, int n) { for (int i = 0; i < n-1; i++) { //记录有序部分的最后一个元素下标 int end = i; //记录要插入的数据 int temp = a[i+1]; while (end >= 0) { //如果最后一个数比要插入的元素大就往后移 if (a[end] > temp) { a[end + 1] = a[end]; end--; } //比插入元素小就停止单前循环 else { break; } } //把插入元素放在比插入元素小的后一位 a[end + 1] = temp; } } 2.希尔排序（缩小增量排序）

希尔排序又称为缩小增量排序，选定一个整数gap，把待排序的序列分成gap组，所有间隔为gap的数据为一组，对这一组数据进行排序，排完所有组就缩小gap，重复之前的分组与排序一直到gap == 1，就完成了排序。

关于gap取多少并没有明确要求：

最初 Shell 提出取 gap = n/2 ，gap = gap/2，直到 gap = 1Knuth 提出取 gap = gap/3 + 1还有人提起都取奇数比较好也有人提出各 gap 互为质为好

void ShellSort(int* a, int n) { //gap初值赋数组的长度 int gap = n; while (gap > 1) { //gap每次除3加1 gap = gap / 3 + 1; //一趟排序，简单说就是把插入排序的依次比对改成间隔gap位比对 for (int i = 0; i < n - gap; i++) { int end = i; int temp = a[i + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; end -= gap; } else { break; } a[end + gap] = temp; } } } }

【本文地址】

公司简介

联系我们