细数排序（1）

插入排序

void insertsort(int *arr, int n)
{
	int i;
	for (i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
        }
		arr[end+1] = tmp;//因为走到了要求的数的前一个位置，那么他的后一位就是我们要插入的位置
	}
}

希尔排序

// 时间复杂度是O(N*logN);
void shellsort(int *arr,int n)
{
	//为了应对假如说使用插入排序的时候，那个数过于无序，如我们对一个逆序的数组，将他排序成顺序的，
	//一个一个的排时间复杂度过于大，太浪费了
	//所以我们可以使用中间间隔多的为一组进行排序，尽量把大的数字放到后面去，小的数字放到前面去，做到尽量有序
	//当间隔为1的时候就是直接插入排序
	int gap = n;
	int i;
	while (gap > 1)
	{
		gap = gap / 2;//如果gap是%2的话，最后gap会变成1，就是直接插入排序
			//假如我们是gap=gap/3的话，最后可能就不能变成1变成直接插入排序了,希尔排序内部的算法可以类比，直接插入排序，只不过把原来的1变成了gap
		
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;

				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}


}

选择排序

void selectsort(int *arr, int n)
{
	int begin = 0, end = n - 1;//
	while (begin < end)//begin和end分别从两边开始走，begin一方找到的是最小的那些数，end一方找到的是最大的一些数，当两者相遇或者刚好走到挨着的时候，就排序完成了
	{
		int max=begin, min=begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[begin])
			{
				min = i;//把最小的下标存到min里面
			}
			if (arr[i] > arr[begin])
			{
				max = i;//把最大的下标存到max里面
			}
		}
		swap(&arr[begin], &arr[min]);//处理完后把找到的最小下标和begin进行交换
//假如说第一个就是最大的，那交换之后，最大的就和最小的交换了
if(begin==maxi)
{
maxi=mini;
}
		swap(&arr[end], &arr[max]);//把最大下标和end进行交换
		begin++;
		end--;
	}
}

快速排序

void quicksort(int *arr, int left,int right)
{
	if (left >= right)//当left>right就算是不存在，=就是只有一个值，都是不用排
	{
		return;
	}
	int begin = left, end = right;
	int pivot = begin;//把左边做一个坑
	int key = arr[begin];//把左边的数作为关键字，保存起来
	//一趟的排序
	while (begin < end)//左边做坑则右边先动
	{
		//右边找小，放到左边

		while (begin < end&&arr[end] >= key)//大于就--，小于才停下来//同时end走的必须是在begin右边，因为begin左边都是以及处理过的，所以end要大于begin
		{
			--end;
		}
		//找到的小的，放到左边，从而自己形成了新的坑位
		arr[pivot] = arr[end];
		pivot = end;
		//现在去找大
		while (begin<end &&arr[begin] <= key)//始终保证begin<end的条件
		{
			++begin;
		}
		//大的放到左边的坑，自己形成新的坑位
		arr[pivot] = arr[begin];
		pivot = begin;
	}
	pivot = begin;//到达了中间的位置
	arr[pivot] = key;
	//[在left，right]
	//每次调用这函数都被分成3部分
	//[left,pivot-1],pivot,[pivot+1,right]//始终被分成了这三个部分，pivot是已经有序的了
	//只要让左子区间和右子区间有序，我们就有序了，我们就用到了分治递归的思想
	quicksort(arr, left, pivot - 1);
	quicksort(arr, pivot + 1, right);
}