【数据结构入门精讲 | 第七篇】一文讲清全部排序算法(1)

简介: 【数据结构入门精讲 | 第七篇】一文讲清全部排序算法(1)

在上一篇文章中我们介绍了队列的相关知识点及进行了专项的练习,在这一篇中我们将学习排序算法。


冒泡排序

冒泡排序是一种简单的排序算法。它重复地比较相邻的两个元素,并将它们按照顺序交换,从而将最大(或最小)元素 “浮” 到数组的末尾。这个过程类似于气泡在水中上浮的过程,因而得名 “冒泡排序”。

适用说明

冒泡排序适用于小规模的数组排序。由于其算法复杂度较高(平均时间复杂度为 O(n^2)),当排序规模较大时,性能会明显下降。因此,对于大规模数据集,更推荐使用其他高效的排序算法,如快速排序或归并排序。

冒泡排序的空间复杂度为O(1)

冒泡排序的比较次数恒为n*(n-1)/2

冒泡排序是一种稳定的排序算法,即具有相同值的元素在排序后的相对位置保持不变。

举个例子:对序列28  19  33  30  26  31使用冒泡排序法进行升序排序,进行第一趟冒泡排序后得到的序列为?
冒泡排序是两个两个比较,比如1和2比、2和3比
28>19
所以变为
19  28  33  30  26  31
28<33,所以不动
19  28  33  30  26  31
33>30
所以变为
19  28  30  33  26  31
一直冒泡排序,最终就能得到
19  28  30  26  31  33

本文给出C语言冒泡排序的范例:

#include <stdio.h>
void bubblesort(int a[],int n)//冒泡排序
{
  for(int i=0;i<n-1;i++)
  {
    for(int j=0;j<n-i-1;j++)
    {
      if(a[j]>a[j+1])
      {
        int t=a[j];
        a[j]=a[j+1];
        a[j+1]=t;
      }
    }
  }
}
void print(int a[],int n)
{
  for(int i=0;i<n;i++)
  printf("%d ",a[i]);
  printf("\n");
}
int main()
{
  int a[]={12,11,13,5,6};
  print(a,5);//输出原数组
  bubblesort(a,5);
  print(a,5);
}

插入排序

插入排序(InsertionSort),一般也被称为直接插入排序。

对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而生成一个新的、记录数增 1 的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

适用说明

插入排序的平均时间复杂度也是 O(n^2),空间复杂度为常数阶 O(1),具体时间复杂度和数组的有序性也是有关联的。

插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较 N-1 次,时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的,此时插入排序执行的比较和交换次数为n*(n-1)/2,即最坏的情况是 O(n^2)。

插入排序算法是稳定的。

过程图示

假设前面 n-1(其中 n>=2)个数已经是排好顺序的,现将第 n 个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。

从小到大的插入排序整个过程如图示:

第一轮: 从第二位置的 6 开始比较,比前面 7 小,交换位置。

**第二轮:**第三位置的 9 比前一位置的 7 大,无需交换位置。

**第三轮:**第四位置的 3 比前一位置的 9 小交换位置,依次往前比较。

**第四轮:**第五位置的 1 比前一位置的 9 小,交换位置,再依次往前比较。

依次比较多次后到最后一个元素。

本文给出C语言插入排序的范例:

#include <stdio.h>
void insertsort(int a[],int n)//插入排序
{
  int i,j,key;
  for(int i=1;i<n;i++)
  {
    key=a[i];
    j=i-1;
    while(j>=0&&a[j]>key)
    {
      a[j+1]=a[j];
      j=j-1;
    }
    a[j+1]=key;
  }
}
void print(int a[],int n)
{
  for(int i=0;i<n;i++)
  printf("%d ",a[i]);
  printf("\n");
}
int main()
{
  int a[]={12,11,13,5,6};
  print(a,5);//输出原数组
  insertsort(a,5);
  print(a,5);//输出排序后的数组
}

希尔排序

希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序,因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。

适用说明

希尔排序时间复杂度是 O(n^(1.3-2)),空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ,因此对中等大小规模表现良好,但对规模非常大的数据排序不是最优选择,总之比一般 O(n^2 ) 复杂度的算法快得多。

过程图示

