[数据结构与算法]排序算法五、选择排序

话不多说，直接上代码

package com.example.demo.study;

import org.junit.Test;

public class SelectSort
{

    @Test
    public void testSort()
    {
        int[] a = {5, 8, 7, 28, 96, 4 , 7, 0, 3};
        selectSort(a);
        CommonService.printArray(a);
    }

    /**
     * 选择排序
     * @param a
     */
    public void selectSort(int[] a)
    {
        int min = a[0];
        int minIndex = 0;
        for (int i = 0; i < a.length; i ++)
        {
            min = a[i];
            minIndex = i;
            for (int j = i + 1; j < a.length; j ++)
            {
                if (a[j] < min) // 如果找到了一个元素，比最小值要小，把a[j]赋值给最小值min
                {
                    min = a[j];
                    minIndex = j;
                }
            }

            if (i != minIndex) // 如果i和minIndex不相等，说明发现更小元素，交换i和minIndex
            {
                int t = a[i];
                a[i] = a[minIndex];
                a[minIndex] = t;
            }
        }
    }
}

算法思想（升序为例）：

对有n个元素的数组，排序过程如下：

1、默认取第一个元素为最小元素min,遍历一次剩下的元素，找到最小元素，记录其下标j为minIndex,并把它赋值给min；

2、将遍历一次后得到的minIndex和当前的遍历值i比较，如果不一样，则交换2个元素的位置；

3、从剩余的（n - i）个元素中找到下一个最小值，重复上面的2个步骤，直到排序结束；

个人理解：

这种排序方法和冒泡排序比较相似，但是冒泡排序每次找到最大的元素过程中一直在交换元素，而选择排序是记录最小元素的下标，在一次查找结束后直接交换当前遍历的元素和最小元素，而且每次查找最小元素后下一次的遍历元素会少一个。

所以个人认为这种算法优于冒泡排序。

时间复杂度：

时间复杂度为O（n2）。