算法排序问题(排序算法包括)

导语：算法 系列一、概述和排序

算法基本是大厂面试必考的。是程序员的必备生存技能。我们的算法系列由浅入深，让大家能真正的学到东西。欢迎大家多多关注，好有动力把这个系列写下去。

一、概述

算法是计算机科学的基础。 本系列主要用java语言，其实明白了原理，实现都很简单。

算法 一直存在于人类的长河中，比如2300多年前的欧几里德算法，找到两个数的最 大公约数:

自然语言描述：计算两个非负整数 p 和 q 的最大公约数:若 q 是 0，则最大公约数为 p。否则，将 p 除以 q得到余数r，p和q的最大公约数即为q和 r 的最大公约数 。

编程语言描述：

Public static int gcd(int p, int q){ if (q == 0) return p; int r = p % q; return gcd(q, r);} 

大多数算法都需要适当的组织数据，也就是 数据结构，数据结构和算法的关系非常密切。

我们首先讲的是一些排序算法。后面还会讲查找、图等。

二、选择排序

首先，找到数组中最小的那个元素，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次，在剩下的元素中 找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

选择排序特点：

运行时间和输入无关。每次找出最小的元素都要扫描一遍数组。

数据移动是最少的。每次交换都会改变两个数组元素的值，交换次数和数组的大小是线性关系。

public class Selection{ public static void sort(Comparable[] a)  { // 将a[]按升序排列 int N = a.length; // 数组长度 for (int i = 0; i < N; i++) { // 将a[i]和a[i+1..N]中最小的元素交换 int min = i; // 最小元素的索引 for (int j = i+1; j < N; j++) if (less(a[j], a[min])) min = j; exch(a, i, min); }  }}

排序轨迹：

命题：对于长度为 N 的数组，选择排序需要大约 N^2/2 次比较和 N 次交换。

证明：如上图，总共有 N 次交换。

(N-1)+(N-2)+...+2+1=N(N-1)/2 ~ N^2/2 次比较。

三、插入排序

通常人们整理桥牌的方法是一张一张的插入。 在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移 动一位。这种算法叫做插入排序。

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给 更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

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

public class Insertion{ public static void sort(Comparable[] a) {  // 将a[]按升序排列 int N = a.length; for (int i = 1; i < N; i++) {  // 将 a[i] 插入到 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); } }}

部分有序的数组 会怎么样呢。

下面是几种典型的部分有序的数组:

数组中每个元素距离它的最终位置都不远;一个有序的大数组接一个小数组;数组中只有几个元素的位置不正确。

插入排序对这样的数组很有效，而选择排序则不然。

每次交换都改变了两个顺序颠倒的元素的位置，相当于减少了一对倒置，当倒置数量为 0 时，排序就完成了。每次交换都对应着一次比较，且 1 到 N-1 之间的每个 i 都可能需要一次 额外的比较(在 a[i] 没有达到数组的左端时)。

命题：对于随机排列的长度为 N 且主键不重复的数组，平均情况下插入排序需要~ N^2/4 次比 较以及~ N^2/4 次交换。最坏情况下需要~ N^2/2 次比较和~ N^2/2 次交换，最好情况下需要 N-1 次比较和 0 次交换。

证明：通过上图可以很容易就得到交换和比较的次数。最坏情 况下对角线之下所有的元素都需要移动位置，最好情况下都不需要。对于随机排列的数组，在 平均情况下每个元素都可能向后移动半个数组的长度，因此交换总数是对角线之下的元素总数 的二分之一。

比较的总次数是交换的次数加上一个额外的项，该项为 N 减去被插入的元素正好是已知的最小 元素的次数。在最坏情况下(逆序数组)，这一项相对于总数可以忽略不计;在最好情况下(数 组已经有序)，这一项等于 N-1。

优化：

要大幅提高插入排序的速度并不难，只需要在内循环中将较大的元素都向右移动而不总是交换 两个元素(这样访问数组的次数就能减半)。

下篇文章我们会给出代码。同时给出 插入排序和选择排序的具体比较等。

该系列借鉴 算法第四版 等书籍。

本文内容由小茜整理编辑！