常见排序宝典：帮助快速上手常见基础排序算法(上）

//冒泡排序
void Swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}


void Bubble_sort(int* arr, int len)
{
	int i, j;
	for ( i = 0; i < len; i++)
	{
		for (j = 0; j < len - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(arr[j], arr[j + 1]);
			}
		}
	}
}

void Swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}

//选择排序
void Selection_sort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		int min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		Swap(arr[min], arr[i]);
	}
}

void Selection_sort(int* arr, int len)
{
	int begin = 0, end = len - 1;
	while (begin < end)
	{
		int max = begin, min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[min] > arr[i])
			{
				min = i;
			}
			if (arr[max] < arr[i])
			{
				max = i;
			}
		}
		Swap(arr[max], arr[end]);//如果end与min重合了，或者max与begin重合了，就会出现一个位置多次被交换数值，导致数值对不上顺序的情况
		//由于max与end交换在前，倘若min与end重合，第一次就相当于max与min交换了一次，原本的min指向了最大值，但后面的交换min所指的最大值会被交换到begin的位置上，使顺序出错
		if (min == end)
		{
			min = max;//纠正，把min所指向的位置移到了最小值所在地
		}

		Swap(arr[min], arr[begin]);
		//倘若min与begin交换在前，就是讨论max是否与begin重合，然后修改max为正确的值了
		begin++;
		end--;
	}
}

//插入排序
void Swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}

void Insert_sort(int* arr, int len)
{
	for (int end = 0; end < len - 1; end++)
	{
		int i = end + 1;
		while (i > 0 && arr[i] < arr[i - 1])
		{
			Swap(arr[i], arr[i - 1]);
			i--;
		}
	}
}

//希尔排序
void Shell_sort(int* arr, int len)
{
	int gap = len;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < len - gap; i++)//gap相当于是当前分出来的组数，gap组，总共len个数，只需要len-gap次排序就行
		{
			int end = i;
			int tmp = arr[end + gap];//tmp的值固定为了arr[end+gap]，当end值变的时候，tmp也会跟着改变
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;//if出循环的话，end最后减了gap，现在加上gap相当于是让arr[end]等于tmp，交换了值。break出循环，两值本来就相等
		}
	}
}