经典排序算法 – 选择排序

c/c++

浏览数:189

2019-9-15

概述

含义:直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完。

特点:以从小到大排序为例:N个元素,每一趟比较找出最小的那个元素,放在头部;经过N-1趟比较,排序就出来了。

相当于每次从无序列表里找出一个最小数,放到左边;然后剩下的元素继续找出最小的,放在左边;直到排序完成。

题目:给出无需数组 [4,3,1,2],要求按照从小到大排序。
输出样例:

1
2
3
4

排序过程:
原数组:

4,3,1,2

1) 第1趟:

3,4,1,2
1,4,3,2
1,4,3,2

2) 第2趟:
首元素已排好序,固定住。

1,3,4,2
1,2,4,3

3) 第3趟:
第2个元素已排好序,固定住。

1,2,3,4

C语言实现

#include<stdio.h>

#define MAX 4
void selection_sort(int *, int);
void selection_sort2(int *, int);

int main(){
    
    
    int arr[MAX] = {4,3,1,2};
    selection_sort(arr, MAX);
    
    int i;
    for(i =0; i< MAX; i++){
        printf("%d\n", arr[i]);
    }
    
    return 0;
}

void selection_sort(int *arr, int n){
    int i,j,min,temp;
    for(i=0; i< n-1; i++){//比较趟数:n个数只需要比较n-1趟 
        for(j=i+1; j<n;j++){//从i+1个元素起,元素之间互相比较 
            if(arr[j] < arr[i]){//如果后面的元素小于于第一个元素,与第一个元素交换位置;这样第一个一直是相对小的 
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

/**
* 优化后的选择排序:
* 每一趟比较只要知道了最小的那个元素的索引,然后每一趟交换一次就行了;没必要每比较一次就交换顺序。 
*  
*/
void selection_sort2(int *arr, int n){
    int i,j,min_index,temp;
    for(i=0; i< n-1; i++){//比较趟数:n个数只需要比较n-1趟 
        min_index = i;//假设第一个元素是最小的 
        for(j=i+1; j<n;j++){//元素之间互相比较次数 
            if(arr[j] < arr[min_index]){//1.如果后面的元素小于假设的最小元素 
                min_index = j;//2.将最小的元素索引记录下来,但不交换位置 
            }
        }
        
        if(min_index != i){//3.经过一趟比较之后,如果最小元素索引和最先假设的不相同,说明第一个元素不是最小的,进行交换 
            temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
    }
}

参考:
经典排序算法 – 选择排序Selection sort – kkun – 博客园
http://www.cnblogs.com/kkun/archive/2011/11/23/2260281.html

作者:飞鸿影