数据结构-选择排序

谁践踏了优雅 2022-06-16 09:42 170阅读 0赞

昨天写了数据结构简单排序中的冒泡排序BubblSort：一般来说第一次排序N个数据，有N-1次比较，第二次又N-2次排序........；

总共约N^2/2次比较（最坏的情况下，每次比较都需要交换数据）。由于常数不在大O表示法中所以，时间复杂度为O(N^2.),所以他的速度是很慢的。

选择偶爱徐改进了冒泡排序：将交换次数从O(N^2)变成了O（N），但是比较次数不会变。

**选择排序：**将所有数据扫描一遍找出中最小的数据，让最小的数据和最左端的数据交换，此时最左端的数据就是有序的，然后找出除了最左端之外的的最小值

例子：4,5,1,2,6,3；

第一次 1 5 4 2 6 3

第二次  1 2 4 5 6 3

第三次 1 2 3 5 6 4

第四次 1 2 3 4 6 5

第五次 1 2 3 4 5 6

五次之后排序完成。

**Java代码： **

public class Arr {
    	public static void main(String[] args) {
    		int b[]={6,12,1,16,7,5,1};
    		selectSort(b);
    		for(int i=0;i<b.length;i++){
    			System.out.print(b[i]+" ");
    		}
    	}
    	public static void selectSort(int []b){
    			int temp=0,tem=0;;
    			for(int i=0;i<b.length;i++){
    				temp=b[i];//每次都是将除去左端排序过得元素保存起来
    				tem=i;
    			       for(int j=i+1;j<b.length;j++){
    			    	   if(temp>b[j]){//不断比较最左端没排序的元素，
    			    		  temp=b[j];
    			    		  tem=j;
    			    	   }
    			       }
    			       if(tem!=i){//如果J!=i则进行交换数据
    			    	   b[tem]=b[i];
    			    	   b[i]=temp;
    			       }
    			}
    		
    	}
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关简单选择排序（数据结构）

简单选择排序的算法实现和复杂度分析。

Dear 丶/ 2024年04月23日 20:12/ 0 赞/ 72 阅读

相关【数据结构】选择排序—堆排序

目录一、什么是选择排序？二、堆排序 -------------------- 一、什么是选择排序？ 1. 选择排序的主要思想是每一趟从待排序列中选取

绝地灬酷狼/ 2024年04月03日 10:51/ 0 赞/ 85 阅读

相关【数据结构】选择排序—直接选择排序、树形选择排序

目录一、什么是选择排序？二、直接选择排序三、树形选择排序 -------------------- 一、什么是选择排序？ 1. 选择排序的主要思想是每

叁歲伎倆/ 2024年04月03日 10:43/ 0 赞/ 76 阅读

相关【数据结构】-内部排序(选择排序)

内部排序-选择排序写在前面 1.头文件及类型定义 2.函数声明 3.基本操作 3.1 简单选择排序 3.1.1

落日映苍穹つ/ 2022年11月25日 13:28/ 0 赞/ 191 阅读

相关复习数据结构：排序（三）——选择排序

选择排序的核心是：每趟选择最小的元素和首部交换。时间复杂度：O(n^2)。选择排序是一种不稳定的排序，为什么呢？因为不好处理相等两个数的前后位置，举个例

Myth丶恋晨/ 2022年08月07日 01:53/ 0 赞/ 160 阅读

相关数据结构-选择排序

昨天写了数据结构简单排序中的冒泡排序BubblSort：一般来说第一次排序N个数据，有N-1次比较，第二次又N-2次排序........；总共约N^2/2次比较（最坏的情况

谁践踏了优雅/ 2022年06月16日 09:42/ 0 赞/ 171 阅读

相关数据结构－杂记--选择排序

动态存储空间 `c`语言允许在程序运行时，进行存储空间的分配,这段空间就是系统堆; 通常申请动态内存空间使用的函数是`

清疚/ 2022年06月07日 03:48/ 0 赞/ 180 阅读

相关数据结构 — 选择排序

选择排序选择排序其实算是排序家族当中比较容易理解的排序方法.选择排序的思想最重要的就是这个选择. 你不是要排序嘛. 那么每次在你的所

雨点打透心脏的1/2处/ 2022年06月05日 06:52/ 0 赞/ 179 阅读

相关数据结构(四)选择排序

1、算法流程 (1)首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 (2)然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。 (3

野性酷女/ 2022年06月01日 11:12/ 0 赞/ 156 阅读

相关 C++数据结构--选择排序

\include <stdio.h> typedef int InfoType; \define n 5 //假设的文件长度，即待排序的记录数目 typedef i

野性酷女/ 2022年01月22日 01:05/ 0 赞/ 252 阅读