【王道数据结构】第八章

8.1. 排序的基本概念

8.2. 插入排序

8.2.1. 直接插入排序

8.2.2. 折半插入排序

8.2.3. 希尔排序

8.3. 交换排序

8.3.1. 冒泡排序

8.3.2. 快速排序

8.4. 选择排序

8.4.1. 简单选择排序

8.4.2. 堆排序

8.5. 归并排序和基数排序

8.5.2. 基数排序

8.1. 排序的基本概念

排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
输入：n个记录 $\small R_{1},R_{2},...,R_{n}$ ，对应的关键字为 $\small R_{1},R_{2},...,R_{n}$ 。
输出:：输入序列的一个重排 $\small R_{1}^{'},R_{2}^{'},...,R_{n}^{'}$ ，使得 $\small k_{1}^{'}\leq k_{2}^{'}\leq ...\leq k_{n}^{'}$ 。
算法的稳定性：若待排序表中有两个元素 $\small R_{1}$ 和 $\small R_{2}$ ，其对应的关键字相同即 $\small key_{i}$ = $\small key_{j}$ ，且在排序前 $\small R_{1}$ 在 $\small R_{2}$ 的前面，若使用某一排序算法排序后， $\small R_{1}$ 仍然在 $\small R_{2}$ 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
- 排序算法的分类：
  内部排序： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
  外部排序： 排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。

8.2. 插入排序

8.2.1. 直接插入排序

算法思想：每次将一个待排序的记录按其关键字大小，插入到前面已经排好序的子序列中，直到全部记录插入完成。

