新闻动态
技术中心
技术中心
当前位置:科达自控 >> 服务支持 >> 技术中心 >> 浏览文章
几种排序、查找算法的cpp实现
作者:符慧宇 日期:2019年05月05日 来源:本站原创 浏览:

内容导读:1、冒泡排序 // 冒泡排序—从左向右扫描数据,选择最大的数据,放在右边。比较相邻两数,如果左边的数大于右边的数就进行交换

1、冒泡排序
// 冒泡排序—从左向右扫描数据,选择最大的数据,放在右边。比较相邻两数,如果左边的数大于右边的数就进行交换
#include <iostream>
using namespace std;
void BubbleSort(int list[], int n);
int main()
{
int a[] = {2,4,6,8,0,1,3,5,7,9};
BubbleSort(a,10);
for(int i=0; i < 10; i++)
cout << a[i] <<"" ;
return 0;
}
void BubbleSort(int list[], int n)
{
for(int i = 0; i < n ; i++)
// 如果是n 个数,就扫描n-1 次
{
for(int j=0; j< n-i-1; j++)
{
if(list[j] > list[j+1])
std::swap(list[j],list[j+1]);
}
}
}

选择排序
// 要点:选择排序选最小的, 往左边选(找到最小的,放在左边,不需交换);冒泡排序选最大的冒泡:每次都要交换; 选择:扫描完交换一次
#include <iostream>
// 选择排序----将当前未排序的整数中找到一个最小的整数将它放在已排序的列表之后
using namespace std;
void SelectSort(int *a, const int n);
int main()
{
int x[] = {9,8,4,5,2,7,6,3,1,0};
SelectSort(x, 10);
for(int k =0; k < 10; k++)
cout << x[k] <<"";
return 0;
}
void SelectSort(int *a, const int n)
{
for(int i = 0; i < n; i++)
{
int min = i;//min 就是毛巾
for(int j = i+1; j < n; j++)
{ // 注:0~i 之间是排好序的, i~n-1之间是未排序的
if(a[j] < a[min])
min = j;// 与冒泡排序不同
}
swap(a[i],a[min]);
}
}

2、顺序查找
#include <iostream>
using namespace std;
// 没有排序的查找只能是顺序查找。顺序查找比较慢
int SequentialSearch(int *a, const int n, const
int x);
int main()
{
int x[] = {9,8,4,5,2,7,6,3,1,0};
int result;
result = SequentialSearch(x, 10, 0);
if(result == -1)
cout <<"can't find the element!"<<
endl;
else
cout <<"在m["<< result <<"]"<<"找
到了0"<< endl;
return 0;
}
int SequentialSearch(int *a, const int n, const
int x)
{
int i;
for(int i = 0; i < n; i++)
{
if(a[i] == x)
return i;
}
if(i == n)
return -1;
}

3、折半查找
#include <iostream>
// 折半查找--二分查找。数据必须先排序,否则只能顺序查找
using namespace std;
int BinarySearch(int *a, const int x, const int
n);
int main()
{
int x[] = {1,2,3,4,5,6,7,8,9};
int result;
result = BinarySearch(x, 5, 10);
if(result < 0)
cout <<"没找到! "<< endl;
else
cout <<"在x["<<result <<"]找到
"<< 5;
return 0;
}
int BinarySearch(int *a, const int x, const int
n)
{/ /返回值是下标
int low, mid,high;
low = 0, high = n-1;
while(low <= high)
{
mid = (low+high)/2;
if(a[mid] == x)
return mid;
else if(a[mid] < x)
low = mid+1;
else if(a[mid] > x)
high = mid -1;
}
return -1;
}

4、快速排序
#include <iostream>
using namespace std;
// 快速排序运用的是递归算法
template<class Type>
void QuickSort(Type *a, const int left, const
int right)
{
if(left < right)
{
// 选枢轴进行划分
int i=left;
int j=right+1;// 为什么是+1,会使循环条件更简单
int pivot = a[left];
do{
do i++; while(a[i]<pivot);
do j--; while(a[j]>pivot);
if(i<j) swap(a[i], a[j]);
}while(i < j);
swap(a[left], a[j]);
QuickSort(a, left, j-1);
QuickSort(a, j+1, right);
}
// 确定枢轴,找到左边小于枢轴的以及,右边大于枢轴的,交换位置,然后继
续选....
// 直至i(左)≥j(右)停止。然后将左边第一次划分的比枢轴大的进行第二次划分
}
int main()
{
int k[] = {8,6,4,2,0,1,3,5,7,9,99};
QuickSort(k, 0, 9);
for(int i=0; i<10; i++)
cout << k[i] <<"";
cout<< endl;
return 0;
}

 

上一篇文章:基于阿里云的双活灾备方案的设计 下一篇文章:开关电源中“高频磁芯的形状”
相关链接
发表评论
用户评论
版权所有 山西科达自控股份有限公司 晋ICP备09004627号    晋公网安备 14019202000008号     
官方微信
新浪官方微博
腾讯官方微博