7-内部排序算法

插入排序

插入排序就是每次都从后面未排序的序列中按照大小插入到前面已经排好的子序列中，这里会产生子序列（已经排好序的）和待排序列，当没有待排序则算法结束，每次从未排序的头部取出一个插入到子序列中合适的位置。包含有：直接插入、折半插入、希尔排序。

直接插入

L[1.......i-1]	L[i]	L[i+1......n]

如上模拟插入排序状态，此时待排序指针指向i，前面i-1项是已经排序好的子序列，后面的i~~n是待排序的，是可以很容易想到解决方法就是在1~~i-1中找到适合L[i]的位置即可，因为前面已经是排好序的，找到合适的位置插入后，子序列长度变为1~i。每次都从未排好序的中取出第一个进行插入，此处需要和后面的选择排序进行区分，当执行所以待插入的都执行完毕则算是排好啦。

初始第一个值默认自成一个已经排好序的子序列
采用哨兵复制L[i]，然后将子序列中大于L[i]的值进行后移，因为已经找到位置，要插入就得有空位嘛
给L[i]找到合适的插入位置
将腾出的空位放入L[i]
继续循环

弄清楚算法思想，代码是比较容易实现的，算法核心在于，从初始子序列为1的数组中，指针依次后移，为当前指向的值，从子序列中找到一个合适的位置，然后插入即可，此处可能会有疑问，插入到前面，那当前的位置呢？因为会要进行移动，所以此处的位置必然也是一个已经排好序的值。 1）代码

void InsertSort(int a[],int len){
    int i,j;
    for(i = 2;i <= len;i++){
        if(a[i]<a[i-1]){
        	a[0] = a[i];
            for(j = i - 1;a[0] < a[j];--j){
            	a[j+1] = a[j];
            }
            a[j+1] = a[0];
        }
    }
}

2）时空复杂度分析

空间上只使用了a[0]当哨兵作为辅助，故空间复杂度上为 $O(1)$
最优时间复杂度，如果已经有序，一趟循环即可，时间复杂度为 $O(n)$
最坏时间复杂度，初始全部乱序，两个for循环，时间复杂度为 $O(n^2)$

3）稳定性分析

这里第一次提及稳定性，所谓稳定性是指，数组中有a[i] == a[j]，其中i<j，理论上正常人工排序会将a[i]排在a[j]前面，假若这里反过来，就是不稳定的。如果值相同的元素在排序后相对位置没有发生改变则认为是稳定的。

据此分析，直接插入排序每次都是从未排序的数组中取出第一个进行插入，循环条件为小于号，故不会出现同值元素出现相对位置改变的情况，由此是稳定的。同时适用于顺序和链式两种结构。

折半插入

折半插入是对直接插入的一个改进。在直接插入中可以发现，每次都会从子序列开头去查找一个合适插入的位置，这会带来一定的时间消耗，折半插入的改进就在于查找使用了折半查找，二分查找找到合适的位置，然后一次性进行移动。如下图就是算法模拟步骤。默认第一个元素自成一个子序列，此时待排序指针指向5，将5复制到的哨兵中，因为子序列中只有一个8，所以mid、low、high都指向8，当拿8和哨兵比较后，发现哨兵更小，high指针左移，终止循环，也就是找到了合适的位置了，此时会将右子序列右移，其实也就是将8右移一个单位，如下所示，最后将哨兵存储的复制值放到合适的位置即可。

折半查找子序列找到合适的位置
右移元素
将哨兵元素插入

1）代码

void InsertSortPlus(int a[],int len){
	int i,j,low,high,mid;
    for(i = 2;i <= len;i++){
    	a[0] = a[i];
        low = 1;high = i - 1;
        while(low<=high){
        	mid = (low + high) / 2;
            if(a[mid] > a[0]) low = mid + 1;
            else high = mid - 1;
        }
        for(j = i - 1;j >= high + 1;j--){
            a[j + 1] = a[j];
        }
        a[high + 1] = a[0];
    }
}