代码实现（不带哨兵）:

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){int i,j,temp;for(i=1; i<n; i++){if(A[i]<A[i-1]){    	//如果A[i]关键字小于前驱temp=A[i];  for(j=i-1; j>=0 && A[j]>temp; --j)A[j+1]=A[j];    //所有大于temp的元素都向后挪A[j+1]=temp;}}
}

代码实现（带哨兵）：

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[], int n){int i,j;for(i=2; i<=n; i++){if(A[i]<A[i-1]){A[0]=A[i];     	//复制为哨兵，A[0]不放元素for(j=i-1; A[0]<A[j]; --j)A[j+1]=A[j];A[j+1]=A[0];}}
}

算法效率分析：
- 时间复杂度：最好情况 O(n)，最差情况O( $n^{2}$ )，平均情况 O( $n^{2}$ )。
- 空间复杂度：O(1)。
- 算法稳定性：稳定。
- 适用性：适用于顺序存储和链式存储的线性表。

对链表进行插入排序代码实现：

//对链表L进行插入排序
void InsertSort(LinkList &L){LNode *p=L->next, *pre;LNode *r=p->next;p->next=NULL;p=r;while(p!=NULL){r=p->next;pre=L;while(pre->next!=NULL && pre->next->data<p->data)pre=pre->next;p->next=pre->next;pre->next=p;p=r;}
}

8.2.2. 折半插入排序

算法思路： 每次将一个待排序的记录按其关键字大小，使用折半查找找到前面子序列中应该插入的位置并插入，直到全部记录插入完成。
注意：为了保证稳定性，当查找到和插入元素关键字一样的元素时，应该在这个元素的右半部分继续查找以确认位置。即当 A[mid] == A[0] 时，应继续在mid所指位置右边寻找插入位置。

代码实现：

//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n){ int i,j,low,high,mid;for(i=2; i<=n; i++){A[0]=A[i];    		     	 //将A[i]暂存到A[0]low=1; high=i-1;while(low<=high){            //折半查找mid=(low+high)/2;if(A[mid]>A[0])high=mid-1;elselow=mid+1;}for(j=i-1; j>high+1; --j)A[j+1]=A[j];A[high+1]=A[0];}
}

与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变。时间复杂度仍为 O(n²)。

8.2.3. 希尔排序

算法思路：先追求表中元素的部分有序，再逐渐逼近全局有序，以减小插入排序算法的时间复杂度。
具体实施：希尔排序:先将待排序表分割成若干形如 $L[i,i+d,i+ed,...,i+kd]$ 的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

希尔排序代码实现：

// 对A[]数组共n个元素进行希尔排序
void ShellSort(ElemType A[], int n){int d,i,j;for(d=n/2; d>=1; d=d/2){  	//步长d递减for(i=d+1; i<=n; ++i){if(A[i]<A[i-d]){A[0]=A[i];		//A[0]做暂存单元，不是哨兵for(j=i-d; j>0 && A[0]<A[j]; j-=d)A[j+d]=A[j];A[j+d]=A[0];}}}
}

算法效率分析：
- 时间复杂度：希尔排序时间复杂度依赖于增量序列的函数。最差情况O( $n^{2}$ )，n在某个特顶范围时可达O( $n^{1.3}$ ) 。
- 空间复杂度：O(1)
- 算法稳定性：不稳定。

8.3. 交换排序

8.3.1. 冒泡排序

算法思路：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A [ i − 1 ] > A [ i ]) ，则交换它们，直到序列比较完。如此重复最多 n-1 次冒泡就能将所有元素排好序。为保证稳定性，关键字相同的元素不交换。

冒泡排序代码实现：

// 交换a和b的值
void swap(int &a, int &b){int temp=a;a=b;b=temp;
}// 对A[]数组共n个元素进行冒泡排序
void BubbleSort(int A[], int n){for(int i=0; i<n-1; i++){bool flag = false; 			//标识本趟冒泡是否发生交换for(int j=n-1; j>i; j--){if(A[j-1]>A[j]){swap(A[j-1],A[j]);flag=true;}}if(flag==false)return;       //若本趟遍历没有发生交换，说明已经有序}
}

算法效率分析：
- 时间复杂度：最好情况O(n) ，最差情况O( $n^{2}$ )，平均情况O( $n^{2}$ )。
- 空间复杂度：O(1)。
- 稳定性：稳定。
- 适用性：冒泡排序可以用于顺序表、链表。

8.3.2. 快速排序

算法思路：在待排序表 L [ 1... n ] 中任选一个元素 pivot 作为枢轴（通常取首元素），通过一趟排序将待排序表分为独立的两部分 L [ 1... k − 1 ] 和 L [ k − 1... n ] 。使得 L [ 1... k − 1 ] 中的所有元素小于 pivot，L [ k − 1... n ]中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L [ k ]上。重复此过程直到每部分内只有一个元素或空为止。
快速排序是所有内部排序算法中性能最优的排序算法。
在快速排序算法中每一趟都会将枢轴元素放到其最终位置上。（可用来判断进行了几趟快速排序）
快速排序可以看作数组中n个元素组织成二叉树，每趟处理的枢轴是二叉树的根节点，递归调用的层数是二叉树的层数。

快速排序代码实现：

// 用第一个元素将数组A[]划分为两个部分
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;
} // 对A[]数组的low到high进行快速排序
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);}
}

算法效率分析：
- 时间复杂度：快速排序的时间复杂度 = O ( n × 递归调用的层数 ) 。最好情况 O( $nlog_{2}n$ ),最差情况 O( $n^{2}$ ) ，平均情况O( $n^{2}$ )。
- 空间复杂度：快速排序的空间复杂度 = O ( 递归调用的层数 ) O(递归调用的层数)O(递归调用的层数)。最好情况O( $nlog_{2}n$ )，最差情况 O(n)，平均情况 O( $n^{2}$ )。

8.4. 选择排序

选择排序思想：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

8.4.1. 简单选择排序

算法思路：每一趟在待排序元素中选取关键字最小的元素与待排序元素中的第一个元素交换位置。

简单选择排序代码实现：

// 交换a和b的值
void swap(int &a, int &b){int temp = a;a = b;b = temp;
}// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n){for(int i=0; i<n-1; i++){          	//一共进行n-1趟，i指向待排序序列中第一个元素int min = i;for(int j=i+1; j<n; j++){		//在A[i...n-1]中选择最小的元素if(A[j]<A[min])min = j;}if(min!=i)                     swap(A[i], A[min]);}
}

