算法之選擇排序
-
一：基本概念
選擇排序(Select Sort)队丝，第1趟港准，在待排序記錄r[1]r[n]中選出最小的記錄，將它與r[1]交換抄瑟；第2趟凡泣，在待排序記錄r[2]r[n]中選出最小的記錄，將它與r[2]交換皮假；以此類推鞋拟，第i趟在待排序記錄r[i]r[n]中選出最小的記錄，將它與r[i]交換惹资，使有序序列不斷增長直到全部排序完畢贺纲。
二：圖文說明
選擇排序示意圖.png
我們分析一下具體的排序步驟：
1. 我們先找到數(shù)列中最小的數(shù)字即16，我們需要將最小的排到第一位布轿，所以將第一位上的值21和16進(jìn)行交換哮笆；
2. 除過第一位元素，在后面的數(shù)列中找出最小的值放到第二位汰扭，即將21與25進(jìn)行交換稠肘；
3. 除過第一、第二位元素萝毛，在后面的數(shù)列中找出最小的值放到第三位项阴，即將25與49進(jìn)行交換；
4. 除過第一笆包、第二环揽、第三位元素，在后面的數(shù)列中找出最小的值放到第四位庵佣，因?yàn)?2是最小的值歉胶，剛好又在第四位上，所以不用交換巴粪；
5. 剩下的最后一位肯定就是最大的數(shù)通今，即數(shù)組排序完成！
-
三：代碼實(shí)現(xiàn)
- C語言實(shí)現(xiàn)
#include <stdio.h> /* 選擇排序 */ void show(int arr[],int len);//打印出數(shù)組 void swap(int arr[],int i,int j); //交換數(shù)組中的兩個(gè)位置 void selectSort(int arr[],int len); //選擇排序算法實(shí)現(xiàn) int main(void) { int arr[] = {21, 25, 49, 32, 16}; int len = sizeof(arr)/sizeof(*arr); printf("待排序數(shù)組為:\n"); show(arr,len); selectSort(arr,len); printf("排序之后的數(shù)組為:\n"); show(arr,len); return 0; } void show(int arr[],int len) { int i; for(i=0;i<len;i++) { printf("%d ",arr[i]); } printf("\n"); } void swap(int arr[],int i,int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void selectSort(int arr[],int len) { int i,j; int k = -1; for(i=0; i<len;i++) { k = i;//存儲(chǔ)將要交換位置的下標(biāo) for(j=i;j<len;j++)//第一趟排序中的所有比較 { if(arr[j]<arr[k]) { k = j; } } swap(arr,i,k); } }2.JAVA實(shí)現(xiàn)
package com.data; import java.util.Arrays; public class SelectSort { public static void main(String[] args) { int a[] = {21, 25, 49, 32, 16}; System.out.println("排序前的數(shù)組為:"+Arrays.toString(a)); selectionSort(a); System.out.println("排序后的數(shù)組為:"+Arrays.toString(a)); } public static void selectionSort(int arr[]){ for(int i=0;i<arr.length;i++){ //遍歷整個(gè)數(shù)組 int minIndex=i; //聲明最小值坐標(biāo) for(int j=i+1;j<arr.length;j++){ //遍歷為交換的數(shù)組 if(arr[minIndex]>arr[j]){ //拿當(dāng)前最小值跟為交換的數(shù)組對比 minIndex=j; } } int conversion=arr[i]; //換位變量 arr[i]=arr[minIndex]; //交換位置 arr[minIndex]=conversion; } } } -
四：選擇排序的時(shí)間復(fù)雜度和穩(wěn)定性
- 選擇排序的時(shí)間復(fù)雜度
- 選擇排序的時(shí)間復(fù)雜度是O(N*N)肛根。
- 選擇排序穩(wěn)定性
- 選擇排序即是給每個(gè)位置選擇待排序元素中當(dāng)前最小的元素辫塌。比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)位置選擇次小的派哲，依次類推臼氨，直到第n-1個(gè)元素，第n個(gè)元素不用選擇了芭届，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了储矩。那么感耙，在一趟選擇時(shí)，如果當(dāng)前鎖定元素比后面一個(gè)元素大椰苟，而后面較小的那個(gè)元素又出現(xiàn)在一個(gè)與當(dāng)前鎖定元素相等的元素后面抑月，那么交換后位置順序顯然改變了。
