选择排序算法

cnaka

选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

选择排序的Java实现:

1. package com.mianshi.easy;
   
2. public class Selection {
   
3. 
   
4.     public static void main(String[] args) {
   
5.         int[] a = {3,11,12,15,4,6,9,8,7};
   
6. 
   
7.         selectionSort(a);
   
8. 
   
9.         for(int i = 0; i < a.length; i++){
   
10.             System.out.print(a[i]+" ");
    
11.         }
    
12.     }
    
13. 
    
14.     public static void selectionSort(int[] a)
    
15.     {
    
16.         for(int i=0; i<a.length; i++)
    
17.         {
    
18.             int k = i; 　　　　　
    
19.             for(int j = i+1; j<a.length; j++)
    
20.             {
    
21.                 if(a[k] > a[j])
    
22.                 {
    
23.                     k = j;
    
24.                 }
    
25.             }
    
26.             //若k不等于i；说明至少存在一个元素小于自定义的最小值，并得到该元素的下标，用于交换
    
27.             if(k != i)
    
28.             {
    
29.                 int temp = a[i];
    
30.                 a[i] = a[k];
    
31.                 a[k] = temp;
    
32.             }
    
33.         }
    
34.     }
    
35. }

复制代码

代码中k的作用类似于一个指针，指向最小的数。



算法稳定性：不稳定的排序算法。选择排序是不稳定的（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

时间复杂度：平均时间复杂度为

renxiao2003

我觉得经典算法还是应该用C语言来讲解。

路曼曼

回复 2# renxiao2003
请问为什么经典的算法用C语言来讲解呢？

   

renxiao2003

高级语言（面向对象语言）讲解算法显得不伦不类。

fly3ds

虽然简单，也很好。用Java实现挺好，有很多Java实现的数据结构与算法的书。说不伦不类，一定是看书太少的缘故。