排序1——直接插入排序，希尔排序，选择排序，堆排序

1.排序的概念及其运用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2排序运用

1.3.常见排序

2.插入排序

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

实际中我们玩扑克牌时，就用了插入排序的思想

我们摸牌的时候，每摸一张牌我们就将其插入到有序的位置当中

2.1直接插入排序

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

在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。

//插入排序（升序）
void InsertSort(int* a, int n)
{int i = 0;for (i = 0; i < n-1 ; ++i){int end = i;//记录有序序列的最后一个元素的下标//最开始只有1个元素，是有序的，所以有序序列最后一个元素的下标是0int tmp = a[end + 1];//待插入的元素，就紧跟在有序序列的后面while (end >= 0){if (tmp < a[end])//待插入元素比有序序列最后一个元素还小              {a[end + 1] = a[end];//将有序序列最后一个元素往后移动，为待插入元素留位置end--;//更新新的有序序列的最后一个元素的下标}else   //待插入元素>=有序序列最后一个元素{break;}}//代码执行到此位置有两种情况://1.待插入元素比当前所有有序序列的所有元素都大或等于（break跳出循环到此，end=i）。//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此，end==-1）。a[end + 1] = tmp;//插入元素}
}

我们来深入理解一下，假设给了我们一个数组，我们用直接插入排序将其排成有序的过程如下

如果还不理解，我们就看动画

2.1.1时间复杂度分析

普通插入排序的时间复杂度最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序。
普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序。

2.2希尔排序

现在，我要讲解的算法叫希尔排序（Shell Sort）。

希尔排序是D.L.Shell于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是0(n)，希尔排序算法是突破这个时间复杂度的第一批算法之一。

我们前一节讲的直接插入排序，应该说，它的效率在某些时候是很高的，比如，我们的记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。

可问题在于，两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。

不过别急，有条件当然是好，条件不存在，我们创造条件也是可以去做的。于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以增加效率。

如何让待排序的记录个数较少呢？

很容易想到的就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序，再对全体记录进行一次直接插入排序。

这便是希尔排序的基本内容

希尔排序分成两部分

希尔排序，又称缩小增量法。其基本思想是：

先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

问题：为什么要让gap由大到小呢？
因为gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置，项下面的代码直接设置成三分之一）。

举个例子分析一下：
现在我们用希尔排序对该序列进行排序。

gap的值折半，此时相隔距离为2的元素被分为一组（共分了2组，每组有5个元素），然后再分别对每一组进行直接插入排序。

gap的值再次减半，此时gap减为1，即整个序列被分为一组，进行一次直接插入排序。

该题中，前两趟就是希尔排序的预排序，最后一趟就是希尔排序的直接插入排序。

代码

//希尔排序（升序）
void ShellSort(int* a, int n)
{// gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){//gap /= 2;这个可以，但是有人嫌他慢，所以用了下面那个gap = gap / 3 + 1;//这里加1是为了保证最后一次gap==1for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[i + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

需要注意的是：增量序列最后一个增量值必须是1才可以，因为这个1代表整个序列被分成了一组，对这整个序列再来一次直接插入排序，完成希尔排序第二部分

2.2.1希尔排序复杂度分析

通过这段代码的剖析，相信大家有些明白，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。

这里“增量”的选取就非常关键了。我们在代码中gap=gap/3+1的方式选取增量的，可究竟应该选取什么样的增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。

需要注意的是，增量序列的最后一个增量值必须等于1才行。

另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。

时间复杂度：O(NlogN) 空间复杂度：O(1)

2.2.2希尔排序的特性总结：

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

2.2.2.2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

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

2.2.2. 4. 稳定性：不稳定

3.选择排序

3.1基本思想：

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

代码：

void Swap(int* p1, int* p2)
{int x = *p1;*p1 = *p2;*p2 = x;
}
//选择排序(一次选一个数)
void SelectSort(int* a, int n)
{int i = 0;for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标{int start = i;//记录当前遍历到的元素的下标int min = start;//记录最小元素的下标while (start < n){if (a[start] < a[min])//如果当前元素比最小元素还小min = start;//最小值的下标更新start++;//遍历下一个元素}Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置}
}

3.2直接选择排序的特性总结：

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定

4.堆排序

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

需要注意的是排升序要建大堆，排降序建小堆。

4.1基本思想

我们以升序为例讲讲

堆排序的基本思想是：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一构造堆

将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr的(size-1-1)/2=3/2=1，也就是下面的6结点），从左至右，从下至上进行调整。

3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二

将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

b.重新调整结构，使其继续满足堆定义

c.后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

4.2代码

void Swap(int* p1, int* p2)
{int x = *p1;*p1 = *p2;*p2 = x;
}//堆的向下调整算法
void AdjustDown(int* a, int n, int root)
{int parent = root;int child = 2 * parent + 1;//假设左孩子较大while (child < n){if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在，并且比左孩子大{child++;//左右孩子的较大值}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else//已成堆{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//排升序，建大堆//从第一个非叶子结点开始向下调整，一直到根int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;//记录堆的最后一个数据的下标while (end){Swap(&a[0], &a[end]);//将堆顶的数据和堆的最后一个数据交换AdjustDown(a, end, 0);//对根进行一次向下调整end--;//堆的最后一个数据的下标减一}
}

4.3复杂度分析

1. 时间复杂度：堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度最好和最坏情况下都是O(nlogn)级。

2. 空间复杂度：堆排序不要任何辅助数组，只需要一个辅助变量，所占空间是常数与n无关，所以空间复杂度为O(1)。