[数据结构与算法]记录数据结构的学习014

(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）

希尔排序：基于插入排序的优化

思路：让局部有序，减少移动消耗

设置一个增量d，把相距距离为d的元素记为同一个子表。例如d=10时，1，11，21...为一个子表，2，12，22...为一个子表，以此类推。然后对每个子表进行直接插入排序，使其有序。处理完毕后，将增量d缩小，重复上述过程，直到d=1。（若初始d=1，则变为直接插入排序）

常用d的取法：初始为N/2，每次减半，N为元素个数。

希尔排序代码实现：

void ShellSort(int A[],int n){
	int d, i, j;
	for(d=n/2;d>=1;d=d/2){		//增量变化
		for(i=d+1;i<=n;++i){
			if(A[i]<A[i-d]){
				A[0]=A[i];	//A[0]暂存
				for(i=i-d; j>0 && A[0]<A[j]; j=j-d){
					A[j+d]=A[j];
					}	
				A[j+d]=A[0]
				}//进行插入排序
		}
	}
}
		

希尔排序有可能改变相同元素的相对位置，故不稳定。

空间复杂度：O(1)

时间复杂度：最坏情况下与直接插入排序相同，即为 O(n2)，n在某个范围内，可达到 O(n的1.3次方)

希尔排序由于需要利用增量d快速访问，需要有随机存取的特点，故只能适用于顺序表，不能使用于链表

交换排序：冒泡排序、快速排序

冒泡排序：

‘从后往前或者从前往后，依次对比两个元素，若为逆序，则交换它们，直到序列比较完毕，这样称之为一趟冒泡排序。第一趟排序会使得最小的元素达到序列最前方。第二趟就无需对比第一个元素，以此类推，不断进行冒泡排序，直到某一趟不存在任何元素顺序交换，则序列排序成功。

冒泡排序代码实现：

void swap(int &a, int &b){
	int temp=a;
	a=b;
	b=temp;
}//交换函数

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==flase)				//若此躺无交换，表示有序
			return;
		}
}

冒泡排序是稳定的

空间复杂度：O(1)

时间复杂度：

最好情况：有序情况，O(n)

最坏情况：逆序情况，O(n2)

平均时间复杂度 O(n2)

移动次数：每交换一次，要进行三次移动（因为有temp）

冒泡排序每次只需要与下一个元素进行对比，所以适用于链表

快速排序

在待排序列表中，任选一个元素作为枢纽元素（或基准，通常取首位），将其位置空出，并将首尾设置low和high指针。初始情况下，low所指位置是被取出的枢纽元素位置，是空的，此时对比high与枢纽大小，若high指向元素大于枢纽，则不需要移动元素，将high左移，若high指向元素小于枢纽，则将high指向元素置于low所指位置，并将high指向位置空出，当high空出时，将low右移，对比low指向元素于枢纽的大小，若low指向元素小于枢纽，则不需要移动元素，将low右移，若low指向元素大于枢纽，则将low指向元素置于high所指位置，并将low指向位置空出。重复上述操作，直到low于high汇集到同一个位置，此位置即为枢纽元素最终位置。此时枢纽元素将比其大的所有元素和比其小的所有元素划分成了两个子表，再对每个子表进行快速排序。最终当所有子表都low不小于high时，快速排序结束。

用递归实现快速排序：

int Partition(int A[],int low,int high){
	int pivot=A[low];							 //将第一个元素作为枢纽
	while(low<high){							 //用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);		//划分右子表
	}
}

时间复杂度：O(n*递归层数)

空间复杂度：O(递归层数）

递归层数可以转化为二叉树问题，若每次枢纽元素能将左右子表划分为数量均匀的两个子表，则效率最高。

最坏情况：序列原本有序或逆序时，则每次枢纽都划分极不均匀，时间复杂度为O(n2)

最好情况：O(n*log2n)

平均情况：O(n*log2n)

快排不稳定

选择排序：简单选择排序、堆排序

简单选择排序：每趟在待排序列中选取关键字最小或最大的元素加入有序子序列

简单选择排序代码实现

void SeectSort(int A[],int n){
	for(int i=0;i<n-1;i++){			//一共进行n-1趟
		int min=i;					//记录最小元素位置
		for(int j=i+1;j<n;j++)		//在待排序中选择最小的元素
			if(A[j]<A[min]) min=j;	//更新最小元素位置
		if(min!=i) swap(A[i],A[min];//交换
		}
}

void swap(int &a, int &b){
	int temp=a;
	a=b;
	b=temp;
}//交换函数

简单选择排序不稳定

空间复杂度：O(n)

时间复杂度：O(n2)