七日算法先导（三）—— 冒泡排序，选择排序

2022 年 8 月 03 日
本文字数：1039 字
阅读完需：约 3 分钟

作业解答

class Solution {    public int[] twoSum(int[] numbers, int target) {        //递减，满足相加之和为target        for (int i = 0, j = numbers.length - 1; i < j;) {            int sum = numbers[i] + numbers[j];            if (sum == target) return new int[] {i + 1, j + 1};            else if (sum > target) j--;//大了，向左移动            else i++;//小了，向右移动        }        return null;    }}

复制代码

双调队列

#include<iostream>using namespace std;int n,a[1001];int main(){    cin>>n;//输入     for(int i=1;i<=n;i++)cin>>a[i];//和输入     sort(a+1,a+n+1);//和排序     for(int i=1;i<=n/2;i++)    {        cout<<a[n-i+1]<<endl<<a[i]<<endl;//和输出     }    if(n%2)cout<<a[n/2+1]<<endl;//和判定 }

复制代码

概念

排序，不同的算法书，有不同的解答，有的叫 10 大排序，有的叫 8 大排序，我们是按照十个来讲，具体可以看下面这篇我早期写的文章：10大排序

冒泡排序

思想：俩俩比较，如果反序交换，直到没有反序的记录为止，代码实现比较简单，是俩个 for 循环的嵌套

#include<iostream>#include<algorithm>//调用算法库，使用交换函数swap#include<cstdio>using namespace std;int main(){  int a[10];  for (int i = 0; i < 10; i++)  {    cin >> a[i];
  }  for (int i = 0; i < 10; i++)  {    for (int j = i + 1; j < 10; j++)    {      if (a[i] < a[j])        swap(a[i], a[j]);    }  }  for (int i = 0; i < 10; i++)  {    printf("%d ", a[i]);  }  return 0;}

复制代码

时间复杂度为 O（n^2)

选择排序

我们发现，从第一个元素到最后一个元素中选择出一个最小的元素，和第一个元素进行交换，然后，从第二个元素到最后一个元素中选择出最小的元素，和第二个元素进行交换，最后，一定可以保证所有元素都是升序排列的

#include<iostream>#include<algorithm>#include<cstdio>using namespace std;int main(){  int a[10];  for (int i = 0; i < 10; i++)  {    cin >> a[i];  }  for (int i = 0; i < 10; i++)  {    int min = i;    for (int j = i + 1; j < 10; j++)    {      if (a[min] > a[j])        min = j;//交换下标位置    }    if (i != min)      swap(a[i], a[min]);  }  for (int i = 0; i < 10; i++)  {    printf("%d ", a[i]);  }  return 0;}

复制代码

刷题巩固

有序数组的平方数组中最大书对和的最小值

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/43832970ead21938be2d0db50】。

秋名山码民

关注

卷不死，就往…… 2021.10.19 加入

2019NOIP退役成员，华为云享专家，阿里云专家博主，csdn博主，努力进行算法分享，有问题欢迎私聊

发布

暂无评论

创作场景

七日算法先导（三）—— 冒泡排序，选择排序

作业解答

概念

冒泡排序

选择排序

刷题巩固

秋名山码民

评论