0
0

【数据结构】八大排序

1.排序的概念及其运用

1.1排序的概念

排序：就是是一串记录，按照其中的某个或默写关键字的大小，递增或者递减的排列起来的操作。

稳定性：假定在带排序的记录排序中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部存在内存中的排序。

外部排序：数据元素太多不嫩恶搞同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2排序应用

排名，商品筛选等。

1.3常见的排序算法

插入排序直接插入排序希尔排序选择排序选择排序堆排序交换排序冒泡排序快速排序归并排序归并排序

2.常见排序算法的实现

1.插入排序

基本思想：有一个有序区间，插入一个数据，依旧保持他有序。

1.1单趟插入排序

假设n-1个数据是有序的，第n个数据是要插入的数据，那么从后往前进行插入，原因：挪动数据比较方便。

画图：

void InsertSort(int* a, int n)
{
    //记录倒数第二个数据的下标
    int end = n - 2;
    //记录最后一个数据
    int tmp = a[end + 1];
    while (end>=0)
    {
        if (tmp < a[end])
        {
            //将数据往后挪一位
            a[end+1] = a[end];
            end--;
        }
        else
            break;
    }
    //考虑极限情况，插入的数据是最小的，那么end就为-1.
    a[end+1] = tmp;
}

多趟即可实现完全版插入排序

void InsertSort(int* a, int n)
{
    //将单趟做成循环就行
    for (int i = 0; i < n-1; i++)
    {
        //单趟是[0,end]是有序的，end+1是需要处理的元素
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else
                break;
        }
        a[end + 1] = tmp;
    }
}

时间复杂度：O(N^2)

最好的情况：顺序有序O(N)

1.2.希尔排序（缩小增量排序）

基本思想：先选定一个整数，吧待排序文件中所有记录分成个组，所有距离为的记录分在同意需内，并对每一组内的记录进行排序。然后，去重复上述分组和排序的工作。当到达1是，所有记录在同一组内排好序。

实现思路：1.预排序 接近有序

2.直接插入排序

预排序：分组排大，大的数更快到后面去，小的数更快到前面，接近有序。

分割：

先进行预排序：

调换三次：

5 1 2 5 6 3 8 7 4 9

代码延续插入排序的基本思路，只是“1”变为了gap

