排序算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3257字,纯文字阅读大概需要5分钟。
内容图文
![排序算法总结](/upload/InfoBanner/zyjiaocheng/842/8af1bb87e36647a8a99f1d1be9515799.jpg)
1. 冒泡排序
// 朴素冒泡
void bubble_sort_1(int n) {
// 总共需要排序 n-1轮
for(int i=n-1; i>=1; i--) {
for(int j=0; j<i; j++) {
if(s[j] > s[j+1])
swap(s[j], s[j+1]);
}
}
}
// 带优化的冒泡
void bubble_sort_2(int n) {
for(int i=n-1; i>=1; i--) {
// 标记是否有序
bool f = false;
for(int j=0; j<i; j++) {
if(s[j] > s[j+1])
swap(s[j], s[j+1]), f=true;
}
// 说明没有发生交换
if(!f) break;
}
}
2. 快速排序
void quick_sort(int l, int r) {
if(l >= r)
return ;
int i=l, j=r;
int num = s[l];
while(i < j) {
// 从右面找比num小的
while(i < j && s[j] > num) j--;
// 从左面找比num大的
while(i < j && s[i] < num) i++;
// 交换
if(i < j)
swap(s[i], s[j]);
}
quick_sort(l, j-1);
quick_sort(j+1, r);
}
3. 插入排序
void insert_sort(int n) {
// s[0]已经排序排好了
for(int i=1; i<=n-1; i++) {
int j = i-1;
// j+1 即为要插的位置
while(j >= 0 && s[j] > s[i])
j--;
int tmp = s[i];
for(int k=i-1; k>=j+1; k--)
s[k+1] = s[k];
s[j+1] = tmp;
}
return ;
}
// 代码优化版本
void insert_sort(int n) {
// s[0]已经排序排好了
for(int i=1; i<=n-1; i++) {
int j = i-1;
// j+1 即为要插的位置
int tmp = s[i];
while(j >= 0 && s[j] > tmp) {
s[j+1] = s[j];
j--;
}
s[j+1] = tmp;
}
return ;
}
4. 希尔排序
void shell_sort(int n) {
for(int gap = (n>>1); gap; gap>>=1) {
// 共分gap个组
for(int i=0; i<gap; i++) {
for(int j=i+gap; j<n; j+=gap) {
int k = j - gap;
int tmp = s[j];
while(k >= i && s[k] > tmp) {
s[k+gap] = s[k];
k-=gap;
}
s[k+gap] = tmp;
}
}
}
}
5. 选择排序
void select_sort(int n) {
// 共n-1轮次
for(int i=0; i<n; i++) {
int mn_pos = i;
for(int j=i+1; j<n; j++) {
if(s[j] < s[mn_pos]) {
mn_pos = j;
}
}
if(i != mn_pos)
swap(s[mn_pos], s[i]);
}
return ;
}
6. 堆排序
这里比较trick的点就是,就是比如小根堆,根节点是最小的,因此呢,在排序的时候,s[0]和s[n]交换一下,排序结果就是从大到小的。
想要从小到大的排序结果,需要用大根堆。
// 对堆从st调整, 数组元素为n
void heap_down(int st, int n) {
int c = st;
// 有左儿子
while(2*c+1 <= n) {
int l = 2*c+1;
int mn = c;
if(s[mn] > s[l])
mn = l;
if(l+1 <= n && s[mn] > s[l+1])
mn = l+1;
if(mn == c)
break;
swap(s[c], s[mn]);
c = mn;
}
return ;
}
void heap_sort(int n) {
for(int i=n/2; i>=0; i--)
heap_down(i,n);
for(int i=n; i>0; i--) {
swap(s[i], s[0]);
heap_down(0, i-1);
}
return ;
}
7. 归并排序
void merge_sort(int l,int r) {
if(l >= r)
return ;
int mid = (l+r)/2;
merge_sort(l, mid);
merge_sort(mid+1, r);
int l1=l, l2=mid+1;
int k = l;
while(l1 <= mid && l2 <= r) {
if(s[l1] > s[l2])
t[k++] = s[l2++];
else
t[k++] = s[l1++];
}
while(l1 <= mid)
t[k++] = s[l1++];
while(l2 <= r)
t[k++] = s[l2++];
for(int i=l; i<=r; i++)
s[i] = t[i];
return ;
}
8. 分桶排序
void bubble_sort(int n) {
for(int i=0; i<n; i++) {
t[s[i]]++;
}
int k = 0;
for(int i=0; i<N; i++) {
while(t[i]) {
s[k++] = i;
t[i]--;
}
}
return ;
}
9. 基数排序
int get_max(int n) {
int mx = INT_MIN;
for(int i=0; i<n; i++) {
mx = max(mx, s[i]);
}
return mx;
}
// 对数组按照"某个位数"进行排序(桶排序)
void count_sort(int n,int exp) {
int output[n+5];
int bucket[10]={0};
for(int i=0; i<n; i++)
bucket[ (s[i]/exp)%10] ++;
// bucket[i] 现在存.. 当前位数为i的最后一个位置
for(int i=1; i<10; i++)
bucket[i] += bucket[i-1];
// 从后面开始排是因为,每个在后面的数, 总有比他小的,所以在后面的先排
for(int i=n-1; i>=0; i--) {
output[bucket[(s[i]/exp)%10]-1] = s[i];
bucket[(s[i]/exp)%10]--;
}
for(int i=0; i<n; i++)
s[i] = output[i];
}
void radix_sort(int n) {
int mx = get_max(n);
for(int exp=1; mx /exp > 0; exp *= 10) {
count_sort(n,exp);
}
}
参考文章
内容总结
以上是互联网集市为您收集整理的排序算法总结全部内容,希望文章能够帮你解决排序算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。