简单选择排序 订阅
简单选择排序是一种排序算法,指在简单选择排序过程中,所需移动记录的次数比较少。 展开全文
简单选择排序是一种排序算法,指在简单选择排序过程中,所需移动记录的次数比较少。
信息
定    义
排序算法 数据结构
分    类
数据结构
中文名
简单选择排序
外文名
Select Sort
简单选择排序基本概念
最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最小,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n)。简单选择排序是不稳定排序。
收起全文
精华内容
下载资源
问答
  • 简单选择排序

    万次阅读 多人点赞 2019-03-05 17:09:49
    文章目录简单选择排序的工作原理时间复杂度分析案例分析代码实现 简单选择排序的工作原理 选择排序(Selection sort)是一种简单直观的排序算法。 它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序...

    简单选择排序的工作原理

    选择排序(Selection sort)是一种简单直观的排序算法。

    它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n个元素的表进行排序总共进行至多 n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

    维基百科的例子如下图:

    image

    时间复杂度分析

    当i=1时,需进行n-1次比较;
    当i=2时,需进行n-2次比较;
    依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n)。

    案例分析

    以排序数组{3,2,1,4,6,5}为例

    image

    image

    代码实现

    public class SimpleSort {
        private  static void simpleSort(){
            int[] number = {2,3,4,1,6,5};
            int length = number.length;
            for (int i=0; i<length-1;i++){//只会进行5轮
                int min_index = i;
                for(int j = i+1;j<length;j++){//每轮的比较
                    if(number[min_index]>number[j]){//找到最小值得下标
                        min_index =j;
                    }
                }
                if(min_index!=i){//交换最小数number[min_index]和第i位数的位置
                    int temp = number[min_index];
                    number[min_index] = number[i];
                    number[i] =temp;
                }
                System.out.print("第"+(i+1)+"次排序:");
                for(int k=0; k<length;k++){
                    System.out.print(number[k]+" ");
                }
                System.out.println("");
            }
    
        }
        public static void main(String[] args){
            simpleSort();
        }
    }
    
    
    第1次排序:1 3 4 2 6 5 
    第2次排序:1 2 4 3 6 5 
    第3次排序:1 2 3 4 6 5 
    第4次排序:1 2 3 4 6 5 
    第5次排序:1 2 3 4 5 6 
    

    排序算法之简单选择排序

    选择排序

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,566
精华内容 6,626
关键字:

简单选择排序