八大排序算法之选择排序

基本思想

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第2个数）和第n个元素（最后一个数）比较为止。

操作方法

1. 第一趟，从n个记录中找出关键码最小的记录与第1个记录交换；
2. 第二趟，从第2个记录开始的n-1个记录中再选出关键码最小的记录与第2个记录交换；
3. 以此类推…..
4. 第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i 个记录交换，直到整个序列按关键码有序。

算法的实现

package com.zyg.sort;

public class SelectSortAlgorithm
{
    // 选择排序
    public static void selectSort(int a[], int len)
    {
        for (int i = 0; i < len; i++)
        {
            // 设置最小元素为第i个
            int min = i;
            <!--more-->
            for (int j = i + 1; j < len; j++)
            {
                // 如果找到更小的元素，则重新设置最小元素序号
                if (a[min] > a[j])
                    min = j;
            }
            // 将第i个元素与第min个元素交换
            swap(a, i, min);
        }
    }
    
    // 交换元素
    public static void swap(int a[], int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    // 打印数组
    public static void printArray(int a[])
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
    
    public static void main(String[] args)
    {
        // 定义初始化数组
        int a[] =
        { 4, 3, 6, 7, 33, 15, 90, 65, 777, 5550 };
        // 进行选择排序
        selectSort(a, a.length);
        // 打印数组
        printArray(a);
    }
}

效率

时间复杂度

平均情况：O(n²)
最好情况：O(n²)
最坏情况：O(n²)

空间复杂度

O(1)

稳定性

不稳定