简单选择法排序

作者:原创时间:2022-05-25
文档

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是选择排序算法:

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

重复第二步,直到所有元素均排序完毕。

2. 动图演示


代码实现

JavaScript 代码实现

实例

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

Python 代码实现

实例

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时,将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

Go 代码实现

实例

func selectionSort(arr []int) []int {
        length := len(arr)
        for i := 0; i < length-1; i++ {
                min := i
                for j := i + 1; j < length; j++ {
                        if arr[min] > arr[j] {
                                min = j
                        }
                }
                arr[i], arr[min] = arr[min], arr[i]
        }
        return arr
}

Java 代码实现

实例

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

PHP 代码实现

实例

function selectionSort($arr)
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

C 语言

实例

void swap(int *a,int *b) //交換兩個變數
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len)
{
    int i,j;

        for (i = 0 ; i < len - 1 ; i++)
    {
                int min = i;
                for (j = i + 1; j < len; j++)     //走訪未排序的元素
                        if (arr[j] < arr[min])    //找到目前最小值
                                min = j;    //紀錄最小值
                swap(&arr[min], &arr[i]);    //做交換
        }
}

C++

实例

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void selection_sort(std::vector<T>& arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
                int min = i;
                for (int j = i + 1; j < arr.size(); j++)
                        if (arr[j] < arr[min])
                                min = j;
                std::swap(arr[i], arr[min]);
        }
}

C#

实例

static void selection_sort<T>(T[] arr) where T : System.IComparable<T>{//整數或浮點數皆可使用
        int i, j, min, len = arr.Length;
        T temp;
        for (i = 0; i < len - 1; i++) {
                min = i;
                for (j = i + 1; j < len; j++)
                        if (arr[min].CompareTo(arr[j]) > 0)
                                min = j;
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
        }
}

Swift

实例

import Foundation
/// 选择排序
///
/// - Parameter list: 需要排序的数组
func selectionSort(_ list: inout [Int]) -> Void {
    for j in 0..- 1 {
        var minIndex = j
        for i in j..{
            if list[minIndex] > list[i] {
                minIndex = i
            }
        }
        list.swapAt(j, minIndex)
    }
}

原文地址:https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md

参考地址:https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

以下是热心网友对选择排序算法的补充,仅供参考:

热心网友提供的补充1:

Kotlin 实现

class SelectionSort { 
    /** 
    * 拓展IntArray为他提供数据两个数交换位置的方法 
    * @param i 第一个数的下标 
    * @param j 第二个数的下标 
    */ 
    fun IntArray.swap(i:Int,j:Int){ 
        var temp=this[i] 
        this[i]=this[j] 
        this[j]=temp 
    } 
    fun selectionSort(array: IntArray):IntArray{
        for (i in array.indices){ 
            //假设最小值是i 
            var min=i 
            var j=i+1 
            while (j in array.indices){ 
                if (array[j]以上为选择排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括: 

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释:

n:数据规模

k:"桶"的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同

显示全文
冒泡排序图解 希尔排序的算法流程图 直接选择排序比较次数 冒泡排序结果 c语言希尔排序例题 直接选择排序c语言 冒泡排序算法代码 选择排序算法c 冒泡排序c语言代码 选择一个排序算法时要考虑 增加标志的冒泡法排序 简单选择排序图解 冒泡排序流程图怎么画 直接选择排序法图解 冒泡排序 c语言数组选择排序 冒泡排序比较次数公式 简单选择排序过程 数据结构冒泡排序 实现选择排序算法 希尔排序数据结构 冒泡排序分析 冒泡排序比较次数 直接选择排序图解 希尔排序c语言代码 冒泡排序法C语言 选择排序的原理 希尔排序算法c语言 归并排序是如何进行的 c语言冒泡排序法详解 选择排序怎么排 数据结构希尔排序算法 归并排序的基本思想 冒泡排序优化思路 选择排序法排序十个数 希尔排序图解 归并排序算法伪代码 java冒泡排序算法代码 c语言选择法排序讲解 数据结构希尔排序例子