排序算法——选择排序

时间：2022-10-11 22:08:11

一种最简单的排序算法是这样的：

  1. 找到数组中最小的那个元素。
  2. 将它和数组的第一个元素交换位置(如果第一个元素就是最小的那么它就和自己交换)。
  3. 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
    这种方法叫做选择排序，因为它在不断地选择剩余元素之中地最小者。

代码实现如下：

//选择排序
public class Selection {

//将a[]按升序排列
public static void sort(Comparable[] a){
    int N = a.length;//数组长度
    for(int i=0; i<N; i++){
        //将a[i] 和a[i+1...N]中最小的元素交换
        int min = i;//最小元素的索引
        for(int j=i+1; j<N; j++)
            if(a[j].compareTo(a[min])<0)  min = j;

        Comparable t = a[i];                
        a[i] = a[min];              
        a[min] = t;         
    }
    //打印数组
    for(Comparable A:a)
        System.out.print(A+" ");
    System.out.println(" ");        
}

public static void main(String[] args) {
    Selection test = new Selection();
    String[] strArr = {"A","W","Q","A","B","Z"};
    Integer[] sc = {9,2,3,6,7,1,2,8};
    System.out.println("排序前:"+"A W Q A B Z");
    System.out.print("排序后:");
    test.sort(strArr);
    System.out.println("排序前:"+"9 2 3 6 7 1 2 8");
    System.out.print("排序后:");
    test.sort(sc);
}

}

运行结果：
排序算法——选择排序

排序过程：
排序算法——选择排序

总的来说，选择排序是一种很容易理解和实现地简单排序算法，它有两个很鲜明的特点。

1. 运行时间和输入无关。

为了找到最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。一个已经有序的数组和一个等长的元素随机排列的数组用选择排序所花费的时间是一样的。

2. 数据移动是最少的。

每次交换都会改变两个数组元素的值，因此选择排序用了N次交换——交换次数和数组的大小是线性关系。

对长度为N的数组，选择排序需要大约N^2/2次比较和N次交换。

标签：

相关文章