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

作者: 顾子豪 | 来源:发表于2021-07-06 22:47 被阅读0次

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

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

选泡插 $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)$ 。

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

冒泡排序

选择排序

插入排序

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读