2.双向冒泡算法，在正反两个方向交替进行扫描，即第一趟把关键字最大的元素放在序列最后，第二趟把关键字最小的元素放在序列最前，如此反复进行。
奇数趟时，从前向后比较相邻元素的关键字，遇到逆序即交换，直到把序列中关键字最大的元素移动到序列尾部。偶数趟时，从后往前比较相邻元素的关键字，遇到逆序即交换，直到把序列中关键字最小的元素移动到序列前端。 void bubblesort(ElemType A[],int n){
int low=0,high=n-1;
bool flag=true; //标记是否交换
while(low<high&&flag){
flag=false;
for(i=low;i<high;i++){
if(a[i]>a[i+1]){
swap(a[i],a[i+1]);
flag=true;
}
high--; //更新上界
}
for(i=high;i>low;i--){
if(a[i]<a[i-1]){
swap(a[i],a[i-1]);
flag=true;
}
low--; //每次冒泡确定一个元素位置
}
}
}
3.已知线性表按顺序存储，且每个元素都是不相同的整数型元素，设计把所有的奇数移动到偶数前面的算法。
可采用基于快速排序的划分思想来设计算法，只需要遍历一次即可，时间On空间O1假设表为L[1..n]从前向后找到一个偶数元素L(i)从后向前找到一个奇数元素L(j)将二者交换，重复过程指导i>j void move(ElemType A[],int len){
int i=0,j=len-1;
while(i<j){
while(i<j&&A[i]%2!=0) i++;
while(i<j&&A[j]%2!=1) j--;
if(i<j){
swap(A[i],A[j]);
i++;j--;
}
}
}
5.编写算法，在数组L[1..n]中找出第k小的元素（即从小到大排序后处于第k个位置的元素）
基于快排的划分操作从数组中选择枢轴pivot，进行快排的划分操作，表被划分为L[1..m-1]L[m+1..n]，其中L(m)=pivot落在哪个区间上就对这个区间递归查找这个元素时间复杂On，空间复杂取决于划分方法
int searchkth(int A[],int low,int high,int k){
int pivot=A[low];
int low_temp=low;
int high_temp=high;
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;
if(low==k) return low;
else if(low>k) return searchkth(a,low_temp,low-1,k);
else return searchkth(a,low+1,high_temp,k-low);
}
7.荷兰国旗问题：设有一个仅由红白蓝三种颜色的条块组成的条块序列，编写时间复杂度On的算法，使这些条块按红白蓝顺序排好。
顺序扫描线性表，将红色交换到最前面，蓝色交换到最后设立三个指针，j为工作指针表示当前扫描的元素，i以前全部为红色，k以后全部为蓝色。根据j所指示元素的颜色，决定将其交换到序列的前部或尾部
typedef enum{
RED;WHITE;BLUE;
}color;
void Flag(color a[],int n){
int i=0,j=0,k=n-1;
while(j<=k){
switch(a[j]){
case RED:swap(a[i],a[j]);i++;j++;break;
case WHITE:j++;break;
case BLUE:swap(a[j],a[k]);k--;
}
}
}
天勤
1、将所有的负数放在正值之前，R[0..n-1]
void Resort(int R[],int n){
int i=0,j=n-1;
int temp;
while(i<j){
while(i<j&&R[i]<0) ++i;
temp=R[i];
while(i<j&&R[j]>0) --j;
R[i++]=R[j];
R[j--]=temp;
}
}
2、对A排序将排序结果存在B里面
void Sort(int A[],int B[],int n){
int i;
for(i=0;i<n;i++) B[A[i]]=A[i];
}
