常见排序算法的分析与实现(10种)
Peng's Blog 只记录和技术相关的东西

常见排序算法的分析与实现(10种)

2017-10-15

写在前面

本文章主要涵盖了:

O(n^2)的:选择排序、插入排序、冒泡排序

O(n*logn)的:快速排序、希尔排序、归并排序、堆排序

以及三种线性排序:计数排序、基数排序、桶排序(严格来说这只是一种排序思想,计数属于桶排的一种)

每种排序我都用自己的理解说一遍,没有动图。详细过程可以去百度或者Google。

这里都是从小到大排序,要大到小,其实很好改。

每种算法的代码我都努力缩减到最短了。需要代码的,可以去我的GitHub上面下载:https://github.com/enterprising/arithmetic/tree/master/arithmetic-core/src/main/java/arithmetic4/sort

代码里面所有的交换和比较,都是抽象出来的。为了便于简化代码。

/**
 * 排序用的 工具类,主要包括比较元素大小、交换元素顺序等
 */
public class SortUtil {
    public static boolean less(int v, int w) {
        return v < w;
    }

    public static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}

选择排序

其实这三个基础排序我觉得最关键的是它们的名字。

选择这两个字就已经把它的思想表达地很清楚了。排序过程是:

先从0-n-1里面选一个最小的,然后和第0位交换顺序;

从1-n-1里面选一个最小的,然后和第1位交换顺序;

以此类推.. 直到最后一位,然后结束。

代码:

private static void selectionSort(int[] a) {
  int n = a.length;
  for (int i = 0; i < n; i++) {
    int min = i;
    for (int j = i + 1; j < n; j++) {
      if (SortUtil.less(a[j], a[min]))
        min = j;
    }
    SortUtil.exch(a, i, min);
  }
}

插入排序

插入排序其实更简单,就和平常和朋友玩斗地主时抓牌一样。每次抽一张牌,然后按序插入到手上已有的牌里面。

直到所有的牌抽完,然后就结束了。

代码:

private static void insertSort(int[] a) {
  int n = a.length;
  for (int i = 1; i < n; i++) {
    for (int j = i; j > 0; j--) {
      if (SortUtil.less(a[j], a[j - 1]))
        SortUtil.exch(a, j, j - 1);
    }
  }
}

冒泡排序

分为从前往后,和从后往前两种冒法。时间复杂度是一样的,没啥好讲究的。

这里说一下从后往前冒。

从最后一个元素开始,两两比较,位置不对就交换。这样每次都把最小的送到了最前面。

这方法看上去是和选择排序差不多的,但有本质上的区别:1、选择排序少了很多次交换过程,2、冒泡是稳定的,选择不是。至于什么是稳定的,你就理解成,两个一样的元素,排序后相对位置不变就是稳定的。

代码:

private static void bubbleSort(int[] a) {
  int n = a.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = n - 1; j > i; j--) {
      if (SortUtil.less(a[j], a[j - 1]))
        SortUtil.exch(a, j, j - 1);
    }
  }
}

快速排序

Java内置的就是快排,很多人说遇到排序基本优先用快排(其实还是要看具体场景)。所以就能看出这东西的重要性了吧。

快排的主要思想就是,找出一个中枢值,然后比它小的都放到它的左边,比它大的都放到它的右边。一直递归下去。

最后整个数组就会变成有序。

这里面最核心的是两个东西:1、递归,2、切分算法

关于递归要注意一定要用递归的出口;

关于切分算法:

算法导论上默认是取的最后一个元素。

代码:

private static void sort(int[] a) {
  sort(a, 0, a.length - 1);
}

private static void sort(int[] a, int low, int high) {
  if (high <= low)
    return;  //递归的终点
  int j = partition(a, low, high);
  sort(a, low, j - 1);
  sort(a, j + 1, high);
}


