美文网首页
选择排序和插入排序

选择排序和插入排序

作者: 世界是一个圆_ | 来源:发表于2018-06-13 22:50 被阅读0次

0.排序中离不开两个方法

排序中最常用的就是比较和互换两个方法,为了简便,在此处提取出来

//交换
public static void exch(int[] arr,int i,int j){
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
//比较
public static boolean less(int x, int y){
  return x < y;
}

1.选择排序

1.1排序方式

1.找到数组中最小的元素,将它和数组的第一个元素交换位置。
2.在剩下的元素中找到最小的元素,将它与第二个元素交换位置
3.重复进行...

1.2实现
  public static void selectionSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (less(arr[j], arr[min])) {
                    min = j;
                }
            }
            exch(arr, i, min);
        }
    }
选择排序轨迹图.png
1.3复杂度
  • 对于长度为N的数组,选择排序需要 N^2/2次比较和N次替换
1.4特点
  • 优点:移动数据是最少的,只需要N次
  • 缺点:花费时间与输入无关,一个升序的数组和一个倒序的数组所花费的时间是一样,因为此特点,下面来讲一下插入排序

2.插入排序

和选择排序不同的是,插入排序所需的时间取决于输入中元素的初始顺序。例如,对一个很大且其中已经有序(接近有序)的数组进行排序比对随机顺序或者逆序的数组进行排序要快的多。

2.1排序方式

索引 i 从1开始,依次比较i左侧相邻的元素(逆序),如arr[i]与arr[i-1], arr[i-1]与arr[i -2]... 如果左侧的小于右侧的,就交换这两个元素,这样就保证了i左侧的元素都是有序的。
下一轮循环时,索引为i+1,由于上一次的排序导致i左侧的数据是有序的,所以只要找出i+1左侧需要交换的位置后,将元素插入此位置,就可以跳入到下一次循环了,即i+2

2.2实现
public static void insertSort(int[] arr){
        
        int len = arr.length;
        
        for(int i = 1; i < len; i++){
            for(int j = i; j > 0 && less(arr[j],arr[j-1]); j--){
                exch(arr,j,j-1);
            }
        }
    }
2.3复杂度
  • 平均情况:N^2 /4次比较和N^2/4次交换
  • 最差情况,如逆序的数组,N^2 /2次比较和N^2/2次交换
  • 最好情况,如顺序的数组,N-1次比较和0次交换
2.4用二分查找优化插入排序

由于插入排序索引左侧的数组是有序的,可以考虑采用二分查找法减少比较次数,代码如下

public static void sort(int[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            int v = a[i];
            int lo = 0, hi = i;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2; 
                if (less(v, a[mid])) hi = mid;
                else                 lo = mid + 1;
            }
            // insetion sort with "half exchanges"
            // (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
            for (int j = i; j > lo; --j)
                a[j] = a[j-1];
            a[lo] = v;
        }
    }

4.对比

选择排序不会访问索引左侧的元素,插入排序不会访问索引右侧的元素,如下图所示:


对比.png

参考资料:https://algs4.cs.princeton.edu/21elementary/

相关文章

  • IOS 常用算法

    一:排序算法 排序方式有插入排序,选择排序和交换排序三种。插入排序有直接插入排序和希尔排序。选择排序有简单选择排序...

  • 排序法

    排序分 内部排序和外部排序 内部排序: 插入排序:{直接插入排序,希尔排序} 选择排序:{简单选择排序,堆排序} ...

  • c算法O(n)^2(一)

    选择排序 插入排序 优化插入排序算法

  • android算法 - 排序

    冒泡排序 选择排序 插入排序 快速排序 堆排序 其中简单排序就是冒泡排序,选择排序和插入排序。继而在分冶合并思想上...

  • Java排序算法

    插入排序 直接插入排序 折半插入排序 交换排序 冒泡排序 快速排序 选择排序 简单选择排序 堆排序 其他排序 二路...

  • 算法

    1.常用的八个基本排序算法 -前言:希尔排序和直接插入排序属于插入排序算法,简单选择排序和堆排序属于选择排序,冒泡...

  • iOS算法

    排序方法 选择排序:直接选择排序、堆排序。 交换排序:冒泡排序、快速排序。 插入排序:直接插入排序、二分法插入排序...

  • JavaScript-常见排序算法实现方法汇总

    常见比较排序1.冒泡排序2.选择排序:简单选择排序和堆排序3.插入排序:直接插入排序和希尔排序4.快速排序5.归并...

  • 九种排序算法(重要!!)

    分类:(九种排序算法) 1、插入排序:直接插入排序、二分插入排序、希尔排序; 2、选择排序:简单选择排序、堆排序 ...

  • 记录几个常见的排序算法

    常见的排序有:快速排序、冒泡排序、希尔排序、选择排序、插入排序、归并排序 冒泡排序: 插入排序: 选择排序: 希尔...

网友评论

      本文标题:选择排序和插入排序

      本文链接:https://www.haomeiwen.com/subject/gxmseftx.html