算法与数据结构（课堂2）

排序与选择

算法排序分类

• 基于比较的排序算法：
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 插入排序
    • 直接插入排序
    • 二分插入排序
    • Shell排序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 合并排序
• 基于数字和地址计算的排序方法
  • 计数排序
  • 桶排序
  • 基数排序

 简单排序算法

        冒泡排序

void sort(Item a[],int l,int r)
{
	for(int i=l+1;i<=r;i++)
	{
		for(int j=i;j>1;j++)
		{
			compswap(a[j-1],a[j]);
		}
	}
}

上述冒泡排序中，待排序元素类型是Item，算法根据Item类型元素的键值对数组元素a[l]~a[r]进行排序。算法中用到关于Item类型变量的一些常用运算：

typedef int Item;	//待排序元素类型
typedef Item* addr;

#define key(A) A
#define less(A,B) (key(A)<key(B))
#define eq(A,B) (!less(A,B) && !less(B,A))
#define swap(A,B) {Item t=A;A=B;B=t;}
#define compswap(A,B) if(less(B,A))swap(A,B)

void ItemShow(Item x)
{
	printf("%d \n",x);
}

其中，less(A,B)比较A和B的键值，等价于key(A)<key(B)；

eq(A,B)等价于key(A)==key(B)；

swap(A,B)交换两个元素的值；

compswap(A,B)等价于语句if(less(A,B)) swap(A,B)，即当key(B)<key(A)时，交换A和B的值

        插入排序算法

 整个过程为n-1趟排序，即先将序列中第一个记录看成是一个有序子序列，然后从第二个记录开始，逐个进行插入，直至整个序列有序。

整个元素插入过程由算法insert来完成

void insert(Item a[],int l,int i)
{
	Item v=a[i];
	while(i>1 && less(v,a[i-1]))
	{
		a[i]=a[i-1];
		i--;
	}
	a[i]=v;
}

//插入排序算法通过反复调用insert来完成排序任务

void sort(Item a[],int l,int r)
{
	for(int i=l+1;i<=r;i++)
		insert(a,l,i);
}

         二分插入排序

用二分查找方法确定插入位置的排序

         希尔排序（缩小增量法）

基本思想：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直到di=1，即所有记录放进一个组中排序为止。

快速排序算法

排序——快速排序（Quick sort）-CSDN博客

typedef int T;
//快速排序算法QuickSort的实现
void QuickSort(T a[], int p, int r)		//p,r都是下标
{
	if (p < r)
	{
		int q = Partition(a, p, r);		//划分
		QuickSort(a, p, q - 1);		//对左端快速排序
		QuickSort(a, q + 1, r);		//对右端快速排序
	}
}	//对a[0:n-1]快速排序只要调用QuickSort(a,0,n-1)

//划分(Partition)的实现
int Partition(T a[], int p, int r)
{
	int i = p;
	int j = r + 1;
	T x = a[p];
	while (true)
	{
		while (a[++i] < x);
		while (a[--j] > x);
		if (i >= j)
			break;
		Swap(a[i], a[j]);
	}
	a[p] = a[j];
	a[j] = x;

	return j;
}

        随机快速排序算法

 在Partition划分的基准值不固定为数组的第一个值，而是随机在a[p:r]中挑选

//随机划分的实现
int RandomizedPartition(T a[], int p, int r)
{
	int i = Random(p, r);
	Swap(a[i], a[p]);
	return Partition(a, p, r);
}

//随机快速排序算法
void RandomizedQuicckSort(T a[], int p, int r)
{
	if (p < r)
	{
		int q = RandomizedPartition(a, p, r);
		RandomizedPartition(a, p, q - 1);
		RandomizedPartition(a, q + 1, r);
	}
}

 合并排序算法（非就地）

数据结构和算法：归并排序（合并排序）详解_合并排序是采用分治策略实现对n个元素进行排序的算法,是分治法的一个典型应用和完-CSDN博客

//非递归版的合并排序算法
void MergeSort(T a[], int n)
{
	T* b = new T[n];
	int s = 1;
	while (s < n)
	{
		MergePass(a, b, s, n);	//合并到数组b
		s += s;
		MergePass(b, a, s, n);	//合并到数组a
		s += s;
	}
}

//需要的函数
//合并x[]中大小为s的相邻子数组到y[]中
void MergePass(T x[], T[y], int s, int n)
{
	int i = 0;
	while (i <= n - 2 * s)
	{
		Merge(x, y, i, i + s - 1, i + 2 * s - 1);
		i = i + 2 * s;
	}
	//剩下的元素个数少于2s
	if (i + s < n)
	{
		Merge(x, y, i, i + s, n - 1);
	}
	else
	{
		for (int j = i; j <= n - 1; j++)
		{
			y[i] = x[i];
		}
	}
}

//有序的合并c[l:m]和c[m+1:r]到d[l:r]
void Merge(T c[], T d[], int l, int m, int r)
{
	int i = l;
	j = m + 1;
	k = l;
	while ((i <= m) && (j <= r))
	{
		if (c[i] <= c[j])
		{
			d[k++] = c[i++];
		}
		else
			d[k++] = c[j++];
	}
	if (i > m)
	{
		for (int q = j; q <= r; q++)
		{
			d[k++] = c[q];		//c[m+1,r]到位
		}
	}
	else
	{
		for (int q = i; q <= m; q++)
		{
			d[k++] = c[q];		//c[l:m]到位
		}
	}
}

特殊有序集的线性时间排序算法   

        计数排序算法 

//算法的实现
void CountingSort(int m,int a[],int n,int b[])
{
	int c[m+1];
	for(int i=0;i<=m;i++)
	{
		c[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		c[a[i]]+=1;
	}
	//c[i]中存放的是a中键值对等于i的元素个数
	for(int i=1;i<=m;i++)
	{
		c[i]+=c[i-1];
	}
	//c[i]中存放的是a中键值对小于或等于i的元素个数
	for(int i=n;i>0;i--)
	{
		b[c[a[i-1]]-1]=a[i-1];
		c[a[i-1]]-=1;		//具有排序的稳定性
	}
}

        桶排序 

基数排序 

        多关键字排序

 中位数与第k小元素

T RandomizeSelect(T a[],int p,int r,int k)
//p,r是下标，要求p<=r，1<=k<=r<=r-p+1
{
	if(p==r)
		return a[p];
	int i=RandomizePartition(a,p,r);
	int j=i-p+1;		//左段的元素个数
	if(k<=j)
		return RandomizeSelect(a,p,i,k);
	else
		return RandomizeSelect(a,i+1,r,k-j);
}
//为在a[0:n-1]中找第k小，只要调用RandomizeSelect(a,0,n-1,k)