//手动规定gap = 3
    int gap = 3;
    //for循环控制走三次
    for (int j = 0; j < gap; j++)
    {
        //单趟选择，但要走三次
        for (int i = j; i < n - gap; i += gap)
        {
            int end = i;
            int tmp = a[i + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }
    }

2.gap = 1时，进行一次插入排序即可。

考虑优化一下代码，使得不用调用插入排序就能直接实现希尔排序。

思路：官方并未给gap任意的限制，可知gap的取值并不能完全影响希尔排序。

所以考虑用数学的方法，手动规划让gap最后一步等于1，完成最后的插入排序。

一般情况下gap = 3为最佳。

gap = gap / 3 + 1;

代码：

    //gap的取法没有啥具体的讲究，可随意取。
    int gap = n;
    while (gap > 1)
    {
        //保证最后一次gap==1，完成一次完整的插入排序。
        gap = gap / 3 + 1;
        //因为代码中出现了 end+gap 所以 判断部分就必须防止数组越界，为n-gap
        for (int i = 0; i < n - gap; i++)
        {
            //这里采用的是三路各走一步的方式来做，
            //将三个阶段的第一小阶段先走
            //插入排序的老套路
            int end = i;
            int tmp = a[i + gap];
            while (gap >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }

    }
}

总结：

**1.**希尔排序是堆插入排序的优化。

*2.当gap>1时都是预排序，目的是让数组更接近有序。当gap == 1*时，数组几乎就是有序的了，这样就会很快。

整体而言，可以达到优化结果。

3.希尔排序的时间否咋读不太好计算，因为gap的取值方法很多，所以希尔排序的时间复杂度是不确定的。

4.稳定性：不稳定。

3.选择排序

3.1基本思想

每一次从待排序的元素中选出最小的（或最大）一个元素，存放在序列的起始位置，知道全部待排序的数据元素排完。

在学习C语言的时候，就会介绍选择排序，现在选有的基础上进行优化，同时进行最大最小元素的处理。

方法：采取双下标的方法，定义left 和 right maxi 和 mini 开始做比较，若是a[i]>a[maxi]

交换，a[i]<a[mini] 交换,知道left>=right.

这里存在一个小问题，代码中会有说明。

void SelectSort(int* a, int n)
{
    //以升序为例
    //左右，记录下标
    int left = 0, right = n - 1;
    while (left < right)
    {
        int maxi = left;
        int mini = left;
        //遍历，在[left+1,right]中找到最大值，最小值的下标
        for (int i = left + 1; i <= right; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
            //交换最小值和最左边值的位置
            Swap(&a[mini], &a[left]);
            //如果left 和 maxi 重合，修正即可
            //在遍历过程中，前面交换了，再次进行交换2就是得最小值标
            //调换到right位置。
            if (left == maxi)
                maxi = mini;
            //交换最大值和最右边的值的位置
            Swap(&a[maxi], &a[right]);
        left++;
        right--;
    }
}

总结：

**1.**直接选择排序思路非常好了解，但效率低，实际操作很少使用。

*2.时间复杂度：O(N^2)*

*3.空间复杂度：O(1)*

**4.**稳定性：不稳定。

4.堆排序

堆排序是在选择排序的基础上，以二叉树为载体，构建的一种效率更优的一种算法。

void AdjustDown(int* a, size_t size, size_t root)
{
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        //选出左右孩子中较大的那一个
        if (child + 1 < size && a[child] < a[child + 1])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}
void HeapSort(int* a, int n)
{
    //向下调整建堆,升序建大堆,并把最大的值放在根结点
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n,i);
    }
    
    //循环调整堆
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }    
}

更多关于堆排序：【数据结构】二叉树--堆排序_福地洞天的博客-CSDN博客https://blog.csdn.net/weixin_61932507/article/details/124082628

总结：

**1.**效率高

*2.时间复杂度：O(NlonN)**

*3.空间复杂度：O(1)*

**4.**稳定性：不稳定

交换排序

冒泡排序

冒泡是第一个学习的排序，所以可以直接整完全版的。

冒泡基本思想：相邻两个元素比较，交换位置。

交换函数：

void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void BubbleSort(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        //因为是两两比较，所以当单趟走完exchang未发生变化，就能说明，
        // 相邻的两个数符合“规则”。
        //单趟
        for (int j = 1; j < n - i; j++)
        {
            if (a[j] < a[j - 1])
            {
                Swap(&a[j], &a[j - 1]);
            }
        }
    }
}

优化：

void BubbleSort(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        int exchange = 0;
        //因为是两两比较，所以当单趟走完exchang未发生变化，就能说明，
        // 相邻的两个数符合“规则”。
        //单趟
        for (int j = 1; j < n - i; j++)
        {
            if (a[j] < a[j - 1])
            {
                exchange = 1;
                Swap(&a[j], &a[j - 1]);
            }
        }
        if (exchange == 0)
            break;
    }
}

虽然优化了，但由于冒泡算法时间复杂度为O(N^2),所以在处理较多数据时，还是远远不如其他排序，但它好理解。

6.快速排序

快速排序是一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某一个元素作为基准值，

按照该排序码将待排序集合分割成两个子序列，做子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，

然后最左右序列重复该过程，知道所有元素都排列在相应的位置上。

将区间按照基准值划分为左右两半部分的常见方式有：

1.hoare版本

单趟排序：选出一个key，一般是第一个或者最后一个数。

要求：左边的值都比key小，右边的值都比key大。

如何保证相遇的位置比key小？

右边先走保证。

R先定下来，L走去遇到R

相遇的位置是比key小的。

刚交换完，R先走，R没有找到比key小的直接跟L相遇。

相遇点而为之也是比key小的。

也就是说，key的位置在哪完全是随机的，比不是意味着key必须在中心位置。

