美文网首页数据结构与算法
算法(一)之排序算法(二)——选择排序(SelectSort)

算法(一)之排序算法(二)——选择排序(SelectSort)

作者: bryanrady_wang | 来源:发表于2017-12-20 14:17 被阅读8次

    选择排序是八大排序算法之一,其排序原理是:

    比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换其数据的索引位置,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成。选择排序与冒泡排序有点不同的是,选择排序是先交换下标,然后在交换数值。用文字叙述是讲不清楚的,还是通过流程来分析吧。

    如现在有一组数据:[3, 1, 8, 6, 2, 5, 9, 4, 7]

    使用选择排序对这组数据进行排序,具体流程:

    第一趟排序: 定义一个下标 int index = 0; 即先指向第一个数3,感叹号代表下标。

           3    1    8    6    2    5    9    4    7
           !
    

    (1) 把index指向的数和下标从1开始往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即3>1,1的下标是1,所以index=1; 这时候下标index指向下标就是1。

           3    1    8    6    2    5    9    4    7
                !
    

    (2) 把index指向的数和下标从2开始往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。后面的数字都比1大,这时候下标index指向的下标还是1。

           3    1    8    6    2    5    9    4    7
                !
    

    .............继续上面的步骤把循环走完,一直走到下标从8开始往后面依次遍历的数字进行比较的时候,发现还是没有数字比index 1指向的数字1小,那就退出了循环,开始进行数字的交换。

            1    3    8    6    2    5    9    4    7    第一趟排序的结果
    

    把第一个数和下标为index的数进行交换,这样一来就相当于把最小的数找到了并且放在第一位,接下来我们只需要对后面的8个数进行排序即可。


    第二趟排序:定义一个下标 int index = 1; 即先指向第二个数3,感叹号代表下标。

            1    3    8    6    2    5    9    4    7
                 !
    

    (1)把index指向的数和从下标为2开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即3>2, 2的下标是4,所以 index = 4; 这时候下标index指向下标就是4。

            1    3    8    6    2    5    9    4    7
                                !
    

    (2)把index指向的数和从下标为3开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。后面的数字都比2大,这时候下标index指向的下标还是4。

            1    3    8    6    2    5    9    4    7
                                !
    

    .............继续上面的步骤把循环走完,一直走到下标从8开始往后面依次遍历的数字进行比较的时候,发现还是没有数字比index 4指向的数字2小,那就退出了循环,开始进行数字的交换。

            1    2    8    6    3    5    9    4    7    第二趟排序的结果
    

    第三趟排序:定义一个下标 int index = 2; 即先指向第三个数8,感叹号代表下标。

            1    2    8    6    3    5    9    4    7
                      !
    

    (1)把index指向的数和从下标为3开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即8>6, 6的下标是3,所以 index = 3; 这时候下标index指向下标就是3。

            1    2    8    6    3    5    9    4    7
                           !
    

    (2)把index指向的数和从下标为4开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即6>3, 3的下标是4,所以 index = 4; 这时候下标index指向下标就是4。

            1    2    8    6    3    5    9    4    7
                                !
    

    (3)把index指向的数和从下标为5开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。后面的数字都比3大,这时候下标index指向的下标还是4。

    .............继续上面的步骤把循环走完,一直走到下标从8开始往后面依次遍历的数字进行比较的时候,发现还是没有数字比index 4指向的数字3小,那就退出了循环,开始进行数字的交换。

            1    2    3    6    8    5    9    4    7      第三趟排序结果
    

    根据这样的流程一直循环下去,最终就会实现这样的排序结果,后面的流程我就不继续写下去了。

    直接上代码:

            public static void selectSort(int[] array){
                for(int i = 0;i < array.length-1; i++){
                    int index = i;
                    for(int j = i+1;j < array.length; j++){
                        if(array[index] > array[j]){
                            index = j;    //说明找到了比Index小的数的下标
                        }
                    }
    
                    if(index != i){    //如果最小的数位置发生了变化就交换
                        int temp = array[index];
                        array[index] = array[i];
                        array[i] = temp;
                    }
                }
            }
    

    选择排序应用场景:也是应用在数据量小的情况下。

    相关文章

      网友评论

        本文标题:算法(一)之排序算法(二)——选择排序(SelectSort)

        本文链接:https://www.haomeiwen.com/subject/mprgwxtx.html