【数据结构】插入、希尔、选择、冒泡四种排序算法_对直接插入排序、简单选择排序、快速排序、希尔排序这几种常用排序算法进行比较。

一、排序的概念及其应用

1.1排序算法的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
 

1.2排序算法的应用：

比如在再买东西是商品的价格，好评数，还有高考完以后学生的分数排名，学校的排名等等；

排序算法在日常生活中使用得非常的频繁，所以这是我们必须掌握的一项算法

1.3常见的排序算法

 二.排序算法的实现

2.1直接插入排序

直接插入排序是一种简单的插入排序，其基本思想为：

把待排序的记录按其关键码值的大小逐个插入到一个有序的序列中，知道所有的记录插入完为止，得到一个新的有序序列

 当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

排升序时，插入排序就相当于把选中的数据保存起来，然后让 大于它的数据往后移，等它前面没数据了，或前面的数据比它小时就拍好了这个数，接着排下一个数，依次往后，最后就拍好了

void Insert(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

直接插入排序特性总结：

1.元素集合越接近有序，直接插入排序算法的时间效率越高

2.时间复杂度为（N^2)，集合接近有序时，时间复杂度为（N）

3.空间复杂度为（1）

4.稳定性：稳定

 2.2希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个n组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后依次取gap/2，重复上述分组和排序的工作。当到达gap=1时，所有记录就在统一组内排好序。

 当gap依次除二，gap等于1的时候，此时的希尔排序就相当于了直接插入排序，希尔排序和直接插入排序思想差不多，就是一个数组被分成了几组，进行预排序，最后当gap等于一时，该组数组就接近有序了，然后再重复上述的方法再排一次就欧克了

void Shellsort(int* a, int n)
{
	int gap = n;
	while (gap > 0)
	{
		gap/=2;
		// i<n-gap防止越界！！
		for (int i = 0; i < n-gap; i ++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
		
	}
}

希尔排序的特性总结：

1.希尔排序是对直接插入排序的优化

2.当gap>1时都是预排序，目的是让数组接近有序，当数组接近有序了的时候，这样就会很快了，这样整体而言就达到了优化的效果

3.希尔排序的时间复杂度不好计算，因为gap的值不统一（ 大约在O（n^1.25)~~O(1.6*n^1.25) )

4.稳定性：不稳定

2.3选择排序

选择排序思想：每次选出最小的一个数和起点位置的对应的数进行交换，然后依次类推。

当遍历一遍数组的时候可以发现，可以选出最小的数，那么最大的数也能一并选出来所以可以每次选出最小的一个数和最大的一个数，然后让最小的数和开始位置第一个下标对应的数交换，再让最大的数和最后一个下标对应的数进行交换，然后依次缩小范围进行循环

void Swap(int* p1, int* p2)
{
		int tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
}
 
void Selectsort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int maxi = left, mini = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
			if (a[mini] > a[i])
			{
				mini = i;
			}
		}
			Swap(&a[left],&a[mini]);
 
			if (maxi == left)//为了防止最大的数的下标在起点位置，交换乱序
			{
				maxi = mini;
			}
			Swap(&a[right], &a[maxi]);
			left++;
			right--;
	}
}

选择排序的特性总结：

1.时间复杂度：O（N^2）

2.空间复杂度：O（1）

3.稳定性：不稳定

2.4冒泡排序

冒泡排序是一种交换排序，核心是冒泡，把数组中最大的那个往上冒，冒的过程就是和他相邻的元素交换。 重复走访要排序的数列，通过两两比较相邻记录的排序码。 排序过程中每次从前往后冒一个最大值，且每次能确定一个数在序列中的最终位置。 若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边，下面的代码是先把大的冒泡到后面

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void bubbleosrt(int* a, int n)
{
	int end = n;
	while (end > 0)
	{
		int flag = 0;
		for (int i = 0; i < end-1; i++)
		{
			if (a[i + 1] < a[i])  //小于就交换
			{
				flag = 1;
				Swap(&a[i + 1], &a[i]);
			}
		}
		if (flag == 0)break;
		end--;
	}
}

冒泡排序总结

1.时间复杂度：O（N^2）

2.空间复杂度：O（1）

3.稳定性：稳定

2.5堆排序

堆排序去往这  堆排序实现