建站资讯

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

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

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

排序分析讲解:

待排数组:

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
若转载请注明原文及出处:


收缩