本文作者:心月

选择排序算法的介绍和实现

心月IT博客 2019-12-27
选择排序算法的介绍和实现摘要:​选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

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

排序分析讲解:

待排数组:

23,15,43,25,54,2,6,82,11,5,21,32,65

        初次:起始位置是23所在位置,假设23是最小的,然后把23依次与后面的数做比较

        第一次比较:23与15比较,15比23小,根据排序原理将小的数放到起始位置,所以此时的排序情况为:

15,23,43,25,54,2,6,82,11,5,21,32,65

        然后将15与后面的数做比较,经比较之后找到一个比15小的数:2,则此时的排序情况为:

2,23,43,25,54,15,6,82,11,5,21,32,65

        再将2与后面的数做比较,经过一番比较后并没有找到比2小的数,也就是说在2和其后面的数中,2是最小的,第一个位置的数确定下来。

        然后将排序的起始位置挪到第二位:23,参照第一位的排序方式得到如下排序结果:

2,5,43,25,23,15,82,11,6,21,32,65

【tips】

        在原理中只说了将最小的数存放到序列的起始位置,对于和其做比较的数如何处理并没有说,我个人理解,对于做比较的数有两种处理方式,一种是将最小的数存放到欲裂起始位置后,排序中的数往后挪一位填补空位;另一种处理方式是,将最小的数和与其做比较的数较换一个位置。这两种方式在程序处理上,第二种处理起来更方便,不过不要和冒泡排序算法混淆了(冒泡排序算法一轮排序后最后一个元素是最小(或最大))。

选择排序算法的实现:

php程序实现选择排序算法

1、php实现:

<?php

$arr = [23,15,43,25,54,2,6,82,11,5,21,32,65];
$len = count($arr);
$min = null;

for($i=0; $i<$len; $i++){
    $min = $arr[$i];
    for($k=$i+1; $k<$len; $k++){
        if($arr[$k]<$min){
            $arr[$i] = $arr[$k];
            $arr[$k] = $min;
            $min = $arr[$i];
        }
    }
}


2、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]);    
    }
}


3、c++实现

template<typename T> 
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]);
    }
}


4、java实现

public static void selectionSort(int[] arr) {
        int min, temp;
        for (int i = 0; i < arr.length; i++) {
            // 初始化未排序序列中最小数据数组下标
            min = i;
            for (int j = i+1; j < arr.length; j++) {
                // 在未排序元素中继续寻找最小元素,并保存其下标
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 将未排序列中最小元素放到已排序列末尾
            if (min != i) {
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }


5、python实现

def selection_sort(arr):
    for i in range(len(arr)-1):
        minIndex=i
        for j in range(i+1,len(arr)):
            if arr[minIndex]>arr[j]:
                minIndex=j
        if i==minIndex:
            pass
        else:
            arr[i],arr[minIndex]=arr[minIndex],arr[i]
    return arr
 
 
if __name__ == '__main__':
    testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
    print(selection_sort(testlist))
文章版权及转载声明:

本文由 心月IT技术博客 博主整理于 2019-12-27
若转载请注明原文及出处:https://www.xinyueseo.com/algorithm/579.html

分享到:
赞(
发表评论
快捷输入:

验证码

    评论列表 (有 0 条评论,人围观)参与讨论