排序(1)-简单排序算法

引言

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列，它在大大小小的程序中都有一定的应用。本文先介绍4种简单排序算法，并给出他们各自的改进实现，关于效率的对比将在排序(3)-效率对比一文中给出。本文目的一方面是为了方便后续查阅，另一方面则是希望透过排序这种简单操作，分析各类算法背后引申出的不简单的思想，给出一些个人浅显的见解。
本文设置了一些约定：

• 升序：按从小到大的顺序排序
• 序列：简单抽象为int[] seq的数组表示
• 元素：指序列的原子成分即seq[i]
• 下标：指元素在序列中所处位置
• 交换操作：元素交换是个通用操作，在很多算法中均有用到，其实现如下：

void swap(int[] seq, int x, int y) {
    int tmp = seq[x];
    seq[x] = seq[y];
    seq[y] = tmp;
}

冒泡排序

1.朴素版

冒泡算法逐个比较相邻两元素的大小，一趟下来将最大元素（或最小元素）归位到序列最高下标seq.length-1处，下一趟则归位到下标seq.length-2处。如此往复，直到归位到下标0处。代码如下：

void bubbleSort(int[] seq) {
    for (int i = 0; i < seq.length - 1; i++)
        for (int j = 0; j < seq.length - i - 1; j++)
            if (seq[j] > seq[j + 1])
                swap(seq, j, j + 1);
}

2.改进版-提前结束冒泡

设想一下，假若现在原始序列除了最大元素处在序列前面某一位置（本应在最高下标处），其余元素间已然有序。那么其实只需要进行一趟冒泡将最大元素归位到最高下标处了，即可终止算法。那么如何判断整个序列已经全部有序了呢？我们不需要刻意去比较，顺着算法的思路来就行，即我们可以在每一趟的冒泡过程中用一个标志位flag判断是否发生交换，若发生，则该趟冒泡仍需等待完成，继续进行下一趟排序，直到不发生交换时，结束。代码如下：

void improvedBubbleSort(int[] seq) {
    boolean hasSwaped = false;
    for (int i = 0; i < seq.length - 1; i++) {
        for (int j = 0; j < seq.length - i - 1; j++) {
            if (seq[j] > seq[j + 1]) {
                hasSwaped = true;
                swap(seq, j, j + 1);
            }
        }
        if (hasSwaped == true) // 上轮发生交换
            hasSwaped = false; // 复位
        else
            break;
    }
}

选择排序

1.朴素版

选择排序从序列首部开始，首先考察seq[0]，让其后的所有元素(1 – seq.length-1)逐个与seq[0]比较，比较时保留住最小元素的值与下标，这样一趟下来便筛选出了0 – seq.length-1序列的最大元素下标，让它与seq[0]交换位置，一趟便结束了。下一趟则考察seq[1]，让其后的所有元素(2 – seq.length-1)逐个与seq[1]比较，同上。如此往复，直到考察完seq[seq.length – 2]这一趟结束。乍一看其实选择排序与冒泡的大致原理差不多，都是每趟选出最大元素，但不同的是冒泡排序是相邻交换（即保证了相同大小的元素在排完序后的顺序与排序前的顺序一致），而选择排序则是各种跳跃性神交换，三下五除二就打乱了次序。代码如下：

void selectionSort(int[] seq) {
    int minpos = 0; // 最小值所在下标
    for (int i = 0; i < seq.length; i++) {
        minpos = i;
        for (int j = i + 1; j < seq.length; j++) {
            if (seq[j] < seq[minpos])
                minpos = j; // 更新最小值位置
        }
        // 与子序列头部元素交换
        swap(seq, minpos, i);
    }
}

2.改进版-最大最小元素同步选出

从朴素的选择排序过程可以看出，其实既然每一趟可以筛选出最小值并将其归位于seq[0]处，那为何又不可在一趟过程中同步筛选出最大值并归位于seq[seq.length – 1]呢，这样的话排seq.length / 2趟就可以了。但有一点需要注意，就是假如筛选出的最大元素刚好在子序列的首部，而首部恰好又是要被最小元素交换的，这时如果最小元素先被交换到了首部，那么最大元素就被带到中间去了，而接下来最大元素要交换到子序列尾部时，实质是把最小元素给移到尾部了，这样就错了。类似的特殊情况共三种，即：仅最大元素在首部，仅最小元素在尾部，最大元素在首部且最小元素在尾部，我们要分别调整好交换的先后次序进行特殊处理，而除此外的其他情况任意次序交换即可。代码如下：

