目录

一、希尔排序

二、堆排序

三、归并排序

四、快速排序

五、计数排序

六、基数排序

一、希尔排序

思路

希尔排序是属于插入排序先对数组进行预排序使数组相对有序再进行直接插入排序预排序的gap值可以取任意>=1的值经测试效率最高的 gap取值为 gap/3 + 1初始值为size初始的有序度越高的数组进行插入排序的效率就越高

时间复杂度不稳定与数组的初始有序度及gap的计算方法有关介于O(n) ~ O(n^2)

void ShellSort(int* arr, int size) {    int gap = size;    while (gap > 1)     {        gap = gap / 3 + 1;        int i = 0;        for (i = 0; i < size - gap; ++i)         {            int end = i;            int tmp = arr[end + gap];            while (end >= 0 && tmp < arr[end])             {                arr[end + gap] = arr[end];                end -= gap;            }            arr[end + gap] = tmp;        }    }}

思路

将数组建堆输出要升序就建大根堆输出要降序就建小根堆将堆顶的元素与与最后一个元素交换从堆顶进行向下调整调整的范围为size依次递减堆可视为顺序存储的完全二叉树

时间复杂度稳定每次从堆顶向下调整为 lg(n)总复杂度为 n * lg(n)

#include <stdio.h>void Swap(int* arr, int pi, int pj) {    int tmp = arr[pi];    arr[pi] = arr[pj];    arr[pj] = tmp;}//大根堆升序//小根堆降序void AdjustDown(int* arr, int parent, int size) {    int child = parent * 2 + 1;    while (child < size) {        if (child + 1 < size && arr[child + 1] > arr[child])             ++child;        if (arr[parent] < arr[child])         {            Swap(arr, parent, child);            parent = child;            child = parent * 2 + 1;        }        else         {            break;        }    }}void HeapSort(int* arr, int size) {    int parent = (size - 2) / 2;    int i;    for (i = parent; i >= 0; --i)     {        AdjustDown(arr, i, size);   //构建大根堆    }    while (size)     {        Swap(arr, 0, --size);        AdjustDown(arr, 0, size);    }    }

领C++学习资料→点击「链接」

三、归并排序

思路

递归思想将一个数组从中间分为两个子数组分别对两个子数组递归进行归并排序子数组的最小长度为2或3此时设置4个角标begin1end1begin2end2begin1、end1代表左子数组的首尾begin2、end2代表右子数组的首尾同时遍历左右两个子数组对比begin1和begin2对应的值小的存入count数组遍历结束之后将count按地址按字节拷贝到arr空间换时间

时间复杂度稳定递归的复杂度为 lg(n)每个数都会遍历一次总复杂度为 n * lg(n)

void _MergeSort(int* arr, int begin, int end, int* count) {    if (begin >= end)         return;    int mid = (begin + end) / 2;    _MergeSort(arr, begin, mid, count);    _MergeSort(arr, mid + 1, end, count);    int begin1 = begin, end1 = mid;    int begin2 = mid + 1, end2 = end;    int i = begin;    while (begin1 <= end1 && begin2 <= end2)     {        if (arr[begin1] < arr[begin2])             count[i++] = arr[begin1++];        else             count[i++] = arr[begin2++];    }    while (begin1 <= end1)     {        count[i++] = arr[begin1++];    }    while (begin2 <= end2)     {        count[i++] = arr[begin2++];    }    memcpy(arr + begin, count + begin, sizeof(int) * (end - begin + 1));}void MergeSort(int* arr, int size) {    int* count = (int*)malloc(sizeof(int) * size);    int mid = size / 2;    _MergeSort(arr, 0, mid, count);    _MergeSort(arr, mid + 1, size - 1, count);    free(count);    count = NULL;}

思路

递归思想数组取一个关键字key值将比key小的数排在key左边比key大的数排在key右边然后从key值处将数组切分为两个子数组再分别对两个子数组进行快排递归key值取首位、中间位、末尾的中位数提高效率前后指针法先将中位数关键字放在首位后指针的值每次都与首位关键字比较最后返回front为提高效率可在end - begin < n 时使用直接插入排序而放弃快排递归n根据数据量取值

时间复杂度不稳定平均复杂度是O(n * lg(n))

void Swap(int* arr, int pi, int pj) {    int tmp = arr[pi];    arr[pi] = arr[pj];     arr[pj] = tmp;}//取中位数int MidNum(int* arr, int l, int m, int r) {    if (arr[l] < arr[r])     {        if (arr[m] < arr[l])            return l;        else if (arr[m] < arr[r])            return m;        else            return r;    }    else     {        if (arr[m] > arr[l])            return l;        else if (arr[m] > arr[r])            return m;        else            return r;    }}//前后指针法int PtrPrt(int* arr, int begin, int end) {    int mid = (begin + end) / 2;    int keyi = MidNum(arr, begin, mid, end);    Swap(arr, keyi, begin);    int front = begin;    int back = begin + 1;    while (back <= end)     {        if (arr[back] < arr[begin] && ++front != back)             Swap(arr, front, back);        ++back;    }    Swap(arr, begin, front);    return front;}void QuickSort(int* arr, int begin, int end) {    if (begin >= end)         return;    int keyi = PtrPrt(arr, begin, end);    QuickSort(arr, begin, keyi - 1);    QuickSort(arr, keyi + 1, end);}

思路

哈希思想用空间换时间找到arr数组中的最大值max和最小值min创建(max - min + 1)个元素的count数组并置零用于统计arr数组中每个数字的出现次数遍历原数组count[arr[i] - min]++可用count记录原数组中每个数出现的次数再遍历count数组从小到大将数值写入arr数组中完成排序适用于arr数组中的最大值和最小值相差不大的情况

复杂度不稳定介于O(n) ~ O(n^2)

void CountSort(int* arr, int size) {    int min = arr[0], max = arr[0];    int i;    for (i = 0; i < size; ++i)     {        if (arr[i] < min)             min = arr[i];        if (arr[i] > max)             max = arr[i];    }    int* count = (int*)malloc(sizeof(int) * (max - min + 1));    memset(count, 0, max - min + 1);    for (i = 0; i < size; ++i)     {        count[arr[i] - min]++;    }    int j = 0;    for (i = 0; i < max - min + 1; ++i)     {        while (count[i]--)         {            arr[j++] = i + min;        }    }}

思路

为了代码方便使用C++利用队列进行数据收发创建一个队列数组数组大小为10每个元素都是一个队列存储取模为 1 ~ 9 的数从低位到高位进行数据收发完成排序适用于数据位数不高的情况

时间复杂度与最大值的位数K有关K * O(n)所以时间复杂度为O(n)

#include <iostream>#include <queue>using namespace std;#define K 3     //数组中最大数据的位数#define RADIX 10//定义基数queue<int> g_q[RADIX];int GetKey(int val, int k) {    int key = val % 10;    while (k--)     {        val /= 10;        key = val % 10;    }    return key;}void Distribute(int* arr, int left, int right, int k) {    for (int i = left; i <= right; ++i)     {        int key = GetKey(arr[i], k);        g_q[key].push(arr[i]);    }}void Collect(int* arr) {    int j = 0;    for (int i = 0; i < RADIX; ++i)     {        while (!g_q[i].empty())         {            arr[j++] = g_q[i].front();            g_q[i].pop();        }    }}void RadixSort(int* arr, int size) {    for (int i = 0; i < K; ++i)     {        Distribute(arr, 0, size - 1, i);    //分发数据        Collect(arr);       //收集数据    }}