2）时空复杂度 与直接插入排序是一样的。

空间复杂度上 $O(1)$
时间复杂度为 $O(n^2)$

3）稳定性 这是稳定的排序算法，不会改变同大小元素的相对位置，该算法依赖初始状态，在初始相对有序且数据量不大的情况下，表现不错。

希尔排序

缩小增量排序，具体思想是按照一个增量将排序表分割成若干小组，小组内部进行直接插入排序。一趟完毕后增量减小，继续分组，然后进行内部的直接插入排序。知道增量为1，最后是一次完整的直接插入排序。这样的好处是，让值更大的更快跑到后面，值更小的更快到前面，在数据量大的时候，较为优秀。

信息

确定初始增量，这里随便写n/2，然后对排序表按照增量分组
各组内进行一趟插入排序
增量缩小，n/2
重复步骤2，知道增量变成1

1）代码

void ShellSort(int a[],int len){
    int gap,i,j; //分别定义增量和两个循环变量
    for(gap = len/2;gap>=1;gap = gap/2){ //增量减小
        for(i = gap+1;i<=n;i++){    //gap+1是因为从a[1]开始，这里i++而不是按分组进行循环，个人理解是，指针向前走，后面的j会控制gap，所以会在后面进行组内的排序(这里思考了挺久，看后面的pic辅助理解)
            if(a[i] < a[i-gap]){ //组内前一个元素大
                a[0] = a[i];  //哨兵
                for(j = i-gap;j>0 && a[0]<a[j];j -= gap)
                    a[j+gap] = a[j];
                a[j+gap] = a[0]; 
            }
        }
    }
}

这里随便拿两个图来看下希尔排序中i指针，在前移的过程都会进行一次组内排序。不是我们手工算的一次就直接把组内给排好的。这里看出来49-27-76-65是一组的，此时i=3，j=1，所以要进行插入排序。完了之后指针i向前走到4，切换到另一个组此时对另一个组进行排序。i++后指向5，对前一个组进行排序，只不过前一个表是27-49，这次变成了27-49-76，依次类推，当i为7的时候，组内元素齐整了。 2）时空复杂度、稳定性

空间只用了一个哨兵，为 $O(1)$
时间复杂度在数学上未能解决，分析没有结果，只知道n在某个范围的时候，时间复杂度为 $O(n^{1.3})$ ，最坏情况是 $O(n^2)$
不稳定，且只适用于顺序表

交换排序

根据序列中两个元素的比较结果来交换两者的位置，所以叫交换排序。两种算法：冒泡和排序，冒泡随便，快排重点，算法题爱考

冒泡排序

直接看图理解：每次都把最小（大）的冒上去 1）代码

void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}
void BubbleSort(int a[],int len){
    bool = flag = false;
    for(int i = 0;i<n-1;i++){
        for(int j = n-1;j>i;j--){
            if(a[j] < a[i]) //这里的小于是确保稳定性的
                swap(a[j],a[i]);flag = true;
        }
        if(!flag)return ;
    }
}

2）时空复杂度、稳定性

空间复杂度为 $O(1)$
最好情况下，本来就有序 $O(n)$ ，否则则进行n-1躺排序，第i躺排序要进行n-i次比较，则比较次数为 $\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}$ ,为 $O(n^2)$ ，其中每次都要移动元素三次，总移动次数为比较次数的三倍
稳定

快速排序

1）分而治之 快排的基本思想是分治，一个待排序表L[1....n]中取一个枢轴值pivot（一般第一个），通过一次排序使得L分为两块：L[1....k-1]和L[k+1...n]，其中L[k]为pivot，使得左边表的值都小于pivot，右边都大于。然后分别再对这两个表执行上面的操作。直到每个部分只有一个元素。 2）交换 知道了分治排序，那么如何高效的将表一分为二呢？使用两个指针low和high，分别指向头和尾，一开始low=0，也就是pivot的位置，先假设给这里挖了。那么需要填坑，所以第一步就是high先向前移动去找元素填坑。我理解为low和j谁有坑，另一个就得去找元素填坑。按照下面的步骤执行交换若此时指针low的位置有坑：

