详解希尔排序，直接插入排序，选择排序（c实现）

void InsertSort(int* arr, int n)//这里的第一个参数是待比较数组，第二个参数是数组的元素个数
{
	for (int i = 1; i < n; i++)
	{
		//我们先来看一趟排序，即现在下标为0到end的元素为有序区元素，而tmp则为我们要插入的元素
		int end = i-1;
		int tmp = arr[i];
		//下面我们要遍历有序区间区寻找位置
		while (end>=0)//这里的end必须等于0因为当有序区只有一个元素的时候，也要进行一次判断
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];//如果正在比较的这个有序区的元素比待插入元素大
				//则将这个有序区元素往后移动
				end--;//比较玩一个元素自然要去寻找下一个
			}
			else
			{
				break;//如果要比较的这个有序区的元素比待比较的这个元素小则要将待插入元素放到这个元素的后面
			}
		}
		arr[end + 1] = tmp;//由此我们就完成了将一个元素放到有序区间，现在我们要将一个数组排序成功，那么肯定要将第一个元素默认为有序元素
	}
}

void testinsertsort()
{
	int arr[] = { 1,4,7,8,5,2,9,6,3,10 };//先写一个无序的数组
	int n = sizeof(arr) / sizeof(arr[0]);//得到数组的元素有多少个
	printf_Arr(arr, n);//这是我写的一个打印数组的函数，因为只用一个for循环就可以解决，所以这里就
  //不展示了
	InsertSort(arr, n);
	printf_Arr(arr, n);
}

void Shellsort(int* arr, int n)
{
	int gap = 3;//这里的gap也就是希尔增量
	//首先我们只写对一组的直接插入排序
	for (int i = 0; i < n; i += gap)
	{
		int tmp = arr[i];//tmp依旧保存待插入元素
		int end = i - gap;//在一组内你知道一组里面的第二个元素的下标为i上一个点的下标自然是i-gap
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + gap] = arr[end];
				end -= gap;//这两个的理由依旧和上面的一样我们要将一个组内的元素进行直接插入排序
			}
			else
			{
				break;
			}
		}
		arr[end + gap] = tmp;//如果找到了tmp在组内所在的正确位置，则将tmp放到哪一个位置上
	}
}

void Shellsort(int* arr, int n)
{
	int gap = 3;//这里的gap也就是希尔增量
	//首先我们只写对一组的直接插入排序
	for (int j = 0; j < gap; j++)//用于控制开始的下标，用于进入不同的组
	{
		for (int i = j; i < n; i += gap)
		{
			int tmp = arr[i];//tmp依旧保存待插入元素
			int end = i - gap;//在一组内你知道一组里面的第二个元素的下标为i上一个点的下标自然是i-gap
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;//这两个的理由依旧和上面的一样我们要将一个组内的元素进行直接插入排序
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;//如果找到了tmp在组内所在的正确位置，则将tmp放到哪一个位置上
		}
	}
}

void Shellsort(int* arr, int n)
{
	int gap = 3;//这里的gap也就是希尔增量
	//首先我们只写对一组的直接插入排序
		for (int i = 0; i < n; i ++)
		{
			int tmp = arr[i];//tmp依旧保存待插入元素
			int end = i - gap;//在一组内你知道一组里面的第二个元素的下标为i上一个点的下标自然是i-gap
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;//这两个的理由依旧和上面的一样我们要将一个组内的元素进行直接插入排序
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;//如果找到了tmp在组内所在的正确位置，则将tmp放到哪一个位置上
		}
}

void Shellsort(int* arr, int n)
{
	int gap = n;//这里的gap也就是希尔增量
	while (gap > 1)//这一个循环也就是对希尔增量进行改变，这里绝对不能等于1不然会死循环
  //因为当gap为2的时候进入循环，下面就会将gap修改为1，如果等于1，那么在gap为1的时候进入
  //1/3为0在加一个1再次变成1，进入死循环。
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n; i++)
		{
			int tmp = arr[i];//tmp依旧保存待插入元素
			int end = i - gap;//在一组内你知道一组里面的第二个元素的下标为i上一个点的下标自然是i-gap
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;//这两个的理由依旧和上面的一样我们要将一个组内的元素进行直接插入排序
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;//如果找到了tmp在组内所在的正确位置，则将tmp放到哪一个位置上
		}
	}
}

void Selectsort(int* arr, int n)
{
	int begin = 0;//数组头
	int end = n - 1;//数组尾
	while (begin < end)//当begin和end相等的时候代表数组已经寻找完毕了
	{
		int maxi = begin;//用于储存最大值的下标
		int mini = begin;//用于储存最小值的下标
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])//如果发现任何一个值小于此时的最小值那就更新这个值
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;//同理更新maxi
			}
		}
		//下面我们就要交换了
		swap(&arr[begin], &arr[mini]);
		if (maxi == begin)//这里需要处理一下当最大的值在begin的位置的时候我们就要修改
    //一下maxi的下标因为经过交换之后begin的元素就被交换到了mini的位置
		{
			maxi = mini;
		}
		swap(&arr[end], &arr[maxi]);
		begin++; end--;
	}
}//时间复杂度尾o（n^2）