希尔排序目的为了加快速度改进了插入排序,交换不相邻的元素对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap=length/2,缩小增量以 gap = gap/2 的方式,用序列 {n/2,(n/2)/2…1} 来表示。

如图示例:

(1)初始增量第一趟 gap = length/2 = 4

(2)第二趟,增量缩小为 2

(3)第三趟,增量缩小为 1,得到最终排序结果

本文给出C语言希尔排序的范例:

#include <stdio.h>
void shellsort(int a[],int n)//希尔排序
{
  for(int gap=n/2;gap>0;gap/=2)
  {
    for(int i=gap;i<n;i++)
    {
      int t=a[i];
      int j;
      for(j=i;j>=gap&&a[j-gap]>t;j-=gap)
      {
        a[j]=a[j-gap];
      }
      a[j]=t;
    }
  }
}
void print(int a[],int n)
{
  for(int i=0;i<n;i++)
  printf("%d ",a[i]);
  printf("\n");
}
int main()
{
  int a[]={12,11,13,5,6};
  print(a,5);//输出原数组
  shellsort(a,5);
  print(a,5);
}

快速排序

快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。

其思想基本上可以总结为以下几个步骤:

1.选择一个基准值:从待排序的数据中选择一个基准值(pivot),通常选择第一个元素、最后一个元素或者中间的元素。

2.分割:将序列中比基准值小的元素移到基准值的左边,比基准值大的元素移到右边。这个过程称为分割操作。

3.递归排序:对基准值左右两边的子序列分别进行递归排序。即重复上述步骤,直到各个子序列的长度为1,排序完成。

4.合并结果:当所有递归调用结束后,整个序列就变成了有序的序列。

快速排序算法不稳定。

举例

有组记录的排序码为{46,79,56,38,40,84 },采用快速排序(以位于最左位置的对象为基准)得到的第一次划分结果为:
A.{40,38,46,56,79,84}
B.{38,46,56,79,40,84}
C.{38,79,56,46,40,84}
D.{38,46,79,56,40,84}
选A,解析:
46,79,56,38,40,84
l                  r
因为以46为基准,所以l不动,对r进行分析
84大于46,所以不用动
接着r--,对应40
46,79,56,38,40,84
l              r
40小于46,所以将40替换46
40,79,56,38,——,84
l              r
接着l++
40,79,56,38,——,84
    l          r
l对应79,大于40,所以79替换到r的地方
40,——,56,38,79,84
    l          r
接着r--,对应38
40,——,56,38,79,84
    l       r
38小于40,所以38替换到l的地方
40,38,56,——,79,84
    l       r
接着l++ 
40,38,56,——,79,84
        l   r
l对应56,大于40,所以56替换到r处
40,38,——,56,79,84
        l   r
接着r--
此时l与r位置相同
所以不用替换,直接把基准值46填进去就行

快速排序的平均时间复杂度为O(nlogn),最好情况下为O(nlogn),最坏情况下为O(n^2),空间复杂度O(logn)

代码

#include <stdio.h>
// 交换数组中两个元素的值
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
// 对数组进行划分操作
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择数组最后一个元素作为基准值
    int i = (low - 1);  // 初始化较小元素的索引
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准值
        if (arr[j] <= pivot) {
            i++;  // 较小元素的索引加1
            swap(&arr[i], &arr[j]);  // 交换arr[i]和arr[j]
        }
    }
    swap(&arr[i + 1], &arr[high]);  // 将基准值放到正确的位置上
    return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 对数组进行划分
        quickSort(arr, low, pi - 1);  // 递归排序划分的左半部分
        quickSort(arr, pi + 1, high);  // 递归排序划分的右半部分
    }
}
// 测试快速排序算法
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

桶排序

桶排序是一种线性时间复杂度的排序算法,适用于元素服从均匀分布的情况。

它的基本思想是将待排序的元素划分为若干个相同大小的区间(桶)。然后对每个桶内的元素进行排序,最后按照桶的顺序依次将各个桶中的元素合并起来。

首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中,那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn;

根据mx和mn确定每个桶所装的数据的范围 size,有

size = (mx - mn) / n + 1,n为数据的个数,需要保证至少有一个桶,故而需要加个1;

求得了size即知道了每个桶所装数据的范围,还需要计算出所需的桶的个数cnt,有

