选择排序 - 数据结构和算法

2019 精帖
0 83

算法思想:

对冒泡排序的一种改进,每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完

算法描述:

用变量i遍历整个数组,用变量j遍历i后面的数组,每次遍历i初始k=i,每次发现a[k]比a[j]大的元素,用k记录其下标,每次遍历完j,比较k和i是否相等,不相等则交换数据,直到i遍历完整个数组完成排序。

public class Test4{
  public static void main(String args[]){
    int a[]=new int[]{1,2,5,4,8,7,1,2,6,5,4,8,9};
    for(int i=0;i<a.length;i++){
      int k=i;
      for(int j=i+1;j<a.length;j++){
        if(a[k]>a[j]){
          k=j;
        }
      }
      if(i!=k){
        int t=a[i];
        a[i]=a[k];
        a[k]=t;
      }
    }
    for(int i=0;i<a.length;i++){
      System.out.print(a[i]+" ");
    }
  }
}
时间空间复杂度

平均时间复杂度:O(n^2)

平均空间复杂度:O(1)

留言(0)
加载更多
猜你喜欢
  • blog 二叉树的遍历-(递归(非递归

    整理 二叉树的遍历-(递归(非递归)-笔记先遍历、中遍历、后续遍历、层级遍历。1.节点信息:package tree;public class Node<E> { private E e;//域 private Node<E
  • blog 递归实现全 c++描述

    递归实现全 c++描述#includeusing namespace std;//交换void exchange(int *a,int i,int j){ if(i==j){ return ;
  • blog -求问题

    问题描述 给定一个int类型一维组 a[],一个int类型的值 b。编写一个程,判断组中有没有两个(a[i],a[j])的等于b,如果存在,返回两个在a组中的下表(return new int[]={1,2}
  • blog 最小生成树Kruskal-

    最小生成树其应用         什么是最小生成树:一个有 n 个点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个点,并且有保持图连通的最少的边。最小生成树可以用krus
  • blog 递归实现合并两递增链表-合并后保持递增

    递归实现合并两递增链表-合并后保持递增列java描述:单链表:递归链表节点package club.test;/*** * 链表节点 * @author jiajia * */public class Node { publi
  • blog 深度优先搜索(dfs、深搜)java实现-

    上一篇:广度优先搜索(bfs、广搜)java实现- 用邻接矩阵表示图的定点之间的关系 如下图 则用邻接矩阵表示为: private static int map[][]={ {0 ,3 ,
  • blog 广度优先搜索(bfs、广搜)java实现-

    广度优先搜索(dfs、深搜)java实现- 用邻接矩阵表示图的定点之间的关系 如下图的: 则用邻接矩阵表示为: private static int map[][]={ {0 ,3 ,6
  • blog -快速

    快速流程--来自百度百科 首先设定一个分界值,通过该分界值将组分成左右两部分。  将大于或等于分界值的集中到组右边,小于分界值的集中到组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素
  • blog 十种理解(前五)

    十种理解(前五)1.冒泡冒泡是一种简单的。它重复地走访过要列,一次比较两个元素,如果它们的顺错误就把它们交换过来。描述:比较相邻的元素。如果第一个比第二个大,就交换它们两个;对每一对相邻元素作同样的工作
  • blog -快速

    百科:快速(Quicksort)是对冒泡的一种改进。 快速由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟将要分割成独立的两部分,其中一部分的所有都比另外一部分的所有