常用排序算法专题—选择排序

作者: 9f5e612a0d44 | 来源:发表于2019-03-19 21:16 被阅读233次

    选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

    • 基本思路
        我们假设有一个含有6个元素的int型的一维数组变量,他们分别是 2,7,8,9,6,4,我们对它们进行选择排序:

      我们首先进行第一轮排序:
      先把第0个元素,即'2'作为索引值,此时索引值的地址是0;
      索引值元素(第0个)与第1个元素,即7比较,2<7,不进行操作;
      索引值元素(第0个)与第2个元素,即8比较,2<8,不进行操作;
      索引值元素(第0个)与第3个元素,即8比较,2<9,不进行操作;
      索引值元素(第0个)与第4个元素,即8比较,2<6,不进行操作;
      索引值元素(第0个)与第5个元素,即8比较,2<4,不进行操作;

    此时我们本应该将索引值地址与第0个元素交换的,但是我们发现索引值地址一直没发生变化。

    我们再进行第二轮排序:
    先把第1个元素,即'7'作为索引值,此时索引值的地址是1;
    索引值元素(第1个)与第2个元素,即8比较,7<8,不进行操作;
    索引值元素(第1个)与第3个元素,即9比较,7<8,不进行操作;
    索引值元素(第1个)与第4个元素,即6比较,7>6,更新索引值,目前索引值地址为4
    索引值元素(第4个)与第5个元素,即4比较,6>4,更新索引值,目前索引值地址为5

    我们再将第1个元素与索引值地址的元素交换,即第1个元素与第5个元素交换,此时数组序列为2,4,8,9,6,7

    我们再进行第三轮排序:
    先把第2个元素,即'8'作为索引值,此时索引值的地址是2;
    索引值元素(第2个)与第3个元素,即9比较,8<9,不进行操作;
    索引值元素(第2个)与第4个元素,即9比较,8>6,更新索引值,目前索引值地址为4
    索引值元素(第4个)与第5个元素,即4比较,6>7,不进行操作;

    我们再将第2个元素与索引值地址的元素交换,即第2个元素与第4个元素交换,此时数组序列为2,4,6,9,8,7,依次类推排序即可完成。



    JAVA 代码:

    package DataStructure;
    
    public class SeleteSort {
    
        public static void sort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                int minIndex = i;
                for (int j = i + 1; j < arr.length; j++)
                    if (arr[j] < arr[minIndex])
                        minIndex = j;
    
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
    
        }
    
        public static void main(String[] args) {
            int[] arr = { 2, 7, 8, 9, 6, 4 };
            sort(arr);
            for (int n : arr)
                System.out.print(n + " ");
        }
    }
    
    
    • 时间复杂度

      选择排序最好的时间复杂度为 O(n²),最坏时间复杂度为 O(n²);
    综上,因此选择排序总的平均时间复杂度为 O(n²)。

    相关文章

      网友评论

        本文标题:常用排序算法专题—选择排序

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