新聞動態
技術中心
技術中心
當前位置:科達自控 >> 服務支持 >> 技術中心 >> 瀏覽文章
幾種排序、查找算法的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號     
官方微信
胜负彩17059期投注策略
新浪官方微博
騰訊官方微博
中国体育彩票大乐透机选 球探比分网足球即时比 重庆时时彩平台 百人牛牛游戏押注技巧 三公扑克牌手机游戏 炸金花棋牌带二八杠 时时彩信誉平台排名 新疆时时个人计划 老时时360走势图 云南时时购买平台 云南时时奖金表 七星彩包什么爱中奖 pk10最牛稳赚单双大小公式 炸金花百人场什么 时时彩信誉平台排名 双色球今晚直播