排序算法（选择排序法、插入排序）

矫情吗；* 2023-06-25 10:25 21阅读 0赞

# 排序算法 #

我们关注的主要对象是`重新排列数组元素`的算法。  
大多情况下，我们的排序代码通常只会通过两个方法操作数据：

*  `less()`方法对元素进行比较
 *  `exch()`方法将元素交换位置

排序算法类的模板：

public class Example{
        
    	/**
         * 排序算法
         * @param a
         */
        public static void sort(Comparable[] a){
        
            ...
        }
    
        /**
         * 比较元素的大小
         * @param v
         * @param w
         * @return
         */
        private static boolean less(Comparable v,Comparable w){
        
            return v.compareTo(w) < 0;
        }
    
        /**
         * 交换元素
         * @param a
         * @param i
         * @param j
         */
        private static void exch(Comparable[] a,int i,int j){
        
            Comparable t = a[i];a[i]=a[j];a[j]=t;
        }
    
        /**
         * 打印结果
         * @param a
         */
        private static void show(Comparable[] a){
        
            for(int i=0;i<a.length;i++){
        
                System.out.println(a[i]);
            }
        }
    
        /**
         * 确保方法已经有序
         * @param a
         * @return
         */
        public static boolean isSorted(Comparable[] a){
        
    
            for(int i=1;i<a.length;i++){
        
                if(less(a[i],a[i-1])) return false;
            }
            return true;
        }
    }

--------------------

## 选择排序 ##

选择排序是一种最简单的排序算法，算法的`核心思想`：

> 首先，找到数组中最小的那个元素，其次，将它和数组中的第一个元素交换位置（如果第一个元素最小那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组中第二个元素交换位置。如此反复，直到将整个数组排序。

算法的特点：

*  运行时间与输入无关。
 *  数据移动总是最少的。只用了N次交换
 *  时间复杂度:O(n2)

算法Demo：

from typing import List
    
    class Selection:
        @staticmethod
        def sort(nums:List[int]):
            for i in range(len(nums)-1):
                min = i
                for j in range(i+1,len(nums)):
                    if nums[j] < nums[min]:
                        min = j
    
                nums[i],nums[min] = nums[min],nums[i]
    
            for k in range(len(nums)):
                print(nums[k])
    
    if __name__ == '__main__':
        Selection.sort([5,4,3,2,1])

--------------------

## 插入排序法 ##

通常人们整理桥牌的方法时一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。**在计算机的视线中，为了给要插入的元素腾出空间，我们需要将其与所有元素在插入之前都向右移动一位。**

算法的特点：

*  当索引左边的元素都是有序的，但它们的最终位置还不确定。
 *  插入排序所需的时间取决于输入中元素的起始顺序。
 *  时间复杂度： `最坏情况`下需要 N2/2次比较和 N2/2次交换，`最好情况`下需要N-1次比较和0次交换

算法Demo：

from typing import List
    
    class Insertion:
        @staticmethod
        def sort(nums:List[int]):
            for i in range(len(nums)):
                j = i
                while j > 0:
                    if nums[j] < nums[j-1]:
                        nums[j],nums[j-1] = nums[j-1],nums[j]
    
                    j -= 1
    
            for item in nums:
                print(item)
    
    if __name__ == '__main__':
        Insertion.sort([5,4,3,2,1])

算法说明：

> 其实排序是从索引0的位置，依次向前进行判断，如果相邻的两个数字后边的更小，就进行交换，直到索引0的位置，依次类推，直到完全有序。

--------------------