插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法，其原理可以简述如下：
1.分已排序区间和未排序区间: 将数组分为已排序区间和未排序区间。初始时，已排序区间只包含数组的第一个元素，而未排序区间包含除第一个元素之外的所有元素。
2.依次将未排序区间中的元素插入到已排序区间中的合适位置: 从未排序区间取出第一个元素，将它插入到已排序区间的合适位置，使得已排序区间仍然保持有序。插入的方式是从已排序区间的末尾开始向前比较，找到插入位置后将元素插入其中。
3.重复步骤2直至未排序区间为空: 重复执行上述插入操作，直到未排序区间中的所有元素都被插入到已排序区间中，即整个数组排序完成。
#include <stdio.h>
void Insert_sort(int arr[], int size)
{
int i = 0;
int j = 0;
int temp = 0; // 存放未排好序区间的第一个数
for (i = 1; i < size; i++)
{
temp = arr[i];
j = i - 1; // 存放已排好序区间的最后一个数下标
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
void Print(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%-3d", arr[i]);
}
printf("\n");
}
int main()
{
int arr[10] = {5, 1, 3, 8, 2, 6, 4, 9, 10, 7};
int len = sizeof(arr) / sizeof(arr[0]);
printf("插入排序前：");
Print(arr, len);
Insert_sort(arr, len);
printf("插入排序后：");
Print(arr, len);
return 0;
}
这段代码实现了插入排序算法。 函数Insert_sort用于对传入的数组进行插入排序操作，参数arr表示要排序的数组，参数size表示数组的长度。在插入排序算法中，通过一个循环将数组分为已排好序的区间和未排好序的区间。从未排好序的区间中选择一个数temp，然后将它插入到已排好序的区间中的正确位置。具体操作是，将temp与已排好序的区间中的数逐个比较，如果temp比当前的数小，则将当前的数向后移动一个位置，直到找到temp的正确位置。然后将temp插入到该位置。重复这个过程直到未排好序的区间为空。
函数Print用于打印数组内容，参数arr表示要打印的数组，参数size表示数组的长度。
在主函数中，定义了一个长度为10的数组arr，并初始化了一些数据。然后调用Insert_sort函数进行排序，最后调用Print函数打印排序后的结果。
整体的思路是先将数组分为已排好序的区间和未排好序的区间，然后从未排好序的区间中选择一个数temp，将它插入到已排好序的区间中的正确位置。重复这个操作直到未排好序的区间为空，即完成了数组的排序。
快速排序
将一个数组的起始位置记成left，最后一个元素位置记成right，那么标记left的位置的元素，把该元素看成基准点（key）。
这时候right要不断的向左移动，若right所在位置的元素是小于key位置的元素，那么right停止移动。left要不断的向右移动，若left所在位置的元素是大于key位置的元素，那么left停止移动。总结就是：left找大，right找小。（注意：若将left设置为key，则先移动right然后才能移动left）
当left和right都停下来后，把他们的元素进行交换，交换过后继续移动。
如此反复操作，最后left会走到right的位置，这时候left和right是处于同一位置的，把该位置的元素和key位置的元素进行交换，更新key的位置。
可以观察到，此时数组有了一个特点：以key为中心点，左边区间的元素都是小于基准点key元素的，右边区间的元素都是大于key元素的。
将左边区间又看成一个小数组，右边区间也看成一个小数组。此时左边区间的left就是下标为0的位置，左边区间的right是key-1的位置。右边区间的left是key+1的位置，right是整个大数组的末尾处，既大数组的right。通过递归不断让每个小数组变得有序，最后整个数组也就有序了。
#include <stdio.h>
void swap(int *p1, int *p2) // 交换函数
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int PatrSort1(int *a, int left, int right) // hoare法
{
int key = left; // 定义基准点key
while (left < right) // 当left<right说明还没相遇，继续数组内元素的交换
{
while (left < right && a[right] >= a[key]) // right找小
{
right--;
}
while (left < right && a[left] <= a[key]) // left找大
{
left++;
}
swap(&a[right], &a[left]); // 交换left和right位置的元素
}
swap(&a[key], &a[left]); // 跳出循环说明他们相遇了，将他们位置的元素与key位置的元素交换
key = left; // 更新key的位置
return left; // 返回key元素当前的下标
}
void Qsort(int *a, int begin, int end) // 快速排序（递归法），这里的begin=left，end=right
{
if (begin >= end) //
{
return;
}
int key = PatrSort1(a, begin, end); // 每次递归都会找到一个属于该数组的key
Qsort(a, begin, key - 1); // 递归左右区间
Qsort(a, key + 1, end);
}
void PrintArr(int *a, int n) // 打印数组
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Test_Qsort() // 快排（递归）测试
{
int arr[] = {5, 10, 6, 1, 2, 4, 3, 9};
int sz = sizeof(arr) / sizeof(int);
printf("快速排序前：");
PrintArr(arr, sz);
Qsort(arr, 0, sz - 1);
printf("快速排序后：");
PrintArr(arr, sz);
}
int main()
{
Test_Qsort();
return 0;
}
该代码实现了快速排序算法。具体分析如下：
swap函数：交换两个指针所指向的值的函数。
PatrSort1函数：使用hoare算法进行快速排序。该函数接受一个数组a、左边界left和右边界right作为参数，返回排序后基准元素的下标。
hoare算法的思想是选择一个基准点key，然后将数组分成两部分，一部分是小于等于key的元素，一部分是大于等于key的元素。通过不断地交换元素，最后将基准元素放置到正确的位置。
Qsort函数：递归实现快速排序。该函数接受一个数组a、开始位置begin和结束位置end作为参数。如果开始位置大于等于结束位置，表示该部分已经有序，直接返回。否则，通过PatrSort1函数找到基准元素的下标key，然后递归调用Qsort对基准元素的左右两部分进行排序。
PrintArr函数：打印数组的函数。
Test_Qsort函数：测试快速排序的函数。首先定义一个数组arr，然后调用Qsort函数对其进行排序，并通过PrintArr函数打印排序后的结果。
main函数：调用Test_Qsort函数进行测试。
希尔排序
希尔排序
希尔排序是一种改进版的插入排序，普通的插入排序算法中，是从第2个节点开始，依次插入到有序序列中，这种做法虽然“一次成形”，但研究发现时间效率上这么做并不划算，更“划算”的做法是这样的：
不严格一个个插入使之有序，而是拉开插入节点的距离，让它们逐步有序，比如如下图所示，有无无序列：
84、83、88、87、61、50、70、60、80、99
第一遍，先取间隔为（Δ=5Δ=5），即依次对以下5组数据进行排序：
84、83、88、87、61、50、70、60、80、99
84、83、88、87、61、50、70、60、80、99
84、83、88、87、61、50、70、60、80、99
84、83、88、87、61、50、70、60、80、99
84、83、88、87、61、50、70、60、80、99
注意，当对84和50进行排序时，其他的元素就像不存在一样。因此，经过上述间隔为5的一遍排序后，数据如下：
50、83、88、87、61、84、70、60、80、99
50、70、88、87、61、84、83、60、80、99
50、70、60、87、61、84、83、88、80、99
50、70、60、80、61、84、83、88、87、99
50、70、60、80、61、84、83、88、87、99
最终的结果（50、70、60、80、61、84、83、88、87、99）是经过这一遍间隔Δ=5Δ=5的情况下达成的，接下去缩小间隔重复如上过程。例如让间距Δ=3Δ=3：
50、70、60、80、61、84、83、88、87、99
50、70、60、80、61、84、83、88、87、99
50、70、60、80、61、84、83、88、87、99
50、70、60、80、61、84、83、88、87、99
将上述粗体的每一组数据进行排序，得到：
50、70、60、80、61、84、83、88、87、99
50、61、60、80、70、84、83、88、87、99
50、61、60、80、70、84、83、88、87、99
50、61、60、80、70、84、83、88、87、99
最终的结果（50、61、60、80、70、84、83、88、87、99）更加接近完全有序的序列。接下去继续不断减小间隔，最终令Δ=1Δ=1，确保每一个元素都在恰当的位置。
代码如下：
#include <stdio.h>
#include <math.h>
int comp_count = 0;
int swap_count = 0;
void show(int data[], int len)
{
int i;
for(i=0; i<len; ++i)
{
printf("%d\t", data[i]);
}
printf("\n");
return;
}
// 起点 节点个数 间距
void insert_sort(int data[], int len, int delta)
{
if(len <= 1)
return;
for(int i=delta; i<len*delta; i+=delta)
{
int j, tmp = data[i];
for(j=i-delta; j>=0; j-=delta)
{
comp_count++;
if(data[j] < tmp)
break;
swap_count++;
data[j+delta] = data[j];
}
data[j+delta] = tmp;
}
}
void shell_sort(int data[], int len)
{
if(len <= 1)
return;
for(int delta=len/2; delta>0; delta/=2)
{
for(int i=0; i<delta; ++i)
{
// 起点 节点个数 间距
insert_sort(data+i, len/delta, delta);
}
}
}
int main(void)
{
// 准备产生一些随机数
srand(time(NULL));
int i, data[100];
for(i=0; i<100; i++)
{
int exp = (int)pow(10, rand()%3+3);
data[i] = rand()%exp;
}
printf("随机序列: ");
show(data, 100);
printf("希尔排序: ");
shell_sort(data, 100);
show(data, 100);
printf("总共比较次数: %d\n", comp_count);
printf("总共移动次数: %d\n", swap_count);
return 0;
}
该代码实现了希尔排序算法。希尔排序是一种插入排序的改进版本，它通过将待排序序列分割成若干个子序列，并对每个子序列进行插入排序，最后再对整个序列进行一次插入排序。希尔排序的关键在于选择合适的间隔序列，通过不断缩小间隔来逐步完成排序。
在该代码中，首先定义了全局变量comp_count和swap_count，用于统计比较次数和移动次数。然后实现了show函数用于打印数组元素，insert_sort函数用于对子序列进行插入排序，shell_sort函数用于实现希尔排序。
在主函数中，通过调用rand函数生成一些随机数，并将其存入数组data中。然后调用shell_sort函数对数组进行希尔排序。最后打印排序后的数组以及比较次数和移动次数。
标签：arr,排序,int,算法,right,key,数据结构,left From： https://blog.csdn.net/weixin_69851948/article/details/144904034