|
2.双向冒泡(双向起泡)排序算法：正反两个方向交替扫描(先正)，奇数趟将待排序列的最大元素放在序列最后面，吧偶数趟将待排序列的最小元素放在序列最前面，如此反复，直至序列有序(从小到大)
算法思想：双指针法，控制双向冒泡的待排序列的上下限
void swap(ElemType temp1,ElemType temp2){
ElemType temp = temp1;
temp1 = temp2;
temp2 = temp;
}
void DoubleBubbleSort(ElemType val[],int n){
int low = 0,high = n-1;
bool flag = true;
//待排序列大于1时,flag判断每次循环两趟冒泡是否都发生了元素交换
while(low < high && flag){
flag = false;
//奇数趟冒泡
for(int i = low;i < high;i++){
if(val[i] > val[i+1]){
swap(val[i],val[i+1]);
flag = true;
}
}
high--;//已将最大值有序，待排序列上限减一
//偶数趟冒泡
for(int i = high;i > low;i--){
if(val[i] < val[i-1]){
swap(val[i],val[i-1]);
flag = true;
}
}
low++;//已将最小值有序，待排序列下限加1
}
}
3.顺序表中的元素值各不相同，求将所有奇数移动到所有偶数前面的算法(时间少,空间少)
算法思想：基于快排的划分算法，双指针交换
void swap(ElemType temp1,ElemType temp2){
ElemType temp = temp1;
temp1 = temp2;
temp2 = temp;
}
void exchange_Move(ElemType val[],int n){
int i = 0,j = n-1;
while(i < j){
while(i < j && val[j] % 2 == 0){//从后向前寻找奇数
j--;
}
while(i < j && val[i] % 2 != 0){//从前向后寻找偶数
i++;
}
if(i < j){//交换
swap(val[i],val[j]);
}
}
}
4.重写快速排序中的划分算法，使得每次选取的枢轴元素都是随机从当前子表选取的，而不是待排子表的第一个元素作为枢轴
算法思想：下标取随机数，将随机元素与第一个元素交换并作为枢轴元素，从第二个元素起扫描序列，将比该枢轴元素小的都交换到前面，最后将枢轴元素插入最终位置，使其前面元素都比枢轴元素小，即完成以该随机元素的划分
void swap(ElemType temp1,ElemType temp2){
ElemType temp = temp1;
temp1 = temp2;
temp2 = temp;
}
void QuickSort(int* nums,int low,int high){
if(low < high){
//划分算法
int i = low;
int rand_Index = rand()%(high+low-1);
swap(nums[i],nums[rand_Index]);//将随机元素与第一个元素交换
ElemType pivot = nums[i];//将第一个元素作为枢轴
for(int j = low+1;j <= high;j++){//从第二个元素开始遍历，寻找比枢轴元素小的元素
if(nums[j] < pivot){
i++;
swap(nums[i],nums[j]);//i始终指向当前比枢轴元素小的序列的最后一个元素
}
}
//将枢轴元素与比枢轴元素小序列的最后一个元素交换位置,其枢轴元素位于最终位置
swap(nums[low],nums[i]);
//递归划分左右子序列
QuickSort(nums,low,i-1);
QuickSort(nums.i+1,high);
}
}
5.求在数组[1..n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素)
算法思想：基于快排划分算法,寻找最终位置为k的元素，若此次划分的枢轴元素的位置小于k，则在右子序列继续划分，若大于k，则在其左子序列划分，若等于k，则该枢轴元素即为第k小元素
ElemType Search_min_k(ElemType L[],int low,int high,int k){
//快排划分算法
int i = low,j = high,pivot = L[i];
while(i < j){
while(i < j && L[j] >= pivot){
j--;
}
L[i] = L[j];
while(i < j && L[i] <= pivot){
i++;
}
L[j] = L[i];
}
L[i] = pivot;//将枢轴元素插入最终位置
if(i == k){//若该枢轴元素即为第k小元素，返回该元素
return L[i];
}else if(i < k){//即第k小元素在右子序列中，对右子序列进行划分
Search_min_k(L,i+1,high,k);
}else{//即第k小元素在左子序列中，对左子序列进行划分
Search_min_k(L,low,i-1,k);
}
}
6.荷兰国旗问题:按照红白蓝的顺序排序
算法思想：无话可说，理解浅薄，请求大神指点一二
void swap(color temp1,color temp2){
color temp = temp1;
temp1 = temp2;
temp2 = temp;
}
typedef enum{red,blue,white} color;//枚举
//arr为color型枚举数组,元素为枚举变量其值只能为red,blue,white三个值,n为数组长度
void Flag_Arrange(color arr[],int n){
int i = 0,k = n-1;//i之前的元素只能为red,k后的元素只能为蓝色
int j;//扫描指针
while(j <= k){
switch(arr[j]){
case red:swap(arr[i++],arr[j++]); break;
case white:j++;break;
case blue:swap(arr[j],arr[k]);break;
}
}
}
7.将集合A(有n个元素)分成两个部分A1,A2，使得A1,A2中的元素个数之差n1-n2最小(绝对值)，A1和A2中的元素之和S1-S2之差最大(绝对值)
算法思想：使用快排的划分算法，如果最终枢轴的位置落在n/2处，表示0-n/2-1的元素都小于等于该枢轴元素,n/2-n-1都大等于该枢轴，此时两部分元素个数之差最小,将枢轴元素归为较大的那部分，使得两部分和的差最大
int setPart_sum_min(int arr[],int n){
int low = i = 0,high = j = n-1;
int k = n/2;//目标枢轴位置
int flag = 1;//划分标记
int s1 = 0,s2 = 0;//保存划分成功后的左右子集之和
while(flag){
int pivot = arr[i];//将待划分序列的第一个元素作为枢轴
//快排的划分算法
while(i < j){
while(i < j && arr[j] >= pivot){
j--;
}
arr[i] = arr[j];
while(i < j && arr[i] <= pivot){
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;//将枢轴插入最终位置
if(i == k){//如果该枢轴元素的位置为n/2
flag = 0;//停止划分
}else if(i > k){//如果该枢轴元素的位置大于目标位置,在左子序列上继续划分
i = low;
j = i-1;
}else{//如果该枢轴元素的位置小于目标位置,在右子序列上继续划分
i = i+1;
j = high;
}
}
//累加左右子集和
for(int i = 0;i < n/2;i++){
s1 += arr[i];
}
for(int i = n/2;i < n;i++){
s2 += arr[i];
}
//返回最大差值
return s2-s1;
}
4.在基于单链表表示的待排序关键字序列上进行简单选择排序(从小到大排序)
算法思想：用头插法插入每次找到的待排序序列中的最大元素
void selectSort_Link(LinkList L){//假设L为没有头节点的单链表
LinkLkist head = L;
L = NULL;//作结果链表
while(head){
LinkList p = head,pre = NULL;//遍历指针，寻找待排序列中的最大节点
LinkList maxp = p,maxpre = pre;//指向每趟遍历的最大节点及前驱，以便删除
while(p){
if(p->val > maxp->val){
maxp = p;
maxpre = pre;
}
pre = p;
p = p->next;
}
if(maxp == head){//若该趟遍历的最大节点为当前链表第一个节点，头指针向后移，删除该节点
head = head->next;
}else{//最大节点在链表内部，从当前链表中删除该节点
maxpre->next = maxp->next;
}
//将该节点插入结果链表中
maxp->next = L;
L = maxp;
}
}
5.判断一个数据序列是否构成一个小根堆
算法思想：从最后一个非叶节点起开始判断每个非叶节点是否比最小孩子节点小
bool isSmallHead(ElemType val[],int n){//顺序存储，从下标1开始存储数据
for(int i = n/2;i > 0;i--){//从最后一个非叶节点起开始遍历
int j = 2*i;//非叶节点的左孩子下标
//判断最后一个节点是否有右孩子，且判断非叶节点的左右孩子大小
if(j < n && val[j] > val[j+1]){
j++;//右孩子小
}
if(val[i] > val[j]){//如果非叶节点比最小的孩子节点大
return false;//不是小根堆
}
}
return true;
}
2.顺序表用数组存储，表中元素存储在1-m+n的范围中，前m个元素递增有序，后n个元素递增有序，设计算法使整个顺序表有序
算法思想：将前m个元素看作进行了m-1趟直接插入排序后形成的有序序列，再对后n个元素进行n趟直接插入排序使序列整体有序
void Direct_Insert_Sort(ElemType val[],int m,int n){
for(int i = m+1;i <= m+n;i++){//i始终指向无序序列中的第一个元素
ElemType val[0] = val[i];
for(int j = i-1;val[j] > val[0];j--){//在有序序列中寻找该元素的插入位置
val[j+1] = val[j];
}
val[j+1] = val[0];//插入该元素使序列有序
}
}
3.计数排序：待排序列用数组存储，元素值各不相同，对于每个记录，扫描待排序序列一趟，记下比该记录小的数的个数，然后将该数放在下标为该个数的另一个数组中
算法思想:数组中任意两个数之间只比较一次,遍历当前元素的后面元素进行比较，统计数组中比当前元素小的元素个数
typedef struct{//给数组中每个数都添加一个count表示数组中比该值小的元素的个数
ElmeType key;
int count;
}Array;
void countSort(Array val[],ElemType arr[],int n){
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
//当有重复元素时,使其排序结果稳定(在初始序列后的重复元素在新数组中的下标大)
if(val[i] <= val[j]){
val[j].count++;
}else{
val[i].count++;
}
}
arr[val[i].count] = val[i].key;
}
}
4.数组中存放了无序序列K1K2...Kn,(从下标开始存储)现要求将Kn放在排序后的最终位置上(要求比较关键字的次数不超过n)
算法思想：以Kn为枢轴使用一趟快速排序,先从前向后扫描，再从后向前扫描
int Partition(ElemType val[],int n){
int i = 1,j = n;
ElemType temp = val[n];//以Kn为枢轴
while(i < j){
while(i < j && val[i] <= temp) i++;
if(i < j){
val[j] = val[i];
}
while(i < j && val[i] >= temp) j--;
if(i < j){
val[i] = val[j];
}
}
val[i] = temp;
return i;
}
|