void improvedSelectionSort(int[] seq) {
    for (int i = 0; i < seq.length / 2; i++) {
        int minpos = i; // 最小值所在下标
        int maxpos = seq.length - i - 1; // 最大值所在下标
        for (int j = i; j < seq.length - i; j++) {
            if (seq[j] < seq[minpos])
                minpos = j; // 更新最小值位置
            if (seq[j] > seq[maxpos])
                maxpos = j;
        }
        // 交换
        if (minpos == seq.length - i - 1 && maxpos == i) {
            // 最小在尾部，最大在首部，互相交换一次
            swap(seq, minpos, maxpos);
        } else if (minpos == seq.length - i - 1) {
            // 最小在尾部,最大在中间任意处，要优先把最小交换到首部去，以防被最大覆盖
            swap(seq, minpos, i);
            swap(seq, maxpos, seq.length - i - 1);
        } else if (maxpos == i) {
            // 最小在中间任意处, 最大在首部，要优先把最大交换到尾部去，以防被最小覆盖
            swap(seq, maxpos, seq.length - i - 1);
            swap(seq, minpos, i);
        } else {
            // 最小在尾部，最大在首部，任意顺序交换
            swap(seq, minpos, i);
            swap(seq, maxpos, seq.length - i - 1);
        }
    }
}

插入排序

1.朴素版

插入排序最形象生动了，和我们打扑克牌时摸牌、插牌的过程一模一样，只是扑克换成了数字或更抽象的元素。具体过程要说的话则是让原始局部有序的序列，随着一个个新元素的插入，逐步演变成全部有序的过程，即最初先固定住seq[0]让其成为一个局部有序的子序列，然后考察seq[1]及它前面那个有序序列，边挪动元素，边根据元素的大小寻找插入点，找到后就插入，一趟便结束了。下一趟又考察seq[2]及它前面那个有序序列，同理操作。循环往复，直到考察完seq[seq.length – 1]。需要指出的是，插入排序在序列基本有序的时候完全不费吹灰之力，顶多挪动两三趟，然后每次待插入元素都不用挪动比较了，正是它应该待的位置，所以可以让时间复杂度降为O(n)。

void insertSort(int[] seq) {
    for (int i = 1; i < seq.length; i++) {
        int target = seq[i]; // 暂存住
        // 向前寻找插入点
        int j = i - 1;
        while (j >= 0 && target < seq[j]) {
            seq[j + 1] = seq[j];
            j--;
        }
        seq[j + 1] = target;
    }
}

2.改进版-二分插入

朴素的插入排序是边比较查找插入点，边挪动元素。不难看出，元素的挪动次数是没有那么容易减少的了，然而比较查找的次数其实很容易减少，只要采用二分查找，找到应该插入的位置后再逐个挪动元素腾出空间，最后插入即可。改进之处其实就是把查找和挪动操作分离开了，而一旦分离，便可以在查找这里做文章，利用二分查找减少比较次数（因为二分查找有跳跃性，它和挪动操作没法同步进行）。代码如下：

