首页 > 其他分享 >选择排序

选择排序

时间:2024-11-10 20:09:25浏览次数:3  
标签:int 复杂度 选择 ++ zz 排序 降序

选择排序的排序方法

通过 \(2\) 重循环遍历数组,发现有不符合顺序的数对,就交换他们.

时间复杂度

选择排序的最好时间复杂度: \(\Theta (n^2).\)

选择排序的平均时间复杂度: \(\Theta (n^2).\)

选择排序的最坏时间复杂度: \(\Theta (n^2).\)

稳定性

选择排序是不稳定的排序算法.

示例代码

这里以降序为例.

//降序 
#include <iostream>
#include <algorithm> // 调用 swap 函数 
using namespace std;
int a[310], n;
int main() {
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) { // a[i]与它之后的每一个数字比较 
			if(a[i] > a[j]) // 不是降序的数对 
				swap(a[i], a[j]); // 交换 
		}
	}
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
	return 0;
}

优化

因为我们每次都是都在交换,所以,我们可以找在 \(a_i\) 后面最小的数,进行交换. ( \(1 \le i \le n\) ).

\(n\) 为数组大小.

优化代码

//降序 
#include <iostream>
#include <algorithm>
using namespace std;
int a[310], n, zz; // zz-指针 指向一个位置 
int main() {
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++) { // 从数组开头循环到 n-2,等价于 i<n-1 
		zz = i; // 指针的位置先指向 i 
		for(int j = i + 1; j < n; j++) { // a[i]与它之后的每一个数字比较 
			if(a[zz] > a[j]) zz = j; // 若找到了比当前数字更小的数,zz指向这个更小的数的位置 
		}
		if(zz != i) swap(a[i], a[zz]); // 如果zz的位置有改动,交换a[i]和最小数 
	}
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
	return 0;
}

标签:int,复杂度,选择,++,zz,排序,降序
From: https://www.cnblogs.com/panda-lyl/p/18538395

相关文章

  • 成分喵 1.3.1 | 功能强大的成分查询软件,纯净无广,帮助选择更健康的产品
    成分喵是一款强大的商品成分查询软件,支持查询食品、化妆品等物品的成分。软件纯净无广告,支持iOS和安卓双端使用。用户可以通过拍照、扫码和链接三种方式一键查询商品的成分。成分喵内置了庞大的成分数据库,可以查看成分介绍、风险评估以及作用,帮助用户精准选择健康的产品。......
  • 如果你搞不懂排序,看这篇文章就对了,初学者也看得懂,其三:进阶插入排序——希尔排序
    目录一.希尔排序1.1希尔排序的原理1.2希尔排序的代码思路1.3希尔排序的代码实现1.1希尔排序的原理希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重......
  • 通过官网下载Qt以及安装选择
    Qt是一个跨平台的应用开发框架,广泛用于桌面、移动、嵌入式和物联网应用的开发。它的主要作用包括:①跨平台支持:编写一次代码,可以在Windows、macOS、Linux、Android和iOS等多个平台上运行。②丰富的GUI组件:提供多种UI组件和工具,帮助快速构建现代化的用户界面。③扩展性......
  • 冒泡排序(详细讲解)
    对于冒泡排序,字面理解就是对一段数据进行排序比如说你有10个数据intarr[10]={3,1,7,5,8,9,0,2,4,6};你想对这些数据进行从小到大的排序,一个个用if和else去进行比较太麻烦了,所以这时候冒泡排序就可以帮你提高效率首先,先文字讲解,这里总共有十个数据,而我们每次排序都会将......
  • 排序算法原理、应用与对比
    一、排序算法综述排序算法在计算机科学中具有至关重要的地位。在众多应用场景中,如数据库管理、搜索引擎结果排序、数据分析等,高效的排序算法能够极大地提高系统的性能和用户体验。不同类型的排序算法具有各自独特的特点和分类。从算法的稳定性来看,有些算法是稳定的,如插入排序......
  • DICOM图像知识:DICOM图像排序与坐标系解析
    目录引言1.概述2.DICOM图像排序规则2.1Patient的Study按StudyDate排序2.2Study的Series按SeriesNumber排序2.3Series的SOP按InstanceNumber或SliceLocation排序2.3.1InstanceNumber排序2.3.2SliceLocation排序2.3.3使用ImagePosition(Patient)和Image......
  • 桶排序 选择,插入排序
    (2)选择排序:基本思想:从数组的未排序区域选出一个最小的元素,把它与数组中的第一个元素交换位置;然后再从剩下的未排序区域中选出一个最小的元素,把它与数组中的第二个元素交换位置。重复上述过程,直到数组中的所有元素按升序排列完成。【案例】对一维数组中的十个数据进行从小到大排......
  • 桶排序2
    #include<iostream>#include<bits/stdc++.h>usingnamespacestd;/*桶排序思想:把每个数组开辟的空间看作一个桶,将与桶编号相同的数据存入桶中13579864210数据b[]开辟桶的个数大于数据最大值第一步:桶内初始化为0第二步:判断数据存入桶中a[11]a[0].........
  • 【VBA实战】用Excel制作排序算法动画续
    为什么会产生用excel来制作排序算法动画的念头,参见【VBA实战】用Excel制作排序算法动画一文。这篇文章贴出我所制作的所有排序算法动画效果和源码,供大家参考。冒泡排序:插入排序:选择排序:快速排序:归并排序:堆排序:希尔排序:完整源码如下。OptionExplicitPublichm......
  • 计算机专业的未来: 2025年,你该如何选择?
    计算机专业的未来:2025年,你该如何选择?在即将到来的2025年,关于计算机专业的选择变得愈发复杂。这个领域吸引了无数年轻人的目光,但你是否真的知道选择计算机专业的月光与阴影?本文将深入探讨计算机专业的现状、斯坦福大学的计算机科学分析,以及国有企业的就业前景,帮助你做出明......