考研数据结构–排序算法汇总，代码完整可实现-六虎

在考研中，经常会考到各种排序算法，所以总结一下，以便温习。

各类排序的时刻复杂度和空间复杂度概览;

1. 直接刺进排序

其根本操作是将一条记载刺进到已排好的有序表中，然后得到一个新的、记载数量增1的有序表。

特性

时刻复杂度

最好状况便是悉数有序，此刻只需遍历一次，最好的时刻复杂度为 O(n)
最坏状况悉数反序，内层每次遍历已排序部分，最坏时刻复杂度为 O(n^2)
综上，因而直接刺进排序的均匀时刻复杂度为 O(n^2)

2.空间复杂度

辅佐空间是常量
均匀的空间复杂度为：O(1)

3.算法安稳性

判别规范：相同元素的前后次序是否改动
刺进到比它大的数前面，所以直接刺进排序是安稳的

4. 完好可完成代码

#include <bits/stdc  .h>
using namespace std;
// 直接刺进排序
// 其根本操作是将一条记载刺进到已排好的有序表中，然后得到一个新的、记载数量增1的有序表
void InsertSort(int a[], int l) {
    int temp;
    int j;
    // 先看榜首个数，将数组划分为有序和无序部分,榜首个数默许有序。
    for (int i = 1; i < l; i  ) {
        // 取出无序部分的首个，在有序部分从后向前比较，刺进到合适的方位
        if (a[i] < a[i - 1]) {
            temp = a[i];  // temp暂存需求刺进的数
            for (j = i - 1; j >= 0 && temp < a[j]; j--) {
                a[j   1] = a[j];  // 取出原序列中大于暂存的数，往后移
            }  // 循环完毕后，现已找到需求刺进元素的方位
            a[j   1] = temp;  // 将该方位刺进元素
        }
        cout << "第" << i << "次刺进:";
        for (int k = 0; k < l; k  ) {
            cout << a[k] << " ";
        }
        cout << endl;
    }
}
int main() {
    int a[10] = {2, 5, 8, 3, 6, 9, 1, 4, 7};
    int b[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int len = 9;
    InsertSort(a, len);
    return 0;
}

2. 减半刺进排序

特性

时刻复杂度:

减半查找只是减少了比较次数，但是元素的移动次数不变，所以时刻复杂度为O(n^2)

空间复杂度

均匀的空间复杂度也是：O(1)

安稳性：安稳的排序算法

#include <bits/stdc  .h>
using namespace std;
void BInsertSort(int a[], int l) {
    int temp;
    int low, high;
    int m;
    for (int i = 1; i < l; i  ) {
        // 取出无序部分的首个，在有序部分二分查找到方位
        if (a[i] < a[i - 1]) {
            low = 0;
            high = i - 1;
            // 在前面有序的部分进行二分查找
            while (low <= high) {
                m = low   (high - low) / 2;
                if (a[m] > a[i])  // 有序部分的中心数，大于无序部分的首个元素
                    high = m - 1;
                else
                    low = m   1;  // low的方位终究为小于等于a[i]的数
            }
            temp = a[i];  // 暂存需求刺进的元素
            // 遍历，将元素向右移，找到刺进的方位
            for (int j = i; j > low; j--) {
                a[j] = a[j - 1];
            }
            a[low] = temp;  // 在找到的方位进行赋值
        }
        cout << "第" << i << "次刺进：";
        for (int k = 0; k < l; k  ) {
            cout << a[k] << " ";
        }
        cout << endl;
    }
}
int main() {
    int a[10] = {2, 5, 8, 3, 6, 9, 1, 4, 7};
    int b[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int len = 9;
    BInsertSort(a, len);
    return 0;
}

3. 减半查找

也称二分查找，它是一种效率较高的查找办法。但是，减半查找要求线性表有必要选用次序存储结构，并且表中元素按关键字有序摆放。

#include <bits/stdc  .h>
using namespace std;
// 也称二分查找，它是一种效率较高的查找办法。但是，减半查找要求线性表有必要选用次序存储结构，并且表中元素按关键字有序摆放
int BinarySearch(int a[], int low, int high, int target) {
    // 终究low与high会兼并（注意兼并时也要比较），按照规律，此刻high会到low前面，这时才能够确定没有，所以这个循环的条件便是low<=high
    while (low <= high) {
        int mid = low   (high - low) / 2;  // 溢出问题
        cout << "low:" << low << " high:" << high << " mid:" << mid << endl;
        if (a[mid] >
            target) {  // 将两个数进行比较，然后缩小查找范围,。当中心数大于查找数时，往左面找
            high = mid - 1;
        } else if (a[mid] < target) {  // 中心数小于查找数时，往右边找
            low = mid   1;
        } else {  // 持平时，直接返回
            return mid;
        }
    }
    return -1;
}
int main() {
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int len = 9;
    cout << BinarySearch(a, 0, len - 1, 3) << endl;
    return 0;
}

4. 希尔排序

是刺进排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接刺进排序算法的一种更高效的改善版本。

特性 1.时刻复杂度对于这个算法有两个常见成果 O ( n^2 ) O(n^1.5)

2.空间复杂度和直接刺进一样均匀的空间复杂度为：O(1)

3.算法安稳性相同元素的前后次序改动

#include <bits/stdc  .h>
using namespace std;
void ShellSort(int a[], int len) {
    int temp;
    int j;
    int gap = len / 2;
    int index = 0;  // 增加增量
    while (gap)     // 多组
    {
        for (int i = gap; i < len; i  )  // 直接从组内第二个判起
        {
            //  是否需求变，比方榜首步的2和9方位不需求改动
            if (a[i] < a[i - gap]) {
                index  ;
                cout << "第" << index << "次交流" << a[i] << "和" << a[i - gap]
                     << "后：";
                temp = a[i];  // 取出改动值,便是需求交流方位，更大的那个数
                // 需求交流方位的数，小于大的数，还要确保下标大于等于0，
                for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap)  // 找方位
                {
                    a[j   gap] = a[j];  // 右移
                }
                a[j   gap] = temp;  // 刺进
                for (int k = 0; k < len; k  )
                    cout << a[k] << " ";
                cout << endl;
            }
        }
        gap /= 2;
    }
}
int main() {
    int a[10] = {2, 5, 8, 3, 6, 9, 1, 4, 7, 0};
    int b[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int len = 10;
    ShellSort(a, len);
    return 0;
}

5. 冒泡排序

是一种简略的排序算法
由来是由于越小的元素会经由交流慢慢“浮”到数列的顶端（升序或降序摆放），就好像碳酸饮料中二氧化碳的气泡终究会上浮到顶端一样，故名“冒泡排序”。

特性

时刻复杂度

最好状况便是悉数有序，此刻只需遍历一次，因而冒泡排序最好的时刻复杂度为O(n)
最坏状况悉数反序，两重for循环悉数执行，因而冒泡排序的最坏时刻复杂度为 O(n^2)

综上，因而冒泡排序总的均匀时刻复杂度为O(n^2)

空间复杂度

最优的空间复杂度便是不需求借用第三方内存空间，则复杂度为0
最差的空间复杂度便是开端元素逆序排序，每次都要借用一次内存，按照实际的循环次数，为O(n)

均匀的空间复杂度为：O(1)

算法安稳性

相同元素的前后次序是否改动, 由于只交流不同巨细的，所以冒泡排序是安稳的

#include <iostream>
using namespace std;
void BubbleSort(int a[], int l) {
    int ans;
    int temp;
    int index;
    for (int i = l - 1; i >= 1; i--)  // 一重循环，n-1次
    {
        ans = 1;
        for (int j = 1; j <= i; j  )  // 第二个数到未排序数
        {
        //大的往后提
            if (a[j - 1] > a[j]) {
                ans = 0;  // 有未排序的
                //                temp = arr[j];
                //                arr[j] = arr[j   1];
                //                arr[j   1] = temp;
                swap(a[j], a[j - 1]);  // 交流
                cout << "第" <<   index << "次排序:";
                for (int k = 0; k < l; k  )  // 打印数组
                {
                    cout << a[k] << " ";
                }
                cout << endl;
            }
        }
        if (ans)  // 额定标记
            break;
    }
}
int main() {
    int a[20] = {2, 5, 8, 3, 6, 9, 1, 4, 7};
    int b[20] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
    int len = 9, temp;
    BubbleSort(a, len);
    return 0;
}

6. 快速排序

快速排序的根本思想是：经过一次排序行将排序的数据分红两部分，其间一部分的一切数据都比另外一部分的一切数据都要小，然后，再按此办法对这两部分数据分别进行快速排序，直到有序。

算法设计

（1）分化：先从数列中取出一个元素作为基准元素。以基准元素为规范，将问题分化为两个子序列，使小于或许等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。

（2）管理：对两个子序列进行快速排序（递归快速排序）。

（3）兼并：将排好的两个子序列兼并在一起，得到原问题的解。

（4）基准元素的选取：

①：取榜首个元素。(通常选取榜首个元素)

②：取终究一个元素

③：取中心方位的元素

④：取榜首个、终究一个、中心方位元素三者之中位数

⑤：取榜首个和终究一个之间方位的随机数 k (low<=k<=hight)

快速排序的状况比较棘手，在最糟状况下，其运行时刻为O(n2)。在均匀状况下，快速排序的运行时刻为O(nlogn)。


#include <bits/stdc  .h>
using namespace std;
// 快速排序（从小到大）
void quickSort(int left, int right, int arr[]) {
    if (left >= right)
        return;
    int i, j, base, temp;
    i = left,
    j = right;  // 把待排序数组元素的榜首个和终究一个下标分别赋值给i,j，运用i,j进行排序；
                // 将待排序数组的榜首个元素作为岗兵，将数组划分为大于岗兵以及小于岗兵的两部分
    base = arr[left];  // 取最左面的数为基准数
    while (i < j) {
        while (arr[j] >= base && i < j)
            j--;
        while (arr[i] <= base && i < j)
            i  ;
        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 基准数归位
    arr[left] = arr[i];
    arr[i] = base;
    quickSort(left, i - 1, arr);   // 递归左面
    quickSort(i   1, right, arr);  // 递归右边
}
void print(int a[], int n) {
    for (int j = 0; j < n; j  ) {
        cout << a[j] << "  ";
    }
    cout << endl;
}
int main() {
    int a[10] = {8, 1, 9, 7, 2, 4, 5, 6, 10, 3};
    cout << "初始序列：";
    print(a, 10);
    quickSort(0, 9, a);
    cout << "排序成果：";
    print(a, 10);
    return 0;
}

7. 简略选择排序

特性

1.时刻复杂度:O(n^2)

2.空间复杂度:均匀的空间复杂度为：O(1)

3.算法安稳性: 不安稳

可完成代码

#include <bits/stdc  .h>
using namespace std;
void SelectSort(int a[], int len) {
    int k;
    for (int i = 0; i < len - 1; i  )  // 未排序榜首个数
    {
        k = i;                             // 取榜首个数
        for (int j = i   1; j < len; j  )  // 遍历未排序部分
        {
            if (a[j] < a[k]) {
                k = j;  // 取更小
            }
        }
        if (i != k)  // 不在未排序榜首的方位
        {
            swap(a[k], a[i]);
        }
        cout << "第" << i   1 << "次排序后";
        for (int t = 0; t < len; t  )
            cout << a[t] << " ";
        cout << endl;
    }
};
int main() {
    int a[9] = {2, 7, 8, 3, 7, 9, 1, 3, 7};
    int len = 9;
    SelectSort(a, len);
    return 0;
}

8. 堆排序

什么是堆首先堆heap是一种数据结构，是一棵彻底二叉树且满意性质：一切非叶子结点的值均不大于或均不小于其左、右孩子结点的值.
下面经过一组数据阐明堆排序的办法： 9, 79, 46, 30, 58, 49

根本进程：

先将待排序的数视作彻底二叉树(按层次遍历次序进行编号, 从0开端)，如下图:

彻底二叉树的终究一个非叶子节点，也便是终究一个节点的父节点。

终究一个节点的索引为数组长度len-1，那么终究一个非叶子节点的索引应该是为(len-1)/2.也便是从索引为2的节点开端
假如其子节点的值大于其本身的值。则把他和较大子节点进行交流，行将索引2处节点和索引5处元素交流。交流后的成果如图：

建堆从终究一个非叶子节点开端即可

3：向前处理前一个节点，也便是处理索引为1的节点，此刻79>30,79>58,因而无需交流。

向前处理前一个节点，也便是处理索引为0的节点，此刻9 < 79,9 < 49, 因而需交流。应该拿索引为0的节点与索引为1的节点交流，由于79>49. 如图:

假如某个节点和它的某个子节点交流后，该子节点又有子节点，系统还需求再次对该子节点进行判别。如上图由于1处，3处，4处中，1处的值大于3,4处的值，所以还需交流。

牢记： 将每次堆排序得到的最大元素与当前规划的数组终究一个元素交流。

6. 完好可完成代码

#include <bits/stdc  .h>
using namespace std;
/*
           8
      1         14
   3    21    5    7
10
*/
void adjust(int arr[], int len, int index) {
    int left = 2 * index   1;
    int right = 2 * index   2;
    int maxIdx = index;
    if (left < len &&
        arr[left] >
            arr[maxIdx])  // 左面的小标小于总的数组长度，和左面的值小于传入索引的值
        maxIdx = left;    // 记载大值的索引
    if (right < len && arr[right] > arr[maxIdx])
        maxIdx = right;   // maxIdx是3个数中最大数的下标
    if (maxIdx != index)  // 假如maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);  // 递归调整其他不满意堆性质的部分
    }
}
void heapSort(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0;
         i--) {  // 对每一个非叶结点进行堆调整(从终究一个非叶结点开端)
        adjust(arr, size, i);  // i为调整元素的下标
    }
    for (int i = size - 1; i >= 1; i--) {
        swap(arr[0], arr[i]);  // 将当前最大的放置到数组结尾
        adjust(arr, i, 0);  // 将未完成排序的部分继续进行堆排序
    }
}
int main() {
    int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(array, 8);
    for (auto it : array) {
        cout << it << " ";
    }
    return 0;
}

其实整个堆排序进程中, 咱们只需重复做两件事：

建堆(初始化调整堆, 时刻复杂度为O(n);
拿堆的根节点和终究一个节点交流(siftdown, 时刻复杂度为O(n*log n);

因而堆排序全体的时刻复杂度为O(n*log n).

9. 归并排序

归并排序是比较安稳的排序办法。

它的根本思想是把待排序的元素分化成两个规划大致持平的子序列。
假如不易分化，将得到的子序列继续分化，直到子序列中包含的元素个数为1。
由于单个元素的序列本身便是有序的，此刻便能够进行兼并，然后得到一个完好的有序序列。

流程图示例

首先咱们先给定一个无序的数列（42，15，20，6，8，38，50，12），咱们进行兼并排序数列，如下图流程图所示：

思路：

进程一：首先将待排序的元素分红巨细大致相同的两个序列。
进程二：再把子序列分红巨细大致相同的两个子序列。
进程三：如此下去，直到分化成一个元素停止，这时含有一个元素的子序列都是有序的。
进程四：进行兼并操作，将两个有序的子序列兼并为一个有序序列，如此下去，直到一切的元素都兼并为一个有序序列。

解释一下int *；

在C 中，“int * a”通常表明一个整型指针。这是一个指针变量，它存储的是整型变量的地址。

举个比方，假设咱们有一个整数变量int num = 5;，假如咱们声明一个指针变量int * a;并使其指向 num，那么a = &num;或a = num;（此处是取地址运算符的应用）之后，a 就存储了 num 的地址。

之后，咱们能够经过解引证操作符 * 来访问 num 的值，如cout << *a;就会输出 5。由于咱们把 a 理解为存储了 num 的地址，解引证操作符 * 便是取出该地址处存储的值。

此外，假如咱们声明晰一个指针数组，例如int * a[5];，那么 a 就存储了五个整型指针的地址，每个整型指针都能够存储一个整型变量的地址。

#include <bits/stdc  .h>
using namespace std;
void merge(int* a, int low, int mid, int hight)  // 兼并函数
{
    cout << "a: " << *a << endl;
    cout << "low: " << low << endl;
    cout << "mid: " << mid << endl;
    cout << "hight: " << hight << endl;
    // 用 new 请求一个辅佐函数，创建一个新的动态数组，用于存放兼并后的有序数组。
    int* b = new int[hight - low   1];
    int i = low, j = mid   1, k = 0;  // k为 b 数组的小标
    cout << "a[i]: " << a[i] << endl;
    cout << "a[j]: " << a[j] << endl;
    while (i <= mid && j <= hight) {
        if (a[i] <= a[j]) {
            b[k  ] = a[i  ];  // 按从小到大存放在 b 数组里边
        } else {
            b[k  ] = a[j  ];
        }
    }
    while (i <= mid)  // j 序列完毕，将剩下的 i 序列弥补在 b 数组中
    {
        b[k  ] = a[i  ];
    }
    while (j <= hight)  // i 序列完毕，将剩下的 j 序列弥补在 b 数组中
    {
        b[k  ] = a[j  ];
    }
    k = 0;                              // 从小标为 0 开端传送
    for (int i = low; i <= hight; i  )  // 将 b 数组的值传递给数组 a
    {
        a[i] = b[k  ];
    }
    delete[] b;  // 辅佐数组用完后，将其的空间进行开释（销毁）
}
void mergesort(int* a, int low, int hight)  // 归并排序
{
    if (low < hight) {
        int mid = (low   hight) / 2;
        mergesort(a, low, mid);        // 对 a[low,mid]进行排序
        mergesort(a, mid   1, hight);  // 对 a[mid 1,hight]进行排序
        merge(a, low, mid, hight);  // 进行兼并操作
    }
}
int main() {
    int a[9] = {2, 4, 8, 3, 565, 9, 1, 56, 7};
    int n = 9;
    mergesort(a, 0, n - 1);
    cout << "归并排序成果：" << endl;
    for (int i = 0; i < n; i  ) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

10. 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也能够表达字符串（比方名字或日期）和特定格式的浮点数，所以基数排序也不是只能运用于整数。基数排序基于计数排序。

图像进程：

#include <bits/stdc  .h>
using namespace std;
int maxBit(vector<int> vec) {
    int max = vec[0];
    for (int i = 1; i < vec.size(); i  ) {
        if (vec[i] > max)
            max = vec[i];
    }
    int p = 1;
    while (max / 10 != 0) {
        max = max / 10;
        p  ;
    }
    return p;
}
vector<int> countSort(vector<int> vec,
                      int place) {  // 按指定方位的值进行计数排序
    vector<int> temp(vec);          // 暂时数组，存储place方位的值
    vector<int> ordered(vec);       // 排好序的数组放进ordered
    int count[10] = {0};
    for (int i = 0; i < vec.size(); i  ) {
        // 找到每个元素place方位上的数字存在temp中
        temp[i] = (int)(vec[i] / pow(10, place - 1)) % 10;
    }
    for (int i = 0; i < vec.size(); i  ) {
        count[temp[i]]  ;  // 统计数字呈现的频率
    }
    for (int i = 1; i < 10; i  ) {
        // 此刻count中存放着temp中每个数字的索引
        count[i] = count[i]   count[i - 1];
    }
    for (int i = vec.size() - 1; i >= 0; i--) {
        int index = count[temp[i]] - 1;
        count[temp[i]]--;
        ordered[index] = vec[i];
    }
    // cout << "next:" << endl;
    return ordered;
}
void radixSort(vector<int>& vec) {
    // 最长位数是多少，代表要进行几次排序
    int maxbit = maxBit(vec);
    // i为多少，代表按第几位数字比较(从右向左)
    for (int i = 1; i <= maxbit; i  ) {
        vec = countSort(vec, i);
    }
    for (int i = 0; i < vec.size(); i  ) {
        cout << vec[i] << "  ";
    }
}
int main() {
    // vector<int> 是 C  
    // 规范模板库（STL）中的一个模板类，它表明一个动态数组，能够存储整数类型（int）的数据。
    // 具体来说，vector<int>
    // 是一个能够动态改动巨细的数组，它供给了便利的接口来管理数组中的元素。你能够经过
    // push_back() 办法添加元素，经过 erase()
    // 办法删除元素，也能够经过下标访问或许迭代器访问元素。
    vector<int> vec{3, 5, 34, 10, 8, 6,  16, 5, 8, 6, 2, 4, 900, 4, 7,
                    0, 1, 8,  9,  7, 38, 1,  2, 5, 9, 7, 4, 0,   2, 6};
    radixSort(vec);
    return 0;
}

11. 计数排序

当待排序数组中的元素是某个区间的整数时，能够运用计数排序。

其根本思想便是对每一个输入元素，确定出小于x的元素个数。有了这一信息，就能够把x直接放到它在终究输出数组中的方位上。
例如，假如有17个元素小于x，则x就归于第18个输出方位。


/*算法：计数排序*/
#include <cstring>
#include <iostream>
using namespace std;
/***************************************************************************
    1.计数排序法，仅可用于正整数排序。
    2.计数排序的根本思想便是对每一个输入元素x，确定出小于x的元素个数。
    有了这一信息，就能够把x直接放到它在终究输出数组中的方位上。
    3.例如，假如有17个元素小于x，则x就归于第18个输出方位。
    4.当排序的数较为稠密时，所需的辅佐空间较小。
****************************************************************************/
bool ctsort(int A[], int size) {
    if (NULL == A || size < 0)
        return false;
    /*寻找数组A中的最大整数k*/
    int k = A[0];
    for (int i = 1; i < size; i  )
        if (A[i] > k)
            k = A[i];
    k  ;  // 最大整数 1
    // 请求数组，使counts数组最大下标对应A中的最大整数
    int* counts = new int[k];
    int* tmp = new int[size];  // 存放排序的成果
    // 初始化counts数组
    for (int i = 0; i < k; i  )
        counts[i] = 0;
    // counts[i]表明数字i在data中的个数
    for (int i = 0; i < size; i  )
        counts[A[i]] = counts[A[i]]   1;
    // 将counts累计起来，这样counts[i]表明小于等于i的元素个数
    for (int i = 1; i < k; i  )
        counts[i] = counts[i]   counts[i - 1];
    // 从后往前开端数A中元素排序
    for (int i = size - 1; i >= 0; i--) {
        // counts[data[j]]表明当前小于等于数据data[j]的元素个数，counts[data[j]]
        // -1则将其转换为temp中的方位
        tmp[counts[A[i]] - 1] = A[i];
        counts[A[i]] = counts[A[i]] - 1;
    }
    memcpy(A, tmp, size * sizeof(int));
    delete[] counts;
    delete[] tmp;
    return true;
}
int main() {
    int A[] = {9, 3, 7, 4, 5, 2, 1};  // 测试用例1
    // int A[] = {9,3,7,4,5,2,7};//测试用例2
    ctsort(A, 7);
    for (int i = 0; i < 7; i  )
        cout << A[i] << " ";
}

考研数据结构–排序算法汇总，代码完整可实现

1. 直接刺进排序

2. 减半刺进排序

3. 减半查找

4. 希尔排序

5. 冒泡排序

6. 快速排序

7. 简略选择排序

8. 堆排序

9. 归并排序

10. 基数排序

11. 计数排序

相关文章

最佳Chromebooks for Artists

Android-策略模式与状态模式：形似而行不似

Android View绘制原理 – VSync原理之SurfaceFlinger篇

算法| Java的int类型最大值为什么是21亿多？

作者信息