void binaryInsertSort(int[] seq) {
    for (int i = 1; i < seq.length; i++) {
        int target = seq[i]; // 暂存住
        int left = 0;
        int right = i - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target >= seq[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 向前寻找插入点
        int j = i - 1;
        while (j > right) {
            seq[j + 1] = seq[j];
            j--;
        }
        seq[right + 1] = target;
    }
}

3.终极改进版-二路插入

二路插入算法的思想其实并不复杂，只是其中一些取余运算和边界条件比较烦人。这个算法的改进思路其实是从这里得到启发的：在朴素的插入排序过程中，我们一出来就固定住了最左侧元素，即堵死了最左边方向，我们只能一味地“向右”挪动元素为新元素腾出位置，这样的一个弊端很明显，就是万一遇到一个最小元素，我们必须把有序序列中的元素整个都往右挪动一位才能有它的容身之处，这样势必造成比较与移动次数的增多！那怎么优化呢？我们可以新开辟一个空的数组_seq，让它配合一个first和一个last指针（分别指向最小元素和最大元素所在的下标，初始下标均为0）实现类似循环数组即两头、中间均能插入的功能。

• 若待插入元素seq[i] < _seq[first]，就直接让first = (first – 1 + seq.length) % seq.length，然后直接一步到位把seq[i]的值赋给_seq[first]
• 若待插入元素seq[i] > _seq[last]，就直接让last++，然后直接一步到位把seq[i]的值赋给_seq[last]
• 若待插入元素_seq[first] <= seq[i] <= _seq[last]，则按朴素插入排序或二分插入排序进行
  代码如下：

void twoWaysInsertSort(int[] seq) {
    int length = seq.length;
    int[] _seq = new int[length];
    int first = 0;
    int last = 0;
    _seq[first] = seq[0];
    for (int i = 1; i < length; i++) {
        if (seq[i] < _seq[first]) {
            first = (first - 1 + length) % length; // 插入到first之前
            _seq[first] = seq[i];
        } else if (seq[i] >= _seq[last]) {
            last++; // 插入到last之后
            _seq[last] = seq[i];
        } else {
            // 1.采用直接插入
            // int j;
            // for(j = last; seq[i] < _seq[j]; j = (j - 1 + length) %
            // length)
            // _seq[(j + 1 + length) % length] = _seq[j]; //后者覆盖前者
            // _seq[(j + 1 + length) % length] = seq[i];
            // last++;
            // 2.采用二分查找位置后插入
            int low = first;
            int high = last;
            int mid = 0;
            int d = 0; // 高低两端之间的元素个数
            while (low != high) {
                d = (high - low + length) / length;
                mid = (low + d / 2) % length;
                if (seq[i] >= _seq[mid]) {
                    low = (mid + 1 + length) % length;
                } else {
                    high = mid;
                }
            }
            // 向前寻找插入点
            int j = last + 1;
            int k;
            while (j != low) {
                k = (j - 1 + length) % length;
                _seq[j] = _seq[k];
                j = k;
            }
            _seq[low] = seq[i];
            last++;
        }
    }
    // 整理到原序列
    for (int i = 0; i < length; i++) {
        seq[i] = _seq[(first + i) % length];
    }
}

希尔排序

该算法又称缩小增量排序，是插入算法的一种叠加与改进。朴素的插入排序中的有序子序列都是以1为增量的，中间不能跃过任一元素，而希尔排序则可以，它第一轮先设定一个增量gap，然后锁定一个起始位置start，让start + i, start + i + gap, start + i + 2gap, start + i + 3gap,…(0<=i<gap)构成序列i，最终得到gap个序列，然后分别对其使用插入排序。第二轮让gap=gap/2（每次除2），后面原理同上。如此往复，直到最后gap=1，则演变为一般的插入排序，而此时不必担心，因为序列已经基本有序了，所以基本不需要排多少次。所以读到这里，大概就能知道为什么选用插入排序来改进，而不选冒泡和选择了吧，就是因为插入排序在序列基本有序时的时间复杂度是O(n)这个特性，使得它比其他两种算法更具优势！

void shellSort(int[] seq) {
    // 除2增量的希尔排序
    for (int gap = seq.length / 2; gap > 0; gap /= 2) {
        for (int start = 0; start < gap; start++) {
            insertSortWithGap(seq, start, gap);
        }
    }
}
// 插入排序算法(服务希尔排序)
// start: 起始处（默认为0）
// gap: 增量（默认为1）
void insertSortWithGap(int[] seq, int start, int gap) {
    for (int i = start + gap; i < seq.length; i += gap) {
        int target = seq[i]; // 暂存住
        // 向前寻找插入点
        int j = i - gap;
        while (j >= 0 && target < seq[j]) {
            seq[j + gap] = seq[j];
            j -= gap;
        }
        seq[j + gap] = target;
    }
}

结语

简单排序算法本文就只记录了这些，下一章会记录一些更有效率、更有思想的复杂排序算法。