一、 直接插入排序

1.概念

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

2.直接插入排序的实现

void insertsort(int* a, int sz)//直接插入排序   [0 end]有序，插入end+1位置的值让[ 0 end+1]也有序
{
	int i = 0;//假设我们要排升序
	for (i = 0; i < sz - 1; i++)//i不能取到sz-1 否则tmp就会造成越界访问
	{
		int end = i;
		int tmp = a[end + 1];//后一个数据
		while (end >= 0)
		{
			if (a[end] > tmp)//如果数组中的数据大于tmp
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;//找到比tmp小的就结束循环
			}
		}
		a[end + 1] = tmp;//为了防止tmp比所有数据都小这种情况发生
	}
	
}

直接插入排序的时间复杂度

二、 希尔排序

1.概念

思想为 ：先选定一个整数，把 待排序文件中所有记录分组，所有距离内的记录在同一组中，再对每一组内的记录进行排序，重复分组和排序， 直到=1时结束.

希尔是直接插入排序的优化
1.先进行预排序,让数组接近有序
2.直接插入排序

此时发现： 多组间隔为gap的预排序，gap由大变小
gap 越大，大的数越快到后面，小的数越快到前面
gap越大，预排完，越不接近有序，
gap越小，预排完，越接近有序
当gap=1时，就时直接插入排序

2. 希尔排序的实现

void shellsort(int* a, int n)//希尔排序
{
	int i = 0;
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1; //间隔为gap的多组数据同时排
		for (i = 0; i < n - gap; i++)//如果gap换成1  那就是直接插入排序
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

3. 希尔排序的时间复杂度

1. gap=n , gap=gap/3+1 即 n=n/3+1
   假设 x为操作次数 3^x=n+1 x=log 3 n+1
   时间复杂度为 O(log 3 N)

2.预排序会使数组接近有序 ,如gap=1 时 ，就为直接插入排序，时间复杂度为O(N)

希尔排序 整体时间复杂度为O(N *log 3 N )

三、 直接选择排序

1.直接选择排序的实现

void selectsort(int arr[], int n)//直接选择排序
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{

		int max = begin;
		int min = begin;
		int i = 0;
		for (i = begin; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;//通过交换找到最大值坐标
			}
			if (arr[i] > arr[max])
			{
				max = i;//通过交换找到最小值坐标
			}
		}
		swap(&arr[begin], &arr[min]);//通过坐标将最小值交换到第begin个
		if (begin == max)
		{
			max = min;
		}
		swap(&arr[end], &arr[max]);//通过坐标将最大值交换到第end个
		begin++;
		end--;
	}
}

2.注意事项

3.直接选择排序的时间复杂度

直接选择排序 ,无论 数组处于 有序 （最好情况下），还是无序 (最坏情况下) 都需要将整个数组遍历一遍 ，
时间复杂度为O(N^2)

四、 堆排序

点击这里 :堆排序详解

五、冒泡排序

1.冒泡排序的实现

void bubblesort(int* a, int sz)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)// i代表趟数  i在倒数第二次就已经把数组排好了 
	{
		int exchange = 0;
		for (j = 0; j < sz - 1 - i; j++)//j代表每趟的对数 
		{
			if (a[j] > a[j + 1])
			{
				int tmp = 0;
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				exchange = 1;
			}
		}
		if (exchange == 0)//说明遍历一遍都没有进行比较，则有序
		{
			break;
		}
	}
}

2.冒泡排序的时间复杂度

正常情况下:
第一趟时，共比较 n-1次 ，
第二趟时，共比较n-2 次，
第n-1趟时，共比较1次
操作次数为: n-1+n-2+n-3+…+1=n(n-1)/2
通过大O渐进法省略 ,时间复杂度为O(N^2)

最好情况下:
数组为有序时 ，如 ： 1 2 3 4 5
正好排升序，遍历一遍后发现并没有进入交换中，exchange==0则跳出循环。
时间复杂度为O(N)

3.冒泡排序与直接插入排序谁更好？

当数组接近有序时 ，如： 1 2 3 5 4 6
1.冒泡排序:

2.直接插入排序:
1 2 3 5 4 6

时间复杂度为O(N)

则直接插入排序更优