日常算法——插入排序

本贴最后更新于 2555 天前,其中的信息可能已经渤澥桑田

直接插入排序

基本思想:
在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排 好顺序的,现在要把第 n 个数插到前面的有序数中,使得这 n 个数也是排好顺序的。如此反复循环,直到全部排好顺序。

插入排序

代码实现

package Suanfa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 插入排序
 * Created by hushangjie on 2017/11/6.
*/
public class InsertSort {
    public static void sort(int[] arr) {
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            temp = arr[i];
            int j = i -1;
            while (j >= 0 && temp < arr[j]) {

                //往后移动
					   arr[j + 1] = arr[j];
                j--;

            }
            arr[j + 1] = temp;

        }
    }

    public static void main(String[] args) {
        int[] arr = {34, 2, 33, 12, 5, 55};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

特点

插入排序是稳定的,时间复杂度为 O(n^2),待排序数列越接近有序,则算法效率越高。插入排序一般不会单独使用,因为其效率并不高,但是可以结合其他排序一起使用,比如快速排序,因为快速排序最后的数据往往是有序的,此时可以使用插入排序收尾。

  • 算法
    428 引用 • 254 回帖 • 24 关注
  • 排序
    19 引用 • 16 回帖 • 1 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...