算法从入门到入土cpp版

1. 排序

1. 快速排序

# include<iostream>
using namespace std;const int N = 100010;int q[N];void quick_sort(int q[], int l, int r)
{if(l>=r) return;int i=l-1,j=r+1,temp=q[l];while(i<j){do i++;while(q[i]<temp);do j--;while(q[j]>temp);if(i<j)swap(q[i], q[j]);}quick_sort(q, l, j);quick_sort(q, j+1, r);
}int main()
{int n;scanf("%d", &n);for(int i=0;i<n;i++)scanf("%d", &q[i]);quick_sort(q, 0, n-1);for(int i=0;i<n;i++)printf("%d ", q[i]);return 0;
}

从无序列数组中找有序的第k个数，其实改一下输出就可以了

# include<iostream>
using namespace std;const int N = 100010;int q[N];void quick_sort(int q[], int l, int r)
{if(l>=r) return;int i=l-1,j=r+1,temp=q[l];while(i<j){do i++;while(q[i]<temp);do j--;while(q[j]>temp);if(i<j)swap(q[i], q[j]);}quick_sort(q, l, j);quick_sort(q, j+1, r);
}int main()
{int n;int x;scanf("%d", &n);scanf("%d", &x);for(int i=0;i<n;i++)scanf("%d", &q[i]);quick_sort(q, 0, n-1);printf("%d", q[x-1]);return 0;
}

2. 归并排序

核心：分治-》双指针问题

• 找分界点
• 递归排序左右
• 归并-》合二为一

#include<iostream>using namespace std;
const int N = 100010;void merge_sort(int q[], int l, int r)
{int temp[N]; //辅助数组if(l>=r) return;int mid=(l+r)>>1; //取中间值作为分界点//递归排序左右merge_sort(q, l, mid), merge_sort(q, mid+1, r);int k=0, i=l, j=mid+1;//用辅助数组接收左右两只更小的数while(i<=mid&&j<=r){if(q[i]<=q[j])  temp[k++]=q[i++];else temp[k++]=q[j++];}//当一只先用完，另一只直接挂在temp数组后while(i<=mid) temp[k++]=q[i++];while(j<=r) temp[k++]=q[j++];//将结果从辅助数组转移到原数组for(int i=l,j=0; i<=r; i++,j++)q[i]=temp[j];
}int q[N];
int main()
{int n;scanf("%d", &n);for(int i=0;i<n;i++)    scanf("%d", &q[i]);merge_sort(q, 0, n-1);for(int i=0;i<n;i++)printf("%d ", q[i]);return 0;
}