常用的簡單排序之插入排序，冒泡排序，選擇排序，希爾排序

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;
		}
	}
}