谈常用的十大排序算法（一）（Java和C++实现）

排序算法是一类非常经典的算法，融入了无数程序大牛的心血。如牛顿所言，正是站在巨人的肩膀上，我们才能望得更远。本系列文章我们就来一起梳理一下排序算法的前世今生。

排序算法大致可分为十类：

选泡插 $O(N^2)$ ：选择排序、冒泡排序、插入排序
快归希堆 $O(NlogN)$ ：快速排序、归并排序、希尔排序、堆排序
桶计基 $O(N)$ ：桶排序、计数排序、基数排序

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

冒泡排序

冒泡排序有三种写法：

一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；

Java实现：

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                swap(arr, j, j + 1);
            }
        }
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    //int temp = arr[i];
    //arr[i] = arr[j];
    //arr[j] = temp;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}

C++实现

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
void bubbleSort(vector<int> &q){
    for(int i = q.size() - 1; i > 0; i--){
        bool flag = false;
        for(int j = 0; j + 1 <= i; j++){
            if(q[j] > q[j+1]){
                swap(q[j], q[j+1]);
                flag = true;
            }
        }
        if(!flag)
            break;
    }
}
 
int main(){
    int n;
    vector<int> q;
    cin >> n;
    for(int i = 0, t; i < n; i++){
        cin >> t;
        q.push_back(t);
    }
    bubbleSort(q);
    for(auto x : q)
        cout << x << ' ';
    cout << endl;
    return 0;
}

经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；

public static void bubbleSort(int[] arr) {
    // 初始时 swapped 为 true，否则排序过程无法启动
    boolean swapped = true;
    for (int i = 0; i < arr.length - 1; i++) {
        // 如果没有发生过交换，说明剩余部分已经有序，排序完成
        if (!swapped) break;
        // 设置 swapped 为 false，如果发生交换，则将其置为 true
        swapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                swap(arr, j, j + 1);
                // 表示发生了交换
                swapped = true;
            }
        }
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    //int temp = arr[i];
    //arr[i] = arr[j];
    //arr[j] = temp;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}

进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

public static void bubbleSort(int[] arr) {
    boolean swapped = true;
    // 最后一个没有经过排序的元素的下标
    int indexOfLastUnsortedElement = arr.length - 1;
    // 上次发生交换的位置
    int swappedIndex = -1;
    while (swapped) {
        swapped = false;
        for (int i = 0; i < indexOfLastUnsortedElement; i++) {
            if (arr[i] > arr[i + 1]) {
                // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                swap(arr, i, i + 1);
                // 表示发生了交换
                swapped = true;
                // 更新交换的位置
                swappedIndex = i;
            }
        }
        // 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
        indexOfLastUnsortedElement = swappedIndex;
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    //int temp = arr[i];
    //arr[i] = arr[j];
    //arr[j] = temp;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}

代码看起来就稍微有点复杂了。最外层的 while 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。
在下一轮比较时，只需比较到上一轮比较中，最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换，必然已经有序了。
当一轮比较中从头到尾都没有发生过交换，则表示整个列表已经有序，排序完成。

稳定性
在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。

时间与空间复杂度
第一种写法的比较次数为 $(n-1)+(n-2)+(n-3)+…+1$ ，总比较次数为 $n^2/2$ ，所以时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(1)$ ;

第二种写法在数组已经有序的情况下比较次数为 $n-1$ ，只需比较一轮即可完成排序，此时时间复杂度为 $O(n)$ ，最坏的情况和第一种写法一样，平均时间复杂度仍是 $O(n^2)$ ，使用的空间最多swapped一个变量，所以空间复杂度为 $O(1)$ ;

第三种写法时间复杂度和第二种写法一样，平均时间复杂度是 $O(n^2)$ ，只是实际运行效率比第二种写法好一些；使用的空间最多 swapped、indexOfLastUnsortedElement、swappedIndex 三个变量，所以空间复杂度为 $O(1)$ 。

选择排序

双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

Java实现：

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
        }
        // 将最小元素交换至首位
        //int temp = arr[i];
       // arr[i] = arr[minIndex];
        //arr[minIndex] = temp;
        arr[i] = arr[i] ^ arr[minIndex];
        arr[minIndex] = arr[minIndex] ^ arr[i];
        arr[i] = arr[i] ^ arr[minIndex];
    }
}

C++实现：

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
void selectionSort(vector<int> &q){
    for(int i = 0; i < q.size(); i++){
        for(int j = i + 1; j < q.size(); j++){
            if(q[i] > q[j])
                swap(q[i], q[j]);
        }
    }
}
 
