陈大剩博客

排序算法-选择排序详解

  • 陈大剩
  • 2020-11-14 17:32:40
  • 2020

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

过程演示:

排序算法gif图

代码演示

C代码演示

#include <stdio.h>
void swap(int *a, int *b); // 交换两个数的函数
void selection_sort(int arr[], int len); //排序函数
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]);
    }
}
int main() {
    int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
    int len = (int) sizeof(arr) / sizeof(*arr);
    selection_sort(arr, len);
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

PHP代码演示

$arr = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
for ($i = 0; $i < count($arr)-1; ++$i) {
    $min = $i;
    for ($j = $i + 1; $j < count($arr); ++$j) {
        if ($arr[$j] < $arr[$min]) {
            $min = $j;
        }
    }
    $temp = $arr[$min];
    $arr[$min] = $arr[$i] ;
    $arr[$i] = $temp;
}
var_dump($arr);

循环过程

循环过程其实最左边的数一直和最右边的数比较,把最小的值移到左边来;
第1趟比较:拿第1个元素依次和它后面的每个元素进行比较,如果第1个元素大于后面某个元素,交换它们,经过第1趟比较,数组中最小的元素被选出,它被排在第一位;
第2趟比较:拿第2个元素依次和它后面的每个元素进行比较,如果第2个元素大于后面某个元素,交换它们,经过第2趟比较,数组中第2小的元素被选出,它被排在第二位;
第n-1趟比较:第n-1个元素和第n个元素作比较,如果第n-1个元素大于第n个元素,交换它们;
循环过程

参考文献

CoderJed:[图解] 选择排序

分享到:
1

说点儿什么吧

头像

表情

本站由陈大剩博客程序搭建 | 湘ICP备17009938号| Copyright © 2017 - 陈大剩博客 | 本站采用创作共用版权:CC BY-NC 4.0

站长统计| 文章总数[31]| 评论总数[12]| 登录用户[21]| 时间点[33]

登入

社交账号登录