动图解析面试常见排序算法（上）

周三不加班

发布于 2019-06-04 18:23:29

4590

发布于 2019-06-04 18:23:29

文章被收录于专栏：程序猿杂货铺

原文 | http://t.cn/E6oruBg

编辑 | 程序猿杂货铺

阅读文本大概需要 10 分钟。

冒泡排序

冒泡排序是一种非常简单的初级排序算法,它每次比较相邻的两个元素,如果顺序错误就进行交换.由于最小的元素是经由不断交换慢慢浮到顶端的,所以叫做冒泡排序.

冒泡排序对 n 个元素需要 O(n^2)次的比较次数,所以它对规模较大的数组进行排序是效率低下的.

运行过程

比较相邻的两个元素,如果第二个元素小于第一个元素,则进行交换(降序则相反).
对每一对相邻元素作同样的工作,从开始第一对直到最后一对.完成后,最后的元素将是最大的元素.
针对所有的元素重复以上步骤,除了最后一个元素.
持续地对每次越来越少的元素重复以上步骤,直到整个数组有序(即没有任何一对元素需要比较).

代码实现

// less与exch函数见完整代码
public static void sort(Comparable[] a) {
 for (int i = 0; i < a.length - 1; i++) {
 for (int j = 0; j < a.length - 1 - i; j++) {
 if (less(a[j + 1], a[j])) {
                exch(a, j, j + 1);
            }
        }
    }
}

完整代码

/**
 * Bubble Sort
 * 
 * @author SylvanasSun
 *
 */
public class Bubble {
 // This class should not be instantiated.
 private Bubble() {
    }
 /**
     * Rearranges the array in ascending order, using the natural order.
     * 
     * @param a
     *            a the array to be sorted
     */
 public static void sort(Comparable[] a) {
 for (int i = 0; i < a.length - 1; i++) {
 for (int j = 0; j < a.length - 1 - i; j++) {
 if (less(a[j + 1], a[j])) {
                    exch(a, j, j + 1);
                }
            }
        }
    }
 /**
     * Rearranges the array in ascending order, using a comparator.
     * 
     * @param a
     *            a the arry to be sorted
     * @param comparator
     *            comparator the comparator specifying the order
     */
 public static void sort(Object[] a, Comparator comparator) {
 for (int i = 0; i < a.length - 1; i++) {
 for (int j = 0; j < a.length - 1 - i; j++) {
 if (less(comparator, a[j + 1], a[j])) {
                    exch(a, j, j + 1);
                }
            }
        }
    }
 // a < b ?
 private static boolean less(Comparable a, Comparable b) {
 return a.compareTo(b) < 0;
    }
 // a < b ?
 private static boolean less(Comparator comparator, Object a, Object b) {
 return comparator.compare(a, b) < 0;
    }
 // exchange a[i] and a[j]
 private static void exch(Object[] a, int i, int j) {
 Object temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 // print array elements to console
 public static void print(Comparable[] a) {
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
        }
    }
 // test
 public static void main(String[] args) {
 String[] s = new Scanner(System.in).nextLine().split("\\s+");
 Bubble.sort(s);
 Bubble.print(s);
    }
}

选择排序

选择排序也是一种非常简单直观的初级排序算法,它的思想是不断地选择剩余元素之中的最小者.

它有以下两个特点.

运行时间与输入模型无关 在选择排序中,为了找出最小元素而扫描一遍数组并不能为下一轮扫描提供什么信息,即使输入是一个已经有序的数组或者是主键全部相等的数组和一个元素随机排列无序的数组所用的排序时间是一样长的.
数据移动是最少的 如果元素处于正确的位置上,则它不会被移动.选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换.

运行过程

首先,找到数组中最小的那个元素
其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素则它就和自己交换)
再次,在剩下的元素中找到最小的元素,将它与数组第二个元素交换位置.如此往复,直到整个数组有序.

代码实现

public static void sort(Comparable[] a) {
 for (int i = 0; i < a.length; i++) {
 int min = i; // the smallest element index
 for (int j = i + 1; j < a.length; j++) {
 if (less(a[j], a[min]))
                    min = j;
                exch(a, i, min);
            }
        }
    }

插入排序

插入排序与选择排序一样,当前索引左边的所有元素都是有序的,但它们的最终位置并不是确定的.它构建了一个有序序列,对于未排序的元素,在有序序列中从后向前扫描,找到相应的位置并插入.

插入排序所需的时间取决于输入模型中元素的初始顺序.当输入模型是一个部分有序的数组时,插入排序的效率会高很多.

因此插入排序对于部分有序的数组十分高效,也很适合小规模的数组.

运行过程

从第一个元素开始,该元素可以认为已是有序的
取出下一个元素,在有序序列中从后向前进行扫描
如果该元素(已排序)大于新元素,则将该元素移到下一位置(右移)
重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤 2~5

代码实现

public static void sort(Comparable[] a) {
 for (int i = 0; i < a.length; i++) {
 // a[i] insert to a[i-1]、a[i-2]、a[i-3]...
 for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

优化

插入排序还有很多可以优化的地方,这里例举两个案例.

采用二分查找法来减少比较操作的次数.

public static void sort(Comparable[] a) {
 int length = a.length;
 for (int i = 1; i < length; i++) {
 // binary search to determine index j at which to insert a[i]
 Comparable 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;
          }
 // insertion 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;
      }
  }

在内循环中将较大的元素都向右移动而不总是交换两个元素(访问数组的次数能够减半)


public static void sort(Comparable[] a) {
 int length = a.length;
 // put smallest element in position to serve as sentinel
 int exchanges = 0;
 for (int i = length - 1; i > 0; i--) {
 if (less(a[i], a[i - 1])) {
              exch(a, i, i - 1);
              exchanges++;
          }
      }
 if (exchanges == 0)
 return;
 // insertion sort with half-exchanges
 for (int i = 2; i < length; i++) {
 Comparable v = a[i];
 int j = i;
 while (less(v, a[j - 1])) {
              a[j] = a[j - 1];
              j--;
          }
          a[j] = v;
      }
  }

希尔排序

希尔排序,也称递减增量排序算法,它是基于插入排序的一种更高效的改进版本.由于插入排序对于大规模乱序数组效率并不高,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端.而希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序.

希尔排序的思想是使数组中任意间隔为h的元素都是有序的,可以说一个h有序的数组就是h个互相独立的有序数组编织在一起组成的一个数组.

代码实现

public static void sort(Comparable[] a) {
 int h = 1;
 while (h < a.length / 3) {
 // h sequence 1,4,13,40,121,364,1093,...
            h = h * 3 + 1;
        }
 while (h >= 1) {
 for (int i = h; i < a.length; i++) {
 // a[i] insert to a[i-h],a[i-2*h],a[i-3*h]...
 for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

小结

限于篇幅，本次文章分了两篇，下篇将会讲解快速排序三向快速排序归并排序堆排序等算法

文中所有源码地址 https://github.com/SylvanasSun/algs4-study

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员啊粥微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度