排序算法之直接插入排序及Java实现

淡淡的烟草味﹌ 2022-05-25 23:48 217阅读 0赞

## 一、排序算法的分类 ##

1.  选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]）
2.  交换排序（[冒泡排序][Link 3]，[快速排序][Link 4]）
3.  插入排序（[直接插入排序][Link 5]，[希尔排序][Link 6]）
4.  [归并排序][Link 7]
5.  桶式排序
6.  基数排序

## 二、直接插入排序的原理 ##

插入排序通俗来讲，就是在一组无序的数组中一个个地取出值，将其放在有序的数组中合适的位置，使有序的数组再次有序，直到无序的数组为空，循环结束。

## 三、直接插入排序的实现 ##

public class InsertSort{
        
        /**
         * 插入排序
         * 插入排序相当于向一个排好序的数组中加入新值，使得数组再次有序
         * 当第一次遍历时，相当于将第二个值与第一个比较，较小的放在前面
         * 第二次遍历时，则是将第三个值加入前两个值中合适的位置，使得三个值有序
         * ...
         * 当将最后一个值加入到前面已经排好序的数组中时，遍历结束
         * @param a
         */
        public static void insSort(int[] a){
            for(int i=0; i<a.length; i++){
                int tmp = a[i];
                int j = 0;
                //将第i个值插入当前i-1中的合适位置
                for(j=i; j>0&&tmp<a[j-1]; j--){
                    //从后向前遍历，如果tmp值更小，说明它的位置需要更靠前
                    //所以依次向后移动一个位置
                    a[j] = a[j-1];
                }
                a[j] = tmp;
            }
        }
        public static void main(String args[]){
            int[] test = {
       5,10,6,3,2};
            insSort(test);
            for(int i=0; i<test.length; i++){
                System.out.print(test[i] + " ");
            }
        }
    
    }

测试结果：

2 3 5 6 10

[Link 1]: https://blog.csdn.net/xdzhouxin/article/details/80017538
[Link 2]: https://blog.csdn.net/xdzhouxin/article/details/80079195
[Link 3]: https://blog.csdn.net/xdzhouxin/article/details/80017719
[Link 4]: https://blog.csdn.net/xdzhouxin/article/details/80031668
[Link 5]: https://blog.csdn.net/xdzhouxin/article/details/80024190
[Link 6]: https://blog.csdn.net/xdzhouxin/article/details/80070031
[Link 7]: https://blog.csdn.net/xdzhouxin/article/details/80070839