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--;}}
}