cnt = (mx - mn) / size + 1,需要保证每个桶至少要能装1个数,故而需要加个1;

求得了size和cnt后,即可知第一个桶装的数据范围为 [mn, mn + size),第二个桶为 [mn + size, mn + 2 * size),…,以此类推

因此步骤2中需要再扫描一遍数组,将待排序的各个数放进对应的桶中。

对各个桶中的数据进行排序,可以使用其他的排序算法排序,例如快速排序;也可以递归使用桶排序进行排序;

将各个桶中排好序的数据依次输出,最后得到的数据即为最终有序。

桶排序的时间复杂度为O(n+k),其中k是桶的数量。相当于桶排序的时间复杂度为O(n)

例如,待排序的数为:3, 6, 9, 1

1)求得 mx = 9,mn = 1,n = 4

size = (9 - 1) / n + 1 = 3

cnt = (mx - mn) / size + 1 = 3

2)由上面的步骤可知,共3个桶,每个桶能放3个数,第一个桶数的范围为 [1, 4),第二个[4, 7),第三个[7, 10)

扫描一遍待排序的数,将各个数放到其对应的桶中,放完后如下图所示:

3)对各个桶中的数进行排序,得到如下图所示:

4)依次输出各个排好序的桶中的数据,即为:1, 3, 6, 9

可见,最终得到了有序的排列。

代码

#include <stdio.h>
#include <stdlib.h>
// 桶排序函数
void bucketSort(int arr[], int n) {
    // 计算数组中最大值和最小值
    int max_val = arr[0];
    int min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }
    // 根据最大值和最小值计算桶的数量
    int bucket_num = (max_val - min_val) / n + 1;
    int** buckets = (int**)malloc(bucket_num * sizeof(int*));
    for (int i = 0; i < bucket_num; i++) {
        buckets[i] = (int*)malloc(n * sizeof(int));
    }
    // 将数组中的元素分配到对应的桶中
    for (int i = 0; i < n; i++) {
        int index = (arr[i] - min_val) / n;
        buckets[index][i] = arr[i];
    }
    // 对每个桶中的元素进行排序
    for (int i = 0; i < bucket_num; i++) {
        int* bucket_arr = buckets[i];
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n - j - 1; k++) {
                if (bucket_arr[k] > bucket_arr[k + 1]) {
                    int temp = bucket_arr[k];
                    bucket_arr[k] = bucket_arr[k + 1];
                    bucket_arr[k + 1] = temp;
                }
            }
        }
    }
    // 将所有桶中的元素按顺序合并起来
    int index = 0;
    for (int i = 0; i < bucket_num; i++) {
        int* bucket_arr = buckets[i];
        for (int j = 0; j < n; j++) {
            if (bucket_arr[j] != 0) {
                arr[index] = bucket_arr[j];
                index++;
            }
        }
    }
    // 释放桶内存空间
    for (int i = 0; i < bucket_num; i++) {
        free(buckets[i]);
    }
    free(buckets);
}
// 测试桶排序算法
int main() {
    int arr[] = {5, 2, 9, 4, 7, 6, 1, 3, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

这篇文章中我们介绍了冒泡排序、插入排序、希尔排序、快速排序及桶排序,在下一篇文章中我们将介绍基数排序、计数排序等算法。

目录
相关文章
|
13天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
|
17天前
|
算法
【算法与数据结构】二叉树(前中后)序遍历2
【算法与数据结构】二叉树(前中后)序遍历
|
5天前
|
存储 机器学习/深度学习 算法
上机实验三 图的最小生成树算法设计 西安石油大学数据结构
上机实验三 图的最小生成树算法设计 西安石油大学数据结构
16 1
|
13天前
|
算法 索引
【算法与数据结构】深入二叉树实现超详解(全源码优化)
【算法与数据结构】深入二叉树实现超详解(全源码优化)
|
13天前
|
存储 算法
【算法与数据结构】深入解析二叉树(二)之堆结构实现
【算法与数据结构】深入解析二叉树(二)之堆结构实现
|
17天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
|
17天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
|
17天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
|
17天前
|
存储 算法 编译器
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
|
21天前
|
存储 算法 搜索推荐
【数据结构】排序算法
【数据结构】排序算法
27 3