经典排序算法 - 选择排序

@date:2017-07-23 09:19:00

概述 #

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

特点:以从小到大排序为例: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
  1. 第2趟:
    首元素已排好序,固定住。
1,3,4,2
1,2,4,3
  1. 第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

Build by Loppo 0.6.14