先将单趟排序完成：

//单趟的目的是，keyi左边都是小于a[keyi]的数据，右边都是大于a[keyi]的数据
int PartSort1(int* a, int left, int right)
{
    int midi = GetKeyi(a, left, right);
    Swap(&a[left], &a[midi]);
    //规定keyi，一般为第一个数或者最后一个数。
    
    int keyi = left;
    while (left < right)
    {
        //循环，找到不符合的那个数据的下标
        while (a[keyi] <= a[right] && left < right)
        {
            right--;
        }
        while (a[keyi] > a[left] && left < right)
        {
            left++;
        }
        //交换数据
        Swap(&a[left], &a[right]);
    }
    //此时将keyi的位置与left交换
    
    Swap(&a[left], &a[keyi]);
    return keyi;
}

行完单趟排序后，key放在了合适的位置，可以采取分治递归的思想，将其完成排序。

void QuickSort(int* a, int begin, int end)
{
    if (begin >= end)
        return;
    //先单趟排序,找到keyi
    int keyi = PartSort1(a, begin, end);

    //递归分治
    //数据现在被分为[begin,keyi-1] keyi [keyi+1,end]
    //对[begin,keyi-1] 和 [keyi+1,end] 进行处理排序
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

2.挖坑法

将一端第一个数存放在临时变量中，构成第一个坑位。从另一端开始寻找符合关系的数，

去占领上一个数的坑位。依次循环，当left>=right时，将临时变量放入最后的坑位。

画图：

right--

找到比key小的值，将值放入pit中，同时更新pit

left左移，寻找比key大的值

当left = right时，循环结束，key扔进pit即可

代码：

//挖坑法
int PartSort2(int* a, int left, int right)
{
    //找好坑位。
    int key = a[left];
    //key定在左边
    int pit = left;
    //从右找小于key的数
    while (left < right)
    {                           //防止a[right]和key相等，导致陷入死循环
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[pit] = a[right];
        pit = right;
        while (left < right && a[left] < key)
        {
            left++;
        }
        a[pit] = a[left];
        pit = left;
        
    }
    a[pit] = key;
    return pit;
}

对比hoare版本：

1.比hoare版本好理解。

2.本质上没啥大的差别。

3.前后指针版本

思路：定义两个指针，prev 和 cur ，cur找比key小的数，prev找比key大的数，

找到后，两者交换位置，循环结束后，a[keyi] 与 a[prev]交换值。

画图：

int PartSort3(int* a, int left, int right)
{
    //以左边为例
    int keyi = left;
    int prev = left, cur = left + 1;
    while (cur <= right)
    {      // 找小                    //用于规避无用的交换操作
        if (a[cur] < a[keyi] && a[++prev] != a[cur])
        {
            Swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}

快速排序的时间复杂度

最好的情况：每次都是接近或者就是二分的，时间复杂度：O(N*logN)

最坏的情况：每次所分的都是最小值或者最大值，相当于二分失效了，时间复杂度：O(N^2).

相差还是蛮大的。

优化一：

考虑对快速排序进行优化，使得其时间复杂度更加靠近O(N*logN)

可以发现：出现最坏的情况还是和keyi的取向有极大的关系，考虑去取区间内的某一个随机值。

可以考虑取其a[left] a[right] a[midi] 的中间值，来实现一定的“伪随机”。

三者比较取其中，代码：

int GetKeyi(int* a,int left, int right)
{
    int midi = left + (right - left) / 2;//防止溢出
    //比较，选出中间的一个
    if (a[left] < a[right])
    {
        if (a[right] < a[midi])
            return right;
        else if (a[midi] < a[left])
            return left;
        else
            return midi;
    }
    else //a[left]>=a[right]
    {
        if (a[midi] < a[left])
            return midi;
        else if (a[midi] > a[left])
            return left;
        else
            return right;
    }

}

在原有代码中稍作修改，就可以继续使用原有代码了。

因为返回的是下标，那么考虑将返回下标的值与最初设立的下标的数进行交换，就不会打乱原有的代码。

优化二：不痛不痒，相较于优化一，优化的情况不是太大。

递归是要调用栈帧的，当数据趋于有序，接近有序的时候，可以考虑减少栈帧的调用，采用插入排序的方法，

实现最后一步。希尔排序不是也延续了这种思想吗？

//优化二：递归调用可以减少部分，以10为界
void QuickSort(int* a, int begin, int end)
{
    if (begin >= end)
        return;
    if (end - begin + 1 < 10)
    {
        InsertSort(a + begin, end - begin + 1);
    }
    //先单趟排序,找到keyi
    int keyi = PartSort1(a, begin, end);
    //int keyi = PartSort2(a, begin, end);
    //int keyi = PartSort3(a, begin, end);
    
    //递归分治
    //数据现在被分为[begin,keyi-1] keyi [keyi+1,end]
    //对[begin,keyi-1] 和 [keyi+1,end] 进行处理排序
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

提升不太明显，但也算有所提升。

快排非递归代码：

递归是创建栈帧的，这里可以通过数据结构中的栈，完成对“递归”的模拟和替代

可以极大的提高代码的运行效率。

//快速排序的非递归版本
/*快速排序递归本质上就是调动函数栈帧，可以考虑用数据结构的栈来完成*/

void QuickSortNone(int* a, int begin, int end)
{
    //建栈
    Stack st;
    StackInit(&st);
    StackPush(&st, begin);
    StackPush(&st, end);
    //当栈不为空就继续。
    while (!StackEmpty(&st))
    {
        int right = StackTop(&st);
        StackPop(&st);
        int left = StackTop(&st);
        StackPop(&st);
        //找keyi
        int keyi = PartSort2(a, left, right);
        //[left,keyi-1] keyi [keyi+1,right]
        //用栈模拟递归,左部分
        if (left < keyi - 1)
        {
            StackPush(&st, left);
            StackPush(&st, keyi - 1);
        }
        //右部分
        if (keyi + 1 < right)
        {
            StackPush(&st, keyi + 1);
            StackPush(&st, right);
        }
    }
    StackDestroy(&st);
}

归并排序

基本思想：是建立在归并操作上的一种由小的算法，采用分治法的一个典型应用。

将已有的子序列合并，得到的完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两者合并成一个有序表，称为二路归并。

思路图：

分解：递归分治完成

归并：将一个集合看做一个数组，实现2个小数组合并成一个数组。这里可以动态申请一个

tmp数组，在tmp数组中完成合并后，再拷贝回原数组。

//归并排序
//建立在归并排序上的一种有序算法，递归分治
//归并排序是完全的二分
//递归版本
void _MergeSort(int* a, int begin, int end, int* tmp)
{
    //递归分治，将数据分割成不可再分的单一元素。
    if (begin >= end)
        return;
    int mid = begin + (end - begin) / 2;
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);
    //[begin, mid] [mid + 1, end] 
    //开始归并，就是给定两个数组，将两个数组合并成一个有序的数组tmp，最后再拷贝进原数组。
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }
    while(begin1<=end1)
        tmp[index++] = a[begin1++];
    while(begin2<=end2)
        tmp[index++] = a[begin2++];
    //拷贝
    memcpy(a + begin , tmp + begin , sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
    //归并排序是需要分治至最小单元后，再进行局部->整体的有序，一般情况下，可以创建临时
    //空间进行辅助。
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
        exit(-1);
    _MergeSort(a, 0, n - 1, tmp);

    //释放空间
    free(tmp);
}

出现了递归，那么就可以考虑一下非递归版本。

考虑递归本身就是将原数组进行分割化为单一元素，那么非递归就可以考虑将这一步循环完成，或者直接完成归并。

直接将原有的数组分割难度有点大，所以考虑反着来，考虑由单一的数到整个数组推广。

前面提及，归并排序使完全的二分，那么，就可以考虑每次乘2来完成“归并”。

归并测试数组：

int a[] = { 9,1,2,5,7,4,8,3,5,6};

思路：排序由单一的一个数到整个数组，间隙gap从1每次*2直到>=n跳出循环。

数组中的数据处理完所有组后，在进行下一个gap的循环归并。所以返回划分比较绕而且比较重要。

先完成第一版：

//非递归版本
//将原先递归分治改为循环来处理
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
        exit(-1);
    memset(tmp, 0, sizeof(int) * n);
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            int index = i;
            //printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
            
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
            while (begin1 <= end1)
                tmp[index++] = a[begin1++];
            while (begin2 <= end2)
                tmp[index++] = a[begin2++];
        }
        memcpy(a, tmp, n * sizeof(int) );
        gap *= 2;
    }
    free(tmp);
}

