Donnie

不积跬步无以至千里

简单选择排序

1.简单选择排序:选择最小数进行交换
2.是不稳定排序
3.时间复杂度为 O(n^2)。最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次
4.是原地排序


       //java实现
    import java.util.Arrays;
    
    public class SelectionSort {
    
        public static void main(String[] args) {
            int[] arr = {9, 5, 1, 3, 6, 8, 4, 2, 7};
            selectionSort(arr);
    
            System.out.println(Arrays.toString(arr));
        }
    
    
        public static void selectionSort(int[] arr){
    
            for (int i = 0; i < arr.length; i++) {
    
                int index = i;  //用于记住最新数的下标
    
                //j从i+1开始,因为i就是本身,不需要再比较
                for (int j = i+1; j < arr.length; j++) {
    
                    if (arr[j]< arr[index]){
                        index = j;
                    }
    
                }
                // 如果相等就不必交换,减少cpu用时
                if (i != index) {
                    int temp = arr[i];
                    arr[i] = arr[index];
                    arr[index] = temp;
                }
            }
        }
    }

       //go实现
    import (
        "fmt"
    )
    
    func main(){
    
        arr:=[]int{1,9,8,10,6,5,4,3,2, 7}
    
        selectSort(arr)
    
        fmt.Println(arr)
    
    }
    
    //选择排序
    func selectSort(arr []int) {
    
        for i := 0; i < len(arr); i++ {
    
            min := i  //用于记住最新数的下标
            //循环寻找最小数
            for j := i + 1; j < len(arr); j++ {
                if arr[min] > arr[j] {
                    min = j
                }
            }
            fmt.Println(arr)
            //找到最小数进行交换
            arr[i], arr[min] = arr[min], arr[i]
        }
    }


赞赏支持