选择排序 (Selection Sort)
选择排序是一种简单的排序算法。它的基本思想是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。
步骤:
首先在未排序序列中找到最小元素,存放到排序序列的起始位置。
遍历未排序序列,将所有小于最小元素值的后续元素放到排序序列前面。
重复上述步骤,直到未排序序列中没有元素,排序序列即为有序序列。
以下是一个说明的示例:
给定一个未排序的数组[9,5,8,3,7]:
从未排序数组中找到最小元素3,并将其与数组 [9,5,8,3,7]的第1个元素9互换,从而构成新的未排序序列[3,5,8,9,7]。
对新的未排序序列,重新从第1步开始,找到最小元素5,并与数组[3,5,8,9,7]的第2个元素5交换,从而构成新的未排序序列[3,5,8,9,7]。
对新的未排序序列,重复上述步骤,找到最小元素7,并与数组[3,5,8,9,7]的第4个元素9互换,从而构成新的未排序序列[3,5,8,7,9]。
重复上述步骤,直到未排序序列中的全部元素全部已经排序(全部为最小值之上的有序序列):
排序前:[9,5,8,3,7]
排序后:[3,5,7,8,9]
#include <iostream>
using namespace std;
void select_sort(int arr[],int len) {
for(int i = 0;i<len;i++){
for(int j = i+1;j<len;j++){
if(arr[j] < arr[i]) swap(arr[i],arr[j]);
}
}
}
int main(void){
int arr[] = {9,5,8,3,7};
int len = sizeof(arr)/sizeof(int);
select_sort(arr,len);
for(int i = 0;i<len;i++){
cout << arr[i] << " ";
}
}
package sort;
import java.util.Arrays;
//选择排序模板
public class select_sort {
public static void main(String[] args) {
int[] arr = new int[]{10,20,-10,40,199,2,100};
select_sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void select_sort(int[] arr){
for(int i = 0;i<arr.length-1;i++){
int min = arr[i];
int min_index = i;
for(int j = i+1;j<arr.length;j++){
if(min>arr[j]){
min = arr[j];
min_index = j;
}
}
if(i != min_index){
arr[min_index] = arr[i];
arr[i] = min;
}
}
}
}