选择排序.md

选择排序

简介

数组长度为N, 
第一次循环将0到N-1位置上最小的数和0位置上的数交换
第二次循环将1到N-1位置上最小的数和1位置上的数交换
...

过程分析

# [3, 6, 4, 2, 7], 设数组长度为N

# 第一次循环 0 到 N-1
[2, 6, 4, 3, 7]

# 第二次循环 1 - N-1
[2, 3, 4, 6, 7]

# 第三次循环 0 - N-3
[2, 3, 4, 6, 7]

# 第四次循环 0 - N-4
[2, 3, 4, 6, 7]

代码

PHP

<?php

class SelectionSort
{
    /**
     * 排序
     *
     * @param $arr
     * @return bool
     */
    public static function sort(&$arr)
    {
        if ($arr == null || count($arr) < 2) {
            return false;
        }

        for ($i = 0; $i < count($arr) - 1; $i++) {
            $minIndex = $i;
            for ($j = $i + 1; $j < count($arr); $j++) {
                $minIndex = $arr[$j] < $arr[$minIndex] ? $j : $minIndex;
            }
            list($arr[$i], $arr[$minIndex]) = [$arr[$minIndex], $arr[$i]];
            print_r($arr);
        }
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
SelectionSort::sort($arr);
// [2, 3, 4, 6, 7]
print_r($arr);

java

import java.util.Arrays;

public class SelectionSort {
	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 4, 2, 7};
		selectionSort(arr);
		// [2, 3, 4, 6, 7]
		System.out.println(Arrays.toString(arr));
	}
}

时间复杂度

O(N^2)