数据结构学习笔记之——排序

排序

1、插入排序

基本思想：在于每次将一个待排序的记录，按其管家腻子大小插到前面已经排好序的子序列中，直到全部记录插入完成。

1.1、直接插入排序

void InsertSort(ElemType A[],int n){
	int i,j;
	for(i=2;i<=n;i++)	//依次将 A[2]~A[n] 插入到前面已经排好序的序序列
		A[0] = A[i];	//复制为哨兵，A[0] 不存放元素
		for(j=i-1;A[0].key < A[j].key;--j)	//从后往前查找插入位置
			A[j+1] = A[j];	//往后移动
		A[j+1] = A[0];		//复制到插入位置
}
           

1.2、折半插入排序

void InsertSort(ElemType A[],int n){
	int i,j,low,high,mid;
	for(i=2;i<=n;i++){		//依次将 A[2]~A[n] 插入到前面已经排好序的序序列
		A[0]=A[i];		//将 A[i] 暂存到 A[0]
		low=1;high=i-1;		//设置折半查找的范围
		while(low<=high){		//折半查找
			mid=(low+high)/2;
			if(A[mid].key > A[0].key)
				high = mid - 1;
			else
				low = mid + 1;
		}
		for(j=i-1;j>=high+1;--j)
			A[j+1]=A[j];		//统一后移元素
		A[high+1]=A[0];		//插入操作
	}
}
           

折半查找仅仅是减少了比较元素的次数。该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 n；而元素的移动并没有改变，它依赖于待排序表的初始状态。

1.3、希尔排序

void ShellSort(ElemType A[],int n){
//对顺序表作希尔排序，本算法和直接插入排序相比，做了如下修改：
//1.前后记录位置的增量是 dk，不是 1
//2.r[0] 只是暂存单元，不是哨兵，当 j<=0时，插入位置已到
	for(dk=n/2;dk>=1;dk=dk/2)	//步长变化
		for(i=dk+1;i<=n;++i)
			if(A[i].key<A[i-dk].key){	//需要将 A[i] 插入有序增量子表
				A[0]=A[i];		//暂存 A[0]
				for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk)
					A[j+dk]=A[j];		//记录后移，查找插入位置
				A[j+dk]=A[0];		//插入
			}//if
}
           

2、交换排序

2.1、冒泡排序

void BubbleSort(ElemType A[],int n){
	for(i=0;i<n-1;i++){
		flag = false;		//表示本趟冒泡是否发生交换的标志
		for(j=n-1;j>i;j--)		//一趟冒泡排序
			if(A[j-1].key>A[j].key){	//若为逆序
				swap(A[j-1],A[j]);		//交换
				flag = true;
			}
		if(flag == false)
			return;		//本趟遍历后没有发生交换，说明表已经有序
	}
}
           

2.2、快速排序

void QuickSort(ElemType A[],int low,int high){
	if(low<high){
	//Partition()就是划分操作，将表 A[low...high]划分为满足上述条件的两个子表
		int pivotpos = Partition(A,low,high);	//划分
		QuickSort(A,low,pivotpos-1);	//依次对两个子表进行递归排序
		QuickSort(A,pivotpos+1,high);
	}
}
           

int Partition(ElemType A[],int low,int high){
	ElemType pivot = A[low];	//当前表中第一个元素设为枢纽值，对表进行划分
	while(low <= high){		//循环跳出条件
		while(low < high && A[high] >= pivot)
			--high;
		A[low] = A[high];	//将比枢纽值小的元素移动到左端
		while(low < high && A[high] >= A[low])
			++low;
		A[high] = A[low];	//将比枢纽值大的元素移动到右端
	}
	A[low] = pivot;		//枢纽值元素放置的位置
	return low;		//返回存放枢纽值的最终位置
}
           

3、选择排序

3.1、简单选择排序

void SelectSort(ElemType A[],int n){
	for(i=0;i<n-1;i++){		//一共进行 n-1 趟排序
		min = i;		//记录最小元素位置
		for(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]);		//与第 i 个位置交换
	}
}
           

3.2、堆排序

4、归并排序和基数排序

pass

5、各种内部排序的比较

算法种类	时间复杂度	空间复杂度	是否稳定
最好情况	平均情况	最坏情况
直接插入排序	O(n)	O(n2)	O(n2)	O(1)	是
希尔排序
冒泡排序	O(n)	O(n2)	O(n2)	O(1)	是
快速排序	O(nlog2n)	O(nlog2n)	O(n2)	O(log2n)	否
简单选择排序	O(n2)	O(n2)	O(n2)	O(1)	否
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	否
2-路归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	是