十大排序算法——选择排序

简介: 十大排序算法——选择排序

目录


选择排序原理


选择排序API设计


选择排序代码实现


选择排序的时间复杂度


选择排序原理

①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引


②交换第一个索引处和最小值所在的索引处的值


选择排序API设计

image.png

选择排序代码实现

public class Selection {
    //对数组a中的元素进行排序
    public static void sort(Comparable[] a){
        for(int i=0;i<a.length-2;i++){
            int minIndex=i;
            for(int j=i+1;j<a.length;j++){
                if(greater(a[minIndex],a[j])){
                    minIndex=j;
                }
            }
            exchange(a,i,minIndex);
        }
    }
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exchange(Comparable[] a,int i,int j ){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
class Test{
    public static void main(String[] args) {
        Integer[] a={4,6,8,7,9,2,10,1};
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

选择排序的时间复杂度

选择排序使用了双层for循环,外层循环完成了数据交换,内层循环完成了数据比较,所以分别统计:数据比较次数:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;


       数据交换次数:N-1;


时间复杂度: N^2/2-N/2+(N-1)=N^2/2+N/2-1;


根据大O推导法则,保留最高阶项,去除常数因子,时间复杂度为O(N^2)


第二种写法

public class SelectionSort {
    private static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 最小数的索引
            int minIndex = i;
            // 找到最小数,并记录最小数的索引
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
相关文章
|
2月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
24 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
2月前
|
搜索推荐 Java Go
深入了解选择排序算法
深入了解选择排序算法
29 4
|
2月前
|
搜索推荐 算法
【排序算法(一)】——插入排序,选择排序 —> 深层解析
【排序算法(一)】——插入排序,选择排序 —> 深层解析
|
2月前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
34 0
|
4月前
|
搜索推荐 算法 Java
经典排序算法之-----选择排序(Java实现)
这篇文章通过Java代码示例详细解释了选择排序算法的实现过程,包括算法的基本思想、核心代码、辅助函数以及测试结果,展示了如何通过选择排序对数组进行升序排列。
经典排序算法之-----选择排序(Java实现)
|
6月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
6月前
|
搜索推荐
排序算法---选择排序-----详解&&代码
排序算法---选择排序-----详解&&代码
|
6月前
|
算法 搜索推荐
数据结构与算法-选择排序
数据结构与算法-选择排序
34 4
|
6月前
|
搜索推荐 算法
【C/排序算法】:堆排序和选择排序
【C/排序算法】:堆排序和选择排序
40 0
|
6月前
|
算法 搜索推荐 Java
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
44 0