常用的简单排序之插入排序，冒泡排序，选择排序，希尔排序

1、插入排序

   插入排序的工作原理是建立有序序列，对于未排序数据，在已排序的数据从后先前扫描，找到对应的位置后插入。

   ①从第一个元素开始，该元素被默认为有序序列。

   ②从下一个未排序数据开始，在已经排序的序列中从后往前扫描     

   ③如果该元素小于已排序的元素，继续往前扫描

   ④重复③，直到找到该元素大于或等于已排序的元素的位置

   ⑤插入该元素

   ⑥重复②

代码：

void InsertSort(int *a,int size)
{
	assert(a);
	for (int i = 1; i < size; i++)
	{
		int index = i;
		int end = index - 1;         //已排序序列最后一个元素下标
		int temp = a[index];         //保存未排序数据的值
		while (end >= 0 && temp < a[end])
		{
			a[end + 1] = a[end]; //当为排序数据小于已排序序列数据时，把已排序数据向后移一位
			end--;  //继续往前扫描
		}
		a[end + 1] = temp; //找到未排序数据大于或等于已排序序列，或者整个已排序序列没有一个数小于未排序数据时
	}
}

  插入排序对几乎已经排好序的数据进行操作时，效率很高。但插入排序一般来说是低效的，每次只能挪动数据一位。

2、选择排序

  选择排序的思想是每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最前，直到全部待排序的数据元素排完。

void SelectSort(int *a,int size)

{

  assert(a);

  for(int i=0;i<size;i++)

  {

    int min=i;

    for(int j=i+1;j<size;j++)

    {

      if(a[min]>a[j])

        min=j;

    }

   swap(a[i],a[min]);

  }

}

还可以优化，我们可以在选出最小的元素放在序列头的同时，选出最大的元素放在序列尾

void SelectSort(int *a, int size)
{
	assert(a);
	for (int left = 0, right = size - 1;left<=right;left++,right--)
	{
		int max = right, min = left;
		for (int i = left; i <= right; i++)
		{
			if (a[min] > a[i])
				swap(a[min],a[i]);
			if (a[max] < a[i])
				swap(a[max],a[i]);
		}
		swap(a[min], a[left]);
		swap(a[max], a[right]);
	}

3、冒泡排序

 从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，一个最大的数沉底成为数组中的最后一个元素，一些较小的数如同气泡一样上浮一个位置。

void BubSort(int* a,int size)
{
	for (int i = 0; i < size; i++)
	{
		int symbol = false;
		for (int j = 1; j < size - i ; j++)
		{
			if (a[j] < a[j - 1])
				swap(a[j], a[j - 1]);
				symbol = true; 
		}
		if (symbol == false) //当symbol为false时，就说明后面的已经有序
			break;
	}
}

4、希尔排序

  希尔排序其实是更优化的插入排序。

  其思想为：

    把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

void ShellSort(int *a, int size)
{
	assert(a);
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = gap; i < size; i++)//比如当gap=4时，并不是让它分别进行4组插入排序，而是采用一种比较巧的方法，让i从gap开始每次加1，这样就能把4组插入排序，一次走完
		{
			int index = i;
			int temp = a[index];
			int end = index - gap;
			while (end >= 0 && temp<a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			a[end + gap] = temp;
		}
	}
}