//始终选定数组中的最后一个元素作为枢轴元素,
// 设置指针 i 初始值为数组起始元素索引减1,设置指针 j 由数组下标从低到高扫描整个数组,
// 若遇到的元素小于枢轴元素则 i 自增然后交换 i 数组元素的值和 j 数组元素的值;
// 若遇到的元素大于 枢轴元素则i指针不动,只有j指针自增。此算法的时间复杂度为O(n),空间复杂度为O(1)。
private static int partition(int[] a, int low, int high) {
  int pivot = a[high];
  int i = low - 1;
  for (int j = low; j < high; j++) {
    if (a[j] <= pivot) {
      i++;
      SortUtil.exch(a, i, j);
    }
  }
  SortUtil.exch(a, i + 1, high);
  return i + 1;
}

希尔排序

希尔排序,我的理解就是,这就是一个优化之后的插入排序。

插入排序多考虑一点,就那么厉害了。佩服。

希尔排序和插入排序的不同点主要在于 步长 。所谓的步长就是和前面步长位元素比较。插入排序的步长是1,所以会进行很多次没必要的比较。希尔排序的步长最开始很长,然后步长为1时结束。它省掉了很多次重复的比较。

代码:

private static void shell(int[] a) {
  int n = a.length;
  int h = 1; //步长

  while (h < n / 3)
    h = h * 3 + 1;

  while (h >= 1) {
    // 这里其实就是插入排序了
    for (int i = h; i < n; i++) {
      for (int j = i; j >= h; j = j - h) {
        if (SortUtil.less(a[j], a[j - h])) {
          SortUtil.exch(a, j, j - h);
        }
      }
    }
    h = h / 3;
  }
}

归并排序

这排序将分治和递归用到了极致。。

归并的意思是,将两个合到一起。归并的主要思想就是这个,它首先递归,分成若干个子数组,子数组排序就非常简单了。然后再将两个有序的子数组合并到一起。一直合啊合,最后整个数组就有序了。

这里面有个非常关键的点,就是如何把两个有序的数组合成一个之后,新数组有序。这个见merge()方法的注释。

代码:

private static int[] aux; //归并所需的辅助数组

public static void main(String[] args) {
  int[] a = new int[]{5, 3, 4, 2, 7};
  sort(a);
  for (int i : a) {
    System.out.println(i);
  }
}

public static void sort(int[] a) {
  aux = new int[a.length];
  sort(a, 0, a.length - 1);
}

public static void sort(int[] a, int low, int high) {
  // 将数组a[low..high]排序
  if (high <= low)
    return;
  int mid = low + (high - low) / 2;
  sort(a, low, mid);
  sort(a, mid + 1, high);
  merge(a, low, mid, high);
}

/**
     * 将 a[low..mid] 和 a[mid...high]归并
     *
     * @param a    待合并的数组
     * @param low  起点
     * @param mid  中点
     * @param high 终点
     */
private static void merge(int[] a, int low, int mid, int high) {
  int i = low;
  int j = mid + 1;
  // 将目标数据复制出来,防止造成数据混乱
  for (int k = low; k <= high; k++) {
    aux[k] = a[k];
  }
  //左半边用尽,取右半边的元素
  //右半边用尽,取左半边的元素
  //右半边的小于左半边的元素,取右半边的元素
  //右半边的大于左半边的元素,取左半边的元素
  for (int k = low; k <= high; k++) {
    if (i > mid)
      a[k] = aux[j++];
    else if (j > high)
      a[k] = aux[i++];
    else if (aux[j] < aux[i])
      a[k] = aux[j++];
    else
      a[k] = aux[i++];
  }
}

10万随机数的时候,归并比希尔快1.2倍。。算法4上面说的。

堆排序

要弄懂堆排序,你首先要有堆的概念。这里用的是最大堆。

所谓的最大堆就是指,一棵树,所有的节点的值都大于它所有的子节点的值。这东西只有一个目的,就是让根节点是最大的。

堆排序的过程是:

  • 构建堆(这个只要n/2次就OK,因为叶子结点占了一半,不用再往下了)
  • 将堆顶元素和最后一个元素互换位置;
  • 重新调整第0-n-2,即重新建堆;
  • 重复步骤2、3. 直到堆为空。这时候数组就有序了。