void AdjustUp(HPDataType* a, int child)//通过父节点找到孩子节点
{
	int parent = (child - 1) / 2;//这个是父节点和子节点的关系（）
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;//重新为父节点赋值，确保循环继续
		}
		else
		{
			break;//如果父节点大于此时插入的新节点不用继续调整，直接break即可，因为我这里做的是大堆，所以如果这里父节点大于了
			//子节点
		}
	}
}

void AdjustDown(HPDataType* a,int n, int parent)//这里的n就是元素个数
{
	int child = 2 * parent + 1;//我这里假设child就是最大的数
	while (child < n)//因为我们是通过父节点去寻找子节点的，所以当求得到的子节点大于元素个数时，代表parent来到了
		//最底部的节点不能再交换，否则会越界访问
	{
		if (child+1<n&&a[child] < a[child + 1])//如果右孩子大于左孩子就改变child,如果没有右孩子则不需要判断,
			//这里要需要考虑如果改父节点如果只有1个子节点的情况。
      //如果你要建立小堆只用改变为小于号即可
		{
			child++;
		}
		if (a[parent] < a[child])
    //建立小堆这里也要改变为小于号
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;//如果父亲大于最大的孩子则满足大堆条件
		}
	}
}

// 对数组进行堆排序
void HeapSort(int* a, int n)
{
	Heap hp;
	HeapCreate(&hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp,a[i]);//将数组里面的数字全部储存进堆里面
	}
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		int val = HeapTop(&hp);
		a[i++] = val;
		HeapPop(&hp);
	}
	HeapDestory(&hp);//使用这种堆排序的话你建立大堆最后出现的就是降序，而小堆就是升序
	//这种方法可行但是需要我们1先写一个完整的堆，并且这样的写法空间复杂度很高,而且需要我们拷贝数据
}

for (int i = 1; i < n; i++)
	{
		AdjustUp(a,i);
	}//通过向上调整我们就能将数组a调整为一个大堆

for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1代表的是最后一个元素的下标再次-1除以2
  //是找到这个元素的父节点，也就是最后一个父节点
	{
		AdjustDown(a, n, i);
	}

void HeapSort(int* a, int n)
{
	// 对数组进行堆排序
//要使用堆排序我们首先就要建立堆，建立堆有两种方法，其中一种是向上建立堆，一种是向下建立堆，同时排序也有两种排序方式，
//其中一种是升序排列，一种是降序排列
//这里我们需要知道如果你要升序排列那么你要建立大堆
//而如果你要降序排列那么你就要创建小堆
  //至于这是为什么，堆排序的思路也就是我们让堆顶的元素和堆底的元素交换（如果这是大堆那么堆顶的元素就是最大的元素），然后将最后一个元素删除，让上面的元素全部重新调整
  //再次取出次大的元素放到倒数第二个元素，那么到最后我们就会得到一个升序的数列
	//首先是创建一个堆有两种建立方式一种是向上建立堆的方法，一种是向下建立堆的方式这里和上一种方法最不同的一点就是我们直接将待排序的数组建立成堆
	//然后有两种方法建立堆
	//向上调整建堆和向下调整建堆
	//首先就是向上调整建立堆,这里建立堆使用的是原数组即我们不再重新创建一个堆而是将数组建立成堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a,i);
	}//通过向上调整我们就能将数组a调整为一个大堆
	//因为做成的是大堆所以最后排序的时候出来的是一个升序
	//现在开始使用向下调整建立大堆
	//向上调整要满足的条件就是左右子树必须是一个大堆
	//所以我们从堆的最顶层开始向下调整
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1代表的是最后一个元素的下标再次-1除以2是找到这个元素的父节点
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);//交换头尾两个元素
		AdjustDown(a, end, 0);//向下调整重新建立堆，这里的end指的是元素个数，因为我们删除了第n-1个元素，但是第n-1个元素
		//之前的元素个数本来就是n-1
		end--;//最后让end--将最后一个元素删除让其不再进入调整
	}


}

while (end > 0)
	{
		swap(&a[0], &a[end]);//交换头尾两个元素，这里我是写了一个简单的交换两个数的函数
		AdjustDown(a, end, 0);//向下调整重新建立堆，这里的end指的是元素个数，因为我们删除了第n-1个元素，但是第n-1个元素
		//之前的元素个数本来就是n-1
		end--;//最后让end--将最后一个元素删除让其不再进入调整
	}