排序之插入排序与选择排序_1.采用插入排序方法进行排序。 2. 采用选择排序方法进行排序。 要求:(1)用数组进

在我们日常生活中，排序的使用可谓是相当广泛，一个好用的排序算法，可以让速度大大提高，今天我们来学习八大排序的四种直接插入排序、希尔排序、选择排序、堆排序。

目录

一、直接插入排序

二、希尔排序

三、选择排序

四、堆排序

---

一、直接插入排序

直接插入排序是一种简单的插入排序法

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

我们玩扑克牌的时候，就用了这种排序方法 ，我们一张一张的摸牌，便是一次次的将无序的扑克牌，插入到我们已排序好的手牌中。

第一张牌一定是有序的，后面每一次摸牌就是在原本有序的扑克里面进行插入。

 在实际的代码中，因为要挪动数据，因此我们通常选择将插入的那个变量，从数组的最右边往左比较，如果比数组这一位小，则将数组这一位往后挪动，又往前一直重复比较，直到比较完整个数组或者比数组的这一位要大才结束。具体流程如图所示。

图片来源于：八大排序详解-超详细_想找后端开发的小杜的博客-CSDN博客 

 插入排序代码实现

1. 我们将第一个a[0]元素视为已排序部分，其余的元素视为未排序部分。从第二个元素开始，逐个遍历未排序部分的元素。
2. 对于当前遍历的元素，将其与已排序部分的元素逐一比较，直到找到合适的位置。较大的元素向右移动一个位置，为当前元素腾出插入位置。重复这个过程，直到找到正确的插入位置。
3. 继续遍历未排序部分，重复上述比较和插入步骤，直到所有元素都被插入到已排序的部分。

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

插入排序的时间复杂度是O(n^2)，但是，如果是在数据有序的情况下，它的时间复杂为O(n)。

二、希尔排序

希尔排序是一个天赋不够但是非常勤奋的孩子，他靠自己的努力，变成了一个很厉害的排序，时间复杂度比他的孩子插入排序高很多。

希尔排序跟插入排序原理一样，但是多了预排序，他将间隔为gap组的数据分别进行插入排序

当gap为三的时候，分别对上图黑线和红线还有绿线进行插入排序，完成预排序，这样即可让数组接近有序，然后再用直接插入排序，因为直接插入排序对接近于有序的数组时间复杂度是O(n)，便能大大提升速度 

图片来源于排序算法之希尔排序_希尔排序单数_morris131的博客-CSDN博客

希尔排序代码实现

void ShellSort(int* a, int n)
{	
    int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = gap + 0; j < n; j++)
		{
			int end = j - gap;
			int tmp = a[j];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
		if (gap == 1)
			break;
	}
}

这里我们的gap = gap / 3 + 1;，使得预排序之后，数组能够更接近与有序。

希尔排序的时间复杂度难以计算，因为对于不同的数据，gap的最佳选择也是不同的，他的多样性是杠杠的，但经过大量的实验，我们可以暂时按照O(n^1.3)来算。

三、选择排序

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

1. 首先，从未排序的数据中选择最小（或最大）的元素。
2. 将选中的元素与未排序部分的第一个元素交换位置，将其放在已排序部分的末尾。
3. 然后，在剩余的未排序数据中再次选择最小（或最大）的元素，将其与未排序部分的第一个元素交换位置。
4. 重复上述过程，每次选择一个最小（或最大）的元素，并将其放在已排序部分的末尾。
5. 当所有元素都被选择并放置在已排序部分时，排序完成。

选择排序流程如图 

图片来源：最常见的六种排序算法的详解_互相离不开这是采用了什么算法-CSDN博客

代码实现

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
			if (a[mini] > a[i])
			{
				mini = i;
			}
		}
		swap(a[maxi], a[end]);
		if (mini == end)
		{
			mini = maxi;
		}
		swap(a[mini], a[begin]);
		begin++;
		end--;
	}
}

这里我们同时进行了最小值和最大值处理，这样可以比普通的选择排序快两倍，只需最后进行判断mini是否是end即可。

四、堆排序

堆排序的核心思想就是建堆。堆可以看成是一颗完全二叉树。

例如一个数组 arr[] = {8,6,10,5,3,7,4,9,13};把他放在二叉树中就类似于这样

数组的索引依然没有变，只是我们把他画成了上图，这是方便我们观看理解的逻辑图，

这里我们选择构建大堆，就是把最大的值放到最上面，父亲结点的左右子树的值比他小。又把左右子树当父亲节点，他的子节点的依然要比他小。如下图就是一个构建好的大堆。 

父节点比他的两个子节点要大   如下图  13>9   13>10

若该子节点还有子节点，那么他也比他的子节点要大  如图  9>8  9>3 

以此类推

如果我们构建出了这样一个堆，就可以把第一个元素a[0]和最后一个元素互换a[size-1]，变成了下图这样，这样我们保证了最后一个元素是最大的。因此我们才选择的是大堆 

并且在这里我们可以发现，最后一个元素不看的情况下，只有第一个元素不符合大堆，其他元素都符合大堆的特性，因此现在的调整很简单，只需要把左右子节点的较大值与之交换，再往下交换，直到没有子节点 或者 他比自己的子节点大就行了，如下两图。

到这里又可以将最大值与倒数第二个数交换了，以此类推，又调整，在交换，一步一步变成升序。

那到现在我们的首要目标是先构建一个大堆，核心代码如下：

//a为指针  表示的是数组首元素的地址   n为数组长度   root为这个节点的索引
void AdjustDown(int* a, int n, int root)
{
    int parent = root; //把这个节点设置为父亲节点
    int child = parent*2+1;//完全二叉树的左子节点为父亲节点*2+1
    while(child<n)
    {
        if(child+1<n&&a[child]<a[child+1])//判断是否有右子节点，
                                          //并且比较左右子节点的大小
        {
            child++;   //哪个子节点大  就用那个子节点
        }
        if(a[child]>a[parent])
        {
            swap(&a[child],&a[parent]);//子节点比父亲大，就交换，让大的往上走
            parent = child;
            child = parent*2+1;  //父亲节点变子节点，子节点又往下走
        }
        else
        {
            break;
        }
    }
}

 这只是向下调整的代码，如果大堆已经构建好，执行起来就没有问题，如果大堆还未构建，则需要从最后一个非叶子节点  即下图中的5依次往前走，走到10，再到6，再到8。依次步步构建。

要从第一个非叶子结点开始构建，保证该节点下面为大堆，再一步一步往前构建，逐步构建为大堆，后续交换再次构建即可完成排序。

void Heapsort(int *nums,int numsSize)
{
    for(int i=(numsSize-1-1)/2;i>=0;i--)//i为最后一个节点的父节点（即最后一个非叶子节点）
    {
        AdjustDown(nums,numsSize,i);//从后往前走，保证自己为父节点时是大堆，往上走依然是大堆
    }
 
    int end = numsSize-1;//到这已经构建好一个完美的大堆，下面准备开始交换
    while(end>0)
    {
        swap(&nums[0],&nums[end]);//第一个节点和未排序的最后一个节点交换
        AdjustDown(nums,end,0);//再次调整，最后的节点已经是最大  无需调整了
        end--;
    }
}