里面最关键的就是堆的建立和调整。这个可以借助代码来理解。

public static void main(String[] args) {
  int[] a = new int[]{5, 2, 4, 6, 7};
  heap(a);
  for (int i : a) {
    System.out.println(i);
  }
}

private static void heap(int[] a) {
  int n = a.length;
  // 这个过程叫做建堆。当前n/2个都调整好了,后面的本来就全是叶子节点。所以这时候已经满足最大/最小堆了
  for (int i = n / 2 - 1; i >= 0; i--) {
    adjust(a, i, n);
  }

  for (int i = n - 1; i > 0; i--) {
    // 将第1个元素与当前最后一个元素交换,保证当前的最后一个位置的元素都是现在的这个序列中最大的
    SortUtil.exch(a, 0, i);
    // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
    adjust(a, 0, i);
  }
}

private static void adjust(int[] a, int i, int n) {
  int child;
  for (; 2 * i + 1 < n; i = child) {
    child = 2 * i + 1; //子节点的位置 = 2*i+1
    // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
    if (child < n - 1 && a[child + 1] > a[child])
      child++;
    // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
    if (a[i] < a[child]) {
      SortUtil.exch(a, i, child);
    } else
      break;
  }
}

计数排序

计数排序是线性排序里面最简单的一种了,但它不使用数据跨度大的情况。它的时间复杂度的 O(N+k);

思路是这样的,它首先找出数组中最大的那个元素max。然后建立一个新的数组,大小为max+1。

然后再遍历原来的数组,以元素的值作为新数组的下标。然后遇到一个,对应下标那元素值就+1。

最后遍历一遍就OK。同时,它还是稳定排序的一种。常用作海量数据的处理,当然。。跨度不能太大。比如0-100分,然后学生100万。这种就刚好适合用计数排序。

代码:

public static void main(String[] args) {
  int[] a = new int[]{5, 2, 4, 6, 7};
  countSort(a);
  for (int i : a) {
    System.out.println(i);
  }
}

private static void countSort(int[] a) {
  int n = a.length;
  // 找到数组中的最大值
  int max = findMax(a);
  int[] result = new int[max + 1];
  for (int i = 0; i < n; i++) {
    result[a[i]]++;
  }
  int k = 0;//存放下标
  for (int i = 0; i <= max; i++) {
    for (int j = 0; j < result[i]; j++)
      a[k++] = i;
  }
}

private static int findMax(int[] a) {
  int max = Integer.MIN_VALUE;
  for (int i : a) {
    if (i > max)
      max = i;
  }
  return max;
}

桶排序

左老师说,桶排序严格来说只是一种排序的思想。

计数排序属于桶排序的一种特殊情况。

所谓的桶排序就是指,将一个大的集合,按照一定大小分发到 n 个桶里面。计数排序是一个数一个桶。其它还有,0-100放一个桶,100-200放一个桶的这种情况。

桶排序最关键的就是映射函数的选择。。选的好,就非常好用。

代码实现(这里是10个桶):

public static void main(String[] args) {
  int[] a = new int[]{5, 2, 4, 6, 7};
  bucketSort(a);
  for (int i : a) {
    System.out.println(i);
  }
}

public static void bucketSort(int[] a) {
  int n = a.length;
  //创建桶
  List<List<Integer>> bucket = new ArrayList<>();
  //初始化桶,这里就当做 10 个吧
  for (int i = 0; i < n; i++) {
    bucket.add(new ArrayList<>());
  }

  // 划分桶
  for (int i = 0; i < n; i++) {
    bucket.get(f(i)).add(a[i]);
  }

  // 对每个桶里的数据进行排序
  for (int i = 0; i < bucket.size(); i++) {
    if (!bucket.get(i).isEmpty())
      Collections.sort(bucket.get(i)); // 调用系统自带的快排
  }

  // 还原数组
  int k = 0;
  for (int i = 0; i < bucket.size(); i++) {
    for (int item : bucket.get(i)) {
      a[k++] = item;
    }
  }
}