代码有bug，打印归并数的下标：

可以发现：除了begin1，end1,begin2,end2都有越界的情况。

所以思路错了吗？不，考虑进行手动修正代码即可。

分三种情况：

  • end1越界，手动修改回n-1即可
  • begin2越界，代表[begin2,end2]已经是不存在的区间了，begin2>=end2即可。
  • end2越界，这里考虑将end2 = n-1即可。

//非递归版本
//将原先递归分治改为循环来处理
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
        exit(-1);
    memset(tmp, 0, sizeof(int) * n);
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            int index = i;
            //printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
            //出现了越界访问的问题，要手动修正
            //出现越界的有：end1 begin2 end2
            //end1越界
            if (end1 >= n)
                end1 = n - 1;
            //begin2 越界,[begin2,end2]就不该存在。
            if (begin2 >= n)
            {
                begin2 = -1;
                end2 = -2;
            }
            //只有end2越界，那就将end2修正
            if (end2 >= n && begin2 < n)
            {
                end2 = n - 1;
            }
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
            while (begin1 <= end1)
                tmp[index++] = a[begin1++];
            while (begin2 <= end2)
                tmp[index++] = a[begin2++];
        }
        memcpy(a, tmp, n * sizeof(int) );
        gap *= 2;
    }
    free(tmp);
}