high向前移动，直到遇到第一个比pivot小的元素
将high位置的元素拿走（挖坑），去填low
同时low++

若此时指针j的位置有坑：

low向后移动，直到遇到第一个比pivot大的元素
将low位置的元素拿走，填high
同时high--

3）代码 理解了分治和交换，代码如下：先看交换部分的：

int Partition(int a[],int low,int high){
    int pivot = a[low];
    while(low < high){
        while(low<high && a[high]>=pivot) --high;  //后面找元素填前面
        a[low] = a[high];
        while(low<high && a[low]<=pivot) ++low;  //前面找元素填后面
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

快排：

void QuickSort(int a[],int low,int high){
    if(low < high){
        int pivotpos = Partition(a,low,high);//找到第一次的枢轴值点
        QuickSort(a,low,pivotpos - 1); //左排序
        QuickSort(a,pivotpos + 1,high); //右排序
    }
}

3）时空复杂度、稳定性

算法是递归的，需要一个递归栈开销，容量和递归调用的最大深度一致。最好情况下位 $O(log_{2}n)$ ，最坏需要 $n-1次递归调用，所以栈为O(n)$ ，平均是 $O(log_{2}n)$
最坏请跨国下的时间复杂度为 $O(n^2)$ ，理想情况是 $O(nlong_{2}n)$
不稳定
所有内部排序中平均性能最优

选择排序

每一趟选择从待排序的元素中选取最小（大）的作为有序序列的第i个元素。分选择排序和堆排序，堆排序是重点。

简单选择

跟插入排序是挺类似的，都是从待排序的序列中拿一个元素放到前面去。但是要进行区分的是，插入排序是，i指到哪里就将i的元素插入到有序序列中合适的位置，同时后移位置，这里的a[i]在序列中的排序是位置的，是在一次次的插入过程中，移动到它应在的位置。简单选择是每次从待排序的序列中找到最小的，和当前i指向的位置元素进行交换。

此时38和27进行交换（因为27最小）按照这样执行n-1次即可

当前指向a[i]，则从a[i.....n-1]中寻找最小的元素a[k]
交换a[k]和a[i]
待排指针i前移（i++），重复上述操作

1）代码

void SelectSort(int a[],int len){
    for(int i = 0;i<n-1;i++){
        int min = i;
        for(int j = i+1;j<n;j++){
            if(a[j]<a[min])
                min = j;
        }
        if(i!=min)
            swap(a[i],a[min]);
    }
}

2）时空复杂度分析

没有借助辅助空间，空间复杂度为 $O(1)$
每次进行三个元素的移动，一共n-1躺，一共移动3(n-1)次元素
元素的比较次数和初始状态没有关系一共进行 $\frac{n(n-1)}{2}$ ，故时间复杂度为 $O(n^2)$
不稳定

堆排序

1）堆 将堆看成一棵完全二叉树，其中二叉树满足性质：任意一个非根节点都小（大）于其根节点。简单来说就是每个根，存放的是该根为根节点的树中最大（小）的值。其中根最大的叫大根堆，最小的叫小根堆。如下是一个大根堆： 2）如何造堆： 这里说的是大根堆的，小根堆跟大根堆差不多。

先将数据表表示成完全二叉树的格式
最树的最后一棵子树开始，从后往前调整

3）处理上升和下坠：

若当前处理的根节点的小于左右孩子中的最大值，那么最大值会替换根节点的值，同时让根节点下坠
根节点下坠的过程，从上往下进行继续进行上述的操作1，如果有比自己还大的孩子，就下坠，直到找到合适的位置

这里贴几个图：初始处理倒数第一棵子树处理可能要下坠的情况，这里处理到了最后一棵树，53＜87，所以要下坠 53下坠到原87的位置，发现这棵子树不符合，所以继续下坠。 53放到了合适的位置，大根堆构建结束。

4）造堆的代码 先来看一下树中儿子和父亲的关系函数： $\begin{aligned} & 1.若i为偶数则双亲为\frac{i}{2}向下取整 \\ & 2.若i为奇数则双亲为\frac{(i-1)}{2} \\ & 3.2i \le n时，i的左孩子是2i \\ & 4.2i+1 \le n时，i的右孩��子是2i+1 \\ \end{aligned}$ 其中要注意的是数组a是从0开始存储还是1开始存储，对应的表达式会有改变。要点：

若表长为len，那么第一棵子树的根节点下表为len/2，从这里开始调整
若根节点需要下坠，把最大值放到根节点位置
根节点下坠到缺空处，此时需要调整指针标记值，去判断下坠位置时候符合大根堆的条件

void BuildMaxHeap(int a[],int len){
    for(int i = len/2;i>0;i++)  //第一棵子树的根节点下表为len/2，从这里开始调整
        HeadAdjust(a,i,len);
}
void HeadAdjust(int a[],int k,int len){
    a[0] = a[k];	//复制一份当前处理节点数据，后面交换后会被覆盖
    for(int i = k*2;i<len;i*=2){   //k*2直接指向其左孩子，每次循环开始都会向下走一层
        if(i<len && a[i]<a[i+1])	
            i++;		//i标记的是左右孩子哪个更大
        if(a[0]>a[i])break;	//根最大，满足，不处理
        else{
            a[k] = a[i];	//根小孩子大，孩子上去
            k = i;			//将根的指针指向这个孩子的，重新循环判断寻找初始根应该放的位置
        }
	}
    a[k] = a[0]			
}

5）堆排序 已经造好了大根堆

输出堆顶元素（堆定元素和堆底元素在完全二叉树的逻辑上进行互换）
调整大根堆
循环1和2

void HeapSort(int a[],int len){
    BuildMaxHeap(a,len);
    for(int i = len;i>n;i--){
        swap(a[i],a[1]);
        HeadAdjust(a,1,i-1);
    }
}

6）时空复杂度、稳定性

空间上借助常数个空间单元 $O(1)$
建堆时间 $O(n)$ 调整时间为 $O(h)$ ，最好、最坏、平均情况下的时间复杂度都是 $O(nlog_{2}n)$
不稳定

归并排序和基数排序

归并排序

将两个（或多个，取决于归并路数）有序表，合并成一个新的有序表，看个图理解：以上是二路归并，初始每个元素独立为一个有序表，则取两两合并，如有剩下不成组则单独为一组，n路归并同理。直到归并成一个完整的有序表。 1）归并 如何合并两个有序表长度分别问n和m

需要一个辅助数组b存放两个表
两个指针p1和p2分别指向两个有序表的起始位置
比较b[p1]和b[p2]，较小者放入a中，同时指针后移
当出现某一个表已经复制完了，剩下的表直接将剩余元素按序复制到a中

图例：这是初始状态。复制元素，指针后移，继续比较。当一个表复制完了，剩下的直接复制进去。

3）归并代码

int *b = (int *)malloc(sizeof(int)*(n+1)); // 辅助数组
void Merge(int a[],int low,int mid,int high){  //mid是两个有序表相隔的位置,a[low~mid]和a[mid+1~high]
    int i,j,k;
    for(k = low;k<=high;k++) //复制元素
        b[k] = a[k];
    for(i = low,j = mid+1,k = i;i<=mid && j<=high;k++){  //i做前段指针，j做后段指针  
        if(b[i]<=b[j])
            a[k] = b[i++];
        else
            a[k] = b[j++];
    }
    //两种情况复制剩下的
    while(i<=mid)
        a[k++] = b[i++];
    while(j<=high)
        a[k++] = b[j++];
}

4）n路归并排序 这里以2路归并，基于分治思想，将n个元素分解成n/2个子表，两两归并。几路就按几个元素一组来划分。

void MergeSort(int a[],int low,int high){
    if(low<high){
        int mid = (low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}

5）时空复杂度、稳定性

需要n个辅助单元，空间复杂度 $O(n)$
每趟归并的复杂度为 $O(n)$ ，二路需要 $log_{2}n$ ，时间复杂度为 $O(nlog_{2}n)$
稳定

基数排序

基数排序不基于比较和移动进行排序，按照关键字各个位置的大小进行比较。如果按0999的数来比较，个人理解为，分别按个十百或者百个十进行比较。有两种关键字排序法： **最高位优先：**从高位开始排序 **最低位优先：**从低位开始排序 1）举个🌰： 有520，211，438,888,007,111,985,666,996，233,168。每个位置都是09的数，我们说其基数r=10。每个数的范围在0~999中，个十百各排序一次，需要三次。基于上述的顺序，进行个位的分配，如下第一趟：接下来将各个队列的值串起来（收集），从前往后：接下来，基于这个顺序进行百位的分配和收集：

最后进行百位的分配和收集：

2）具体过程 感觉通过上面的例子都会理解了，这里还是按过程随便写一下。给定长度n的线性表，每个结点 $a_j$ 的关键字由d元组 $(k_j^{d-1},k_j^{d-2},k_j^{d-3}......k_j^{0})$ 组成其中， $0 \le k_j^{i} \le r-1 (0 \le j \le n,0 \le i \le d-1)$ ，r称为基数有点难说，简单认为就是，一个关键字有多少位就是几元组，关键字中的任意一位的取值范围最大值就是基数r。上述的520就是三元组，基数。基数排序得到递减序列的过程：

设置r个空队列 $Q_r,Q_{r-1}.......Q_0$
按各个关键字位权重递增次序，就是个十百的顺序，对关键字分配和回收
分配：如果当前处理的关键字位是n就挂到队列n的队尾中，比如520的个位是0，就挂0队列
回收：从前到后将队列元素出队，串起来

3）时空复杂度、稳定性

空间需要r个队列， $Q(r)$
需要进行d躺排序，一次分配要 $Q(n)$ ，一次收集要 $Q(r)$ ，所以时间复杂度为 $O(d(n+1))$
稳定

4）应用 基本不考大题，了解手算，一般适用于那种有关键字的比较，年月日、身份证这种。

内部排序算法总结

算法	时间复杂度			空间复杂度	稳定性
	最好	最坏	平均
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳
折半插入	$O(nlog_{2}n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳
希尔	\	\	$O(n^2)$	$O(1)$	不稳
冒泡	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳
快排	$O(nlog_{2}n)$	$O(nlog_{2}n)$	$O(n^2)$	$O(log_{2}n)$	不稳
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳
堆	$O(nlog_{2}n)$	$O(nlog_{2}n)$	$O(nlog_{2}n)$	$O(1)$	不稳
2路归并	$O(nlog_{2}n)$	$O(nlog_{2}n)$	$O(nlog_{2}n)$	$O(n)$	稳
基数	$O(d(r+1))$	$O(d(r+1))$	$O(d(r+1))$	$O(r)$	稳

四种不稳定情况

1）希尔 2）快排 3）简单选择 4）堆

与数据结构的适用性

顺序表结构
直接插入、折半插入、希尔、冒泡、快排、简单选择、堆、归并、基数

链表结构
直接插入、冒泡、简单选择、基数（可能降低效率）；（快排、希尔、归并、堆都可以用，但是不推荐）

插入排序​

直接插入​

折半插入​

希尔排序​

交换排序​

冒泡排序​

快速排序​

选择排序​

简单选择​

堆排序​

归并排序和基数排序​

归并排序​

基数排序​

内部排序算法总结​

四种不稳定情况​

与数据结构的适用性​

插入排序

直接插入

折半插入

希尔排序

交换排序

冒泡排序

快速排序

选择排序

简单选择

堆排序

归并排序和基数排序

归并排序

基数排序

内部排序算法总结

四种不稳定情况

与数据结构的适用性