private static int f(int x) {
  return x / 10;
}

基数排序

基数排序也是线性排序的一种。。还有,这东西是稳定的。如果不稳定,肯定就会连排序都无法达到了。

它是根据一个数的具体位数的比较来排序的。

先比较个位,放到n个桶里面,全放完后更新原数组的值。

然后比较十位,放到n个桶里面,全放完后再次更新原数组值。

直到最高位比完,结束。

这里有两个注意的点:

1、为啥不先比最高位。。没错,理论上这样是会快一点,但考虑到“重要性”的因素,优先做重要性或者影响性小的操作。

2、每个元素的位数可能不同,所以位数小的要注意在前面补0;

代码(比较长,最后自己写两遍):

public static void main(String[] args) {
  int[] a = new int[]{53, 42, 46, 26, 78};
  radixSort(a);
  for (int i : a) {
    System.out.println(i);
  }
}

public static void radixSort(int[] a) {
  // 获取最大 item 的长度
  int maxBit = getMaxBit(a);
  for (int i = 1; i <= maxBit; i++) {
    List<List<Integer>> buf = distribute(a, i); // 按第 i 位进行分配
    collection(a, buf);  //将 buf 分配到 a 里面 (这时候 a 里面元素的顺序变了)
  }
}

private static void collection(int[] a, List<List<Integer>> buf) {
  int k = 0;
  for (List<Integer> item : buf) {
    for (int num : item) {
      a[k++] = num;
    }
  }
}

/**
     * @param a    待分配的数组
     * @param iBit 要分配的第 i 位
     * @return
     */
private static List<List<Integer>> distribute(int[] a, int iBit) {
  List<List<Integer>> buf = new ArrayList<>();
  for (int i = 0; i < 10; i++) {
    buf.add(new LinkedList<>());
  }
  for (int i = 0; i < a.length; i++) {
    int index = getNbit(a[i], iBit);
    buf.get(index).add(a[i]);
  }
  return buf;
}

/**
     * 获取 item 的第 n-iBit 位的元素
     *
     * @param item 目标数字
     * @param iBit 目标位数
     * @return
     */
private static int getNbit(int item, int iBit) {
  String x = item + "";
  if (x.length() < iBit)
    return 0;
  return x.charAt(x.length() - iBit) - '0';  //这里有两个点,一个是:比较从最低位开始; 还一个是,- '0' 返回正常的数字
}

/**
     * 获取最大位数
     *
     * @param a
     * @return
     */
private static int getMaxBit(int[] a) {
  int max = Integer.MIN_VALUE;
  for (int item : a) {
    int length = (item + "").length();
    if (length > max)
      max = length;
  }
  return max;
}

排序算法稳定性

不稳定的主要有:选择排序、快速排序、希尔排序、堆排序。

选择排序:

​ 直接举例子吧,比如 65631,选最小的,然后1和6换了位置。两个6的相对位置就换了。

快速排序:

​ 64534xxx,中枢元素是6,然后6和中间那4交换位置,这样两个4的相对位置就换了。

希尔排序:

​ 步长大于1,这样非常明显了吧。。可能在某个步长里,把一个数换到另一个没动的数的前面去了。

堆排序:

​ 关键就在于根节点跟最后一个元素交换位置。。这样很明显了吧。

适用情况

(1)若n较小(如n≤50),可采用插入或选择排序

​  当记录规模较小时,插入排序较好;否则因为选择移动的记录数少于直接插人,应选选择排序。

(2)若文件初始状态基本有序(指正序),则应选用插人、冒泡或随机的快速排序为宜;

(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。

​  快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

​  堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

​  若要求排序稳定,则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件,然后再两两归并之。因为插入排序是稳定 的,所以改进后的归并排序仍是稳定的。

(4)元素的跨度比较小,然后n又比较大的时候,用计数排序或者桶排序会很好。


Comments

评论功能暂停使用,如需跟作者讨论请联系底部的GitHub