归并排序的特性总结

  1. *归并的缺点在于需要***O(N)**的空间复杂度，归并排序更多是解决磁盘外排序的问题。
  2. 时间复杂度：***O(NlogN)
  3. 空间复杂度：****O(N)
  4. 稳定性：稳定

计数排序

计数偶爱徐又称为鸽巢原理，是对哈希直接地址法的应用变形。

操作步骤：

  • 统计相同元素出现的次数。
  • 根据统计的结果将序列回收到原来的序列中

计数排序分绝对路径和相对路径，本身计数排序对空间的利用率就特别底，绝对路径较相对路径浪费率更高。

所以较为优秀的排序自然就是相对路径下的计数排序。

操作步骤：

  1. 统计相同元素出现的个数。
  2. 根据统计的结构将序列会受到原来的序列中。
//计数排序
void CountSort(int* a, int n)
{
    //确定范围,找到最大值和最小值
    int max = a[0], min = a[0];
    for (int i = 1; i < n; i++)
    {
        if (max < a[i])
            max = i;
        if (min > a[i])
            min = i;
    }
    //计算需要开辟的空间
    int range = max - min + 1;
    int* countA = malloc(sizeof(int) * range);
    //初始化为0
    memset(countA, 0, sizeof(int) * range);

    //相对路径
    for (int i = 0; i < n; i++)
    {
        countA[a[i] - min]++;
    }
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (countA[i]--)
            a[j++] = i + min;
    }
}

时间复杂度：O(N+range)

空间复杂度：O(range)

稳定性：稳定

如有错误还请大佬指正！！！

标签： c语言 数据结构 排序算法
本文转载自: https://blog.csdn.net/weixin_61932507/article/details/124302878
版权归原作者 福地洞天 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】八大排序”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Linux 再入门整理：详解 /etc/fstab 文件

HBase Java API编程-学习记录

【大数据技术基础 | 实验十二】Hive实验：Hive分区

【前端】CSS

python 爬虫 入门 五、抓取图片、视频

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

文章导航