排序与选择

算法排序分类

• 基于比较的排序算法：
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 插入排序
    • 直接插入排序
    • 二分插入排序
    • 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);	//合并到数组bs += s;MergePass(b, a, s, n);	//合并到数组as += 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;}//剩下的元素个数少于2sif (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++];}elsed[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);elsereturn RandomizeSelect(a,i+1,r,k-j);
}
//为在a[0:n-1]中找第k小，只要调用RandomizeSelect(a,0,n-1,k)