数据结构之八大算法详解(1)——希尔排序，堆排序，插入排序，选择排序，冒泡排序！

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

直接插入排序的特性总结：

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

2. 时间复杂度：O(N2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

   设为逆序插入排序的时间复杂度算法为

   设有n个元素的数组从第一个开始到最后一个

   1+2+3+4+....+n−1=n+n(n−1)/2=n2/2+n/21+2+3+4+....+n-1 = n+n(n-1)/2 = n^2/2 + n/2 1+2+3+4+....+n−1=n+n(n−1)/2=n2/2+n/2

   所以其时间复杂度为O(N2)

   当为有序或者接近有序的时候其时间复杂度O(N)，几乎完全不用挪动！

   

   void InsertSort(int* a,int size)//升序
   {
   	for (int i = 0; i < size - 1; i++)//size-1是为了将最后一个当成是插入的值！
   	{
   		int end = i;//这是该数组最后的值
   		int temp = a[end + 1];//这是要插入的值
   		while (end >= 0)
   		{
   			if (a[end] > temp)
   			{
   				a[end + 1] = a[end];
   				end--;
   			}
   			else
   			{
   				break;
   			}
   		}
   		a[end + 1] = temp;//会走到这里说明temp比所有的值都笑，end此时已经到了-1 所以end要+1
   	}
   }
   

希尔排序( 缩小增量排序 ）

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

希尔排序首先要进行的就是预排序，预排序的目的是为了让整个序列接近有序！

然后进行直接插入排序！

这时候我们在对其进行直接插入排序，效果会很好很多！因为直接进行插入对于相当有序的数组效率很高！

void ShellSort(int* a, int size)
{

	int gap = size;
	while (gap>1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)//一共gap组
		{
			for (int i = j; i < size - gap; i += gap)//
			{
				int end = i;
				int temp = a[end + gap];//end+gap [0,end+gap]有序---间隔为gap的数据！
				while (end >= 0)
				{
					if (a[end] > temp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = temp;

			}
		}

	}
	
}



void ShellSort(int* a, int size)
{
	int gap = size;
	//gap越快，大的数据可以越快跳到后面,小的数据可以越快跳到前面！但是越不接近有序！
	//gap越小 跳的越慢也越接近有序！
	while (gap > 1)//进行多次预排序！
	{
		gap = gap / 3 + 1;//这就是为了让他最后可以==1 //这个就是log3为底
		// gap = gap/2 也可以让他最后一次就是1//就是log2为底
		for (int i = 0; i < size - gap; ++i)//这一步比起上面的相当于三组起头并进！上面是一组组的来！
		{
			int end = i;
			int temp = a[end + gap];//end+gap [0,end+gap]有序---间隔为gap的数据！
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;

		}
	}
	//gap>1是预排序
	//gap==1是直接插入排序！
}

gap的时间复杂度的粗略算法

gap组，每组数据有n/gap个

每组都是逆序的最坏情况！则每组预排序的次数都是等差数列

1+2+3+4+…+n/gap

有gap组那么就是

（1+2+3+4+n/gap)*gap

但是每次的预排序的gap都是在变化的！

我们以gap/2来算那么 gap的值为 size/2 size/4 size/8 …1

这个最麻烦的就是我们不可以每次都用最坏的算，因为每次的预排序都会进行一次优化！

下一次的情况一定会比上一次还好！所以我们不可以使用最坏的情况进行计算！

gap很大的要按最坏的情况算

gap很小的时候要按最好的情况算！

希尔排序的特点

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

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定：

我们的gap取值是用kunyh提出来的方法进行取值的，而且kunth，而且Knuth进行了大量的试验统计，我们就按O(n1.25)到O(1.6n1.25)来算！

1. 稳定性：不稳定

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)(每一次调整堆的时间复杂度为logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

第一步建堆

• 升序：建大堆
• 降序：建小堆

为什么要降序建大堆呢？我们一般的想法不是，将小的放在前面吗？那不是应该是小堆吗？

由图我们可以看出来，当我们把最小的找到时候，剩下的数组父子关系已经全乱了！

如果要继续使用它找到次小的，我们就得重新建堆！这样是十分的麻烦的！

但是如果使用的是大堆：

我们先将最后一个与堆顶交换，然后将数组的范围缩小，因为左右的父子关系都是不变的，所以我们可以使用向下调整算法，将第一个到倒数第二个位置（右图中4的位置）范围开始进行向下调整算法，从新找到次大的放在堆顶，然后继续上一步的过程！这我们就完成了升序！

1. 所以就是第二步利用堆删除思想来进行排序！
2. 

//代码演示
typedef int HPdataType;
void AdjustDown(HPdataType* a,int parent,int size)
{
    int child = parent*2+1;
    
    while(child < size)
    {
        if(child +1 < size && a[child] < a[child+1])
        {
            child++;
        }
        if(a[parent] < a[child])
        {
            swap(&a[parent],&a[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}
void swap(HPdataType* x,HPdataType* y)
{
    HPdataType temp = *x;
    *x = *y;
    *y = temp;
}
int main()
{
    HPdataType a[] = {1,4,19,15,7,34,65,25,27,8};
    
    int size = sizeof(a)/sizeof(a[0]);
    for(int i = (size-2)/2;i>=0;i--)//i>0的话无法调整到顶部！
    {
        AdjustDown(a,i,size);
    }//完成建堆
    for(int i = 1;i<size;i++)
    {
        swap(&a[0],&a[size-1-i]);//为什么要-i呢，因为把该堆最大（小）的放在最后面，然后就不要动他，开始放次大（小）
        AdjustDown(a,0,size-i);//然后开始进行调整！
    }    
    return 0;
}

直接选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。

直接选择排序步骤

1. 在元素集合==array[i]–array[n-1]==中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3. 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

void SlectSort(int* a, int size)//升序
{
	int begin = 0; int end = size - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		swap(&a[mini], &a[begin]);//因为begin == maxi 所以这样写的话，先是最大和最小互换，然后是最小的最大互换又换回来了！
		swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

void SlectSort(int* a, int size)//升序
{
	int begin = 0; int end = size - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		swap(&a[mini], &a[begin]);
		if (maxi == begin)
		{
			maxi = mini;//修正一下，bigini的位置被换到mini的位置那边去了！
		}
		swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

直接选择排序的特点

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度为O(2)

   时间选择排序的最坏情况和最好情况的时间复杂度都是一样的！

   因为无论如何它都得遍历一遍找打最大和最小值！

3. 空间复杂度为O(1)

4. 稳定性 :不稳定！

冒泡排序也是我们熟悉的一种交换排序！

其本思想：就是根据序列中两个记录键值的比较结果来对换

这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

void BubbleSort(int* a, int size)
{
	for (int i = 0; i < size; i++)
	{
		int exchange = 0;
		for(int j = 1.;j<size-i;j++)
		{
			if (a[j - 1] > a[j])
			{
				swap(&a[j - 1], &a[j]);
				exchange = 1;
			}
		}
		if (!exchange)
		{
			break;
		}
	}
}

冒牌排序特点

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

   最好的情况的下的时间复杂度为O(N)——即在有序的情况下

3. 空间复杂度：O(1)

4. 稳定性：稳定