int main(){
    int n;
    vector<int> q;
    cin >> n;
    for(int i = 0, t; i < n; i++){
        cin >> t;
        q.push_back(t);
    }
    selectionSort(q);
    for(auto x : q)
        cout << x << ' ';
    cout << endl;
    return 0;
}

动画演示

选择排序算法也是可以优化的，既然每轮遍历时找出了最小值，何不把最大值也顺便找出来呢？这就是二元选择排序的思想。
使用二元选择排序，每轮选择时记录最小值和最大值，可以把数组需要遍历的范围缩小一倍。

public static void selectionSort2(int[] arr) {
    int minIndex, maxIndex;
    // i 只需要遍历一半
    for (int i = 0; i < arr.length / 2; i++) {
        minIndex = i;
        maxIndex = i;
        for (int j = i + 1; j < arr.length - i; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                // 记录最大值的下标
                maxIndex = j;
            }
        }
        // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
        if (minIndex == maxIndex) break;
        // 将最小元素交换至首位
        //int temp = arr[i];
        //arr[i] = arr[minIndex];
       // arr[minIndex] = temp;
        arr[i] = arr[i] ^ arr[minIndex];
        arr[minIndex] = arr[minIndex] ^ arr[i];
        arr[i] = arr[i] ^ arr[minIndex];
        // 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
        if (maxIndex == i) maxIndex = minIndex;
        // 将最大元素交换至末尾
        int lastIndex = arr.length - 1 - i;
        //temp = arr[lastIndex];
        //arr[lastIndex] = arr[maxIndex];
        //arr[maxIndex] = temp;
        arr[lastIndex] = arr[lastIndex] ^ arr[maxIndex];
        arr[maxIndex] = arr[maxIndex] ^ arr[lastIndex];
        arr[lastIndex] = arr[lastIndex] ^ arr[maxIndex];
    }
}

在二元选择排序算法中，数组需要遍历的范围缩小了一倍。那么这样可以使选择排序的效率提升一倍吗？

从代码可以看出，虽然二元选择排序最外层的遍历范围缩小了，但 for 循环内做的事情翻了一倍。也就是说二元选择排序无法将选择排序的效率提升一倍。但实测会发现二元选择排序的速度确实比选择排序的速度快一点点，它的速度提升主要是因为两点：
在选择排序的外层 $for$ 循环中， $i$ 需要加到 $arr.length - 1$ ，二元选择排序中 $i$ 只需要加到 $arr.length / 2$
在选择排序的内层 $for$ 循环中， $j$ 需要加到 $arr.length$ ，二元选择排序中 $j$ 只需要加到 $arr.length - i$

稳定性
用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。
不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。

时间与空间复杂度
前文已经说到，选择排序使用两层循环，时间复杂度为 O(n^2)O(n
2
); 只使用有限个变量，空间复杂度 O(1)O(1)。二元选择排序虽然比选择排序要快，但治标不治本，二元选择排序中做的优化无法改变其时间复杂度，二元选择排序的时间复杂度仍然是 O(n^2)O(n
2
)；只使用有限个变量，空间复杂度 O(1)O(1)。

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
重复上述过程直到最后一个元素被插入有序子数组中。

动态演示

Java实现：

public static void insertionSort(int[] arr){
    for (int i=1; i<arr.length; ++i){
        int value = arr[i];//待排序的值
        int position=i;
        while (position>0 && arr[position-1]>value){
            arr[position] = arr[position-1];
            position--;
        }
        arr[position] = value;
    }
}

C++实现：

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
void insertionSort(vector<int> &q){
    for(int i = 1; i < q.size(); i++){
        int t = q[i], j;
        for(j = i - 1; j >= 0; j--){
            if(q[j] > t)
                q[j+1] = q[j];
            else
                break;
        }
        q[j+1] = t;
    }
}
 
int main(){
    int n;
    vector<int> q;
    cin >> n;
    for(int i = 0, t; i < n; i++){
        cin >> t;
        q.push_back(t);
    }
    insertionSort(q);
    for(auto x : q)
        cout << x << ' ';
    cout << endl;
    return 0;
}

插入排序由于O( n2 )的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序。
稳定性
由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。
时间和空间复杂度
插入排序过程需要两层循环，时间复杂度为 $O(n^2)$ ；只需要常量级的临时变量，空间复杂度为 $O(1)$ 。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,294评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,780评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,001评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,593评论 1赞 289
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,687评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,679评论 1赞 294
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,667评论 3赞 415
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,426评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,872评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,180评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,346评论 1赞 345
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,019评论 5赞 340
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,658评论 3赞 323
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,268评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,495评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,275评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,207评论 2赞 352

谈常用的十大排序算法（一）（Java和C++实现）

冒泡排序

选择排序

插入排序

推荐阅读更多精彩内容