算法效率分析：
- 时间复杂度：无论待排序序列有序、逆序还是乱序，都需要进行 n-1 次处理，总共需要对比关键字(n−1)+(n−2)+. . .+1=n( n−1) /2 次，因此时间复杂度始终是O( $n^{2}$ ) 。
- 空间复杂度：O(1) 。
- 稳定性：不稳定。
- 适用性：适用于顺序存储和链式存储的线性表。

对链表进行简单选择排序：

void selectSort(LinkList &L){LNode *h=L,*p,*q,*r,*s;L=NULL;while(h!=NULL){p=s=h; q=r=NULL;while(p!=NULL){if(p->data>s->data){s=p; r=q;}q=p; p=p->next;}if(s==h)h=h->next;elser->next=s->next;s->next=L; L=s;}
}

8.4.2. 堆排序

算法思路：首先将存放在 L [ 1... n ] 中的n个元素建成初始堆，由于堆本身的特点，堆顶元素就是最大值。将堆顶元素与堆底元素交换，这样待排序列的最大元素已经找到了排序后的位置。此时剩下的元素已不满足大根堆的性质，堆被破坏，将堆顶元素下坠使其继续保持大根堆的性质，如此重复直到堆中仅剩一个元素为止。
在顺序存储的完全二叉树中：
- 非终端结点的编号：i ≤ [ n / 2 ]
- i 的左右孩子：2i 和 2i+1
- i 的父节点：[ i / 2 ]

堆排序代码实现：

// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){for(int i=len/2; i>0; i--) 		//从后往前调整所有非终端结点HeadAdjust(A, i, len);
}// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){A[0] = A[k];for(int i=2*k; i<=len; i*=2){	//沿k较大的子结点向下调整if(i<len && A[i]<A[i+1])	i++;if(A[0] >= A[i])break;else{A[k] = A[i];			//将A[i]调整至双亲结点上k=i;					//修改k值，以便继续向下筛选}}A[k] = A[0]
}// 交换a和b的值
void swap(int &a, int &b){int temp = a;a = b;b = temp;
}// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){BuildMaxHeap(A, len);         	//初始建立大根堆for(int i=len; i>1; i--){      	//n-1趟的交换和建堆过程swap(A[i], A[1]);HeadAdjust(A,1,i-1);}
}

算法效率分析：
- 时间复杂度：O( $n\log_{2}n$ )。建堆时间 O(n) ，之后进行 n-1 次向下调整操作，每次调整时间复杂度为O( $\log_{2}n$ )。
- 空间复杂度：O(1)。
- 稳定性：不稳定。
堆的插入：对于大（或小）根堆，要插入的元素放到表尾，然后与父节点对比，若新元素比父节点更大（或小），则将二者互换。新元素就这样一路==“上升”==，直到无法继续上升为止。
堆的删除：被删除的元素用堆底元素替换，然后让该元素不断==“下坠”==，直到无法下坠为止。

8.5. 归并排序和基数排序

归并（Merge）：把两个或多个已经有序的序列合并成一个新的有序表。k路归并每选出一个元素，需对比关键字k-1次。
算法思想：把待排序表看作 n 个有序的长度为1的子表，然后两两合并，得到 ⌈ n / 2 ⌉ 个长度为2或1的有序表……如此重复直到合并成一个长度为n的有序表为止。

代码实现：

// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int 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++){if(B[i]<=B[j])A[k]=B[i++];elseA[k]=B[j++];}while(i<=mid)A[k++]=B[i++];while(j<=high) A[k++]=B[j++];
}// 递归操作
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);     //归并}
}

8.5.2. 基数排序

算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时O ( n ) O(n)O(n)。
收集：把各个队列中的结点依次出队并链接。一趟收集耗时O ( r ) O(r)O(r)。
基数排序擅长处理的问题：
1. 数据元素的关键字可以方便地拆分为d组，且d较小。
2. 每组关键字的取值范围不大，即r较小。
3. 数据元素个数n较大。
算法效率分析：算法效率分析：
1. 时间复杂度：一共进行d趟分配收集，一趟分配需要 O ( n )，一趟收集需要 O(r) ，时间复杂度为 O[ d ( n + r ) ] ，且与序列的初始状态无关.
2. 空间复杂度：O(r)，其中r为辅助队列数量。
3. 稳定性：稳定。

未完待续