数据结构——排序算法(冒泡、快速、选择、插入)

avatar
作者
筋斗云
阅读量:0

文章目录

1. 概念

2. 十大排序算法

3. 冒泡排序

4. 冒泡代码实现

5. 快速排序

6. 快速代码实现

7. 选择排序

8. 选择代码实现

9. 插入排序

10. 插入代码实现


1. 概念

排序(Sort)是将无序的记录序列(或称文件)调整成有序的序列。排序算法在计算机科学中非常重要,因为它们可以提高数据检索效率、简化后续算法的复杂性和优化存储结构等。

稳定排序和非稳定排序

  • 稳定排序:如果在排序前,两个相等的元素在原序列中的先后顺序在排序后依然保持不变,那么这种排序算法就是稳定的。插入排序,归并排序,冒泡排序。
  • 非稳定排序:如果排序后,两个相等的元素的先后顺序可能改变,那么这种排序算法就是非稳定的。选择排序,快速排序,堆排序。

例如:

  • 原序列:R1,R2,...,Ri,...,Rj,...,Rn
  • 其中,Ki=Kj 且 i<j(即 Ri 在 Rj 之前)。

在稳定排序中,排序后 Ri 仍在 Rj​ 之前。而在非稳定排序中,Ri​ 和 Rj 的相对位置可能会改变。

内排序和外排序

  • 内排序:如果待排序文件的所有记录都能放入内存中进行排序,那么这种排序称为内排序。内排序速度快,但受限于内存容量,适用于较小的数据集。插入排序、冒泡排序、选择排序、快速排序、归并排序等。
  • 外排序:如果待排序文件的大小超过了内存容量,需要借助外存(如磁盘)进行排序,那么这种排序称为外排序。外排序速度较慢,但适用于大型数据集。通常通过将数据分块读取到内存中排序,然后再将排序后的块合并来实现。比如:归并排序。

排序算法是计算机科学中的基本算法,广泛应用于各种场景。稳定性和适用场景是选择排序算法时的重要考虑因素。内排序适用于小数据集,外排序则适用于大数据集。理解这些概念和性质有助于选择合适的排序算法,从而提高程序的效率和性能。

2. 十大排序算法

排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性
插入排序O(n²)O(n²)O(n)O(1)稳定
希尔排序O(n log² n)O(n²)O(n)O(1)不稳定
选择排序O(n²)O(n²)O(n²)O(1)不稳定
堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定
冒泡排序O(n²)O(n²)O(n)O(1)稳定
快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定
计数排序O(n + k)O(n + k)O(n + k)O(n + k)稳定
桶排序O(n + k)O(n²)O(n)O(n)稳定
基数排序O(n * k)O(n * k)O(n * k)O(n * k)稳定

3. 冒泡排序

冒泡排序是一种简单的排序算法,它通过多次遍历要排序的序列,依次比较相邻元素的大小,并根据需要交换它们的位置,以此将序列中的最大或最小元素逐步移动到序列的一端。其思路如下:

  • 比较相邻元素:

    • 从数组的第一个元素开始,依次比较相邻的两个元素。
  • 交换位置:

    • 如果当前面的元素比后面的元素大(或小,根据升序或降序排序的要求),则交换这两个元素的位置。
  • 一趟遍历完成:

    • 最大(或最小)元素已移至末尾:经过一趟遍历,最大(或最小)的元素会被交换到数组的最后一个位置。
  • 重复进行遍历和交换:

    • 除了最后一个元素,对数组中的所有元素重复执行上述两步。

每次遍历都会将当前未排序部分的最大(或最小)元素放置到合适的位置。

循环遍历:重复执行步骤3和步骤4,直到整个数组都被排序。

示例:

以序列 [3, 1, 5, 4, 2] 为例,进行冒泡排序的过程如下:

  1. 第一趟比较:

    • 比较 313 大于 1,交换位置,序列变为 [1, 3, 5, 4, 2]
    • 比较 353 小于 5,不交换位置,序列不变。
    • 比较 545 大于 4,交换位置,序列变为 [1, 3, 4, 5, 2]
    • 比较 525 大于 2,交换位置,序列变为 [1, 3, 4, 2, 5]
    • 第一趟比较结束,最大元素 5 已经移到序列末尾。
  2. 第二趟比较:

    • 比较 131 小于 3,不交换位置,序列不变。
    • 比较 343 小于 4,不交换位置,序列不变。
    • 比较 424 大于 2,交换位置,序列变为 [1, 3, 2, 4, 5]
    • 第二趟比较结束,次大元素 4 已经移到序列倒数第二位。
  3. 第三趟比较:

    • 比较 131 小于 3,不交换位置,序列不变。
    • 比较 323 大于 2,交换位置,序列变为 [1, 2, 3, 4, 5]
    • 第三趟比较结束,次小元素 3 已经移到正确位置。
  4. 第四趟比较:

    • 比较 121 小于 2,不交换位置,序列不变。
    • 第四趟比较结束,次次小元素 2 已经移到正确位置。

通过上述步骤,整个序列变为 [1, 2, 3, 4, 5],排序完成。

优化:

在实际实现中,可以通过添加一个标志来检测在某一趟遍历中是否发生了交换。如果没有发生交换,则说明数组已经是有序的,可以提前终止排序过程,进一步提升算法效率。

这种算法适用于数据量较小的情况,虽然其时间复杂度为O(n²),但其实现简单,且在某些情况下(如数据量较小或数据已基本有序)依然具有一定的实用性。

4. 冒泡代码实现

#include <stdio.h>  // 冒泡排序函数定义 void bubbleSort(int arr[], int n) {     int i, j;     // 外层循环:控制比较轮数,每次减少一个元素的比较     for (i = 0; i < n - 1; i++) {         // 内层循环:进行元素比较和交换         for (j = 0; j < n - i - 1; j++) {             // 如果前一个元素大于后一个元素,则交换它们             if (arr[j] > arr[j + 1]) {                 int temp = arr[j];                 arr[j] = arr[j + 1];                 arr[j + 1] = temp;             }         }     } }  // 打印数组的函数 void printArray(int arr[], int size) {     int i;     for (i = 0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); }  // 主函数 int main() {     // 定义一个数组     int arr[] = {64, 34, 25, 12, 22, 11, 90};     int n = sizeof(arr) / sizeof(arr[0]);      printf("排序前的数组: \n");     printArray(arr, n);      // 调用冒泡排序函数     bubbleSort(arr, n);      printf("排序后的数组: \n");     printArray(arr, n);      return 0; } 

5. 快速排序

快速排序(Quick Sort)是一种高效的排序算法,由图灵奖获得者Tony Hoare发明,被列为20世纪十大算法之一。其主要特点是通过分治法(Divide and Conquer)来实现对数据的快速排序。下面详细解释快速排序的算法原理和执行过程。

基本思想

快速排序通过以下步骤进行排序:

  1. 选择基准(pivot):从数列中挑选一个元素,称为“基准”。
  2. 分区(partition):重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆放在基准后面。经过分区后,基准值的位置就是它在排序后数组中的最终位置。
  3. 递归排序:递归地对基准值左边的子数组和右边的子数组进行快速排序。

执行步骤

  1. 选择基准

    • 基准可以是数组中的任意一个元素,常见的选择方法有:选择第一个元素、最后一个元素、中间的元素,或者随机选择一个元素作为基准。
  2. 分区操作

    • 将数组中的元素重新排列,所有小于基准的元素放在基准的左边,所有大于基准的元素放在基准的右边。
    • 分区过程中,基准值最终会被放到它的正确位置上,即使得基准左边的所有元素都小于基准,右边的所有元素都大于基准。
  3. 递归排序

    • 对基准左边和右边的子数组分别进行快速排序。
    • 递归的基准情况是子数组的大小为零或一,此时数组已经被排序好了。

优点与缺点

  • 优点

    • 平均时间复杂度为O(n log n),在大多数情况下表现非常好。
    • 空间复杂度为O(log n),需要递归调用栈空间。
    • 属于原地排序算法,空间利用率高。
    • 排序速度非常快,尤其适用于大数据集。
  • 缺点

    • 最坏情况下时间复杂度为O(n^2),如数组已经有序或逆序时。
    • 不稳定排序,可能打乱相同元素的相对顺序。

示例1:

个示例展示了如何使用快速排序算法对数组进行排序。假设有以下数组:

[49, 38, 65, 97, 76, 13, 27, 49]

第一步:选择基准并进行第一次分区

  1. 选择基准 49
  2. 进行分区,将数组分为三部分:小于 49、等于 49 和大于 49 的部分。
[27, 38, 13], 49, [76, 97, 65, 49] 

第二步:递归排序

对每一部分继续递归地进行快速排序:

  • 对左侧 [27, 38, 13] 部分:
    • 选择 27 作为基准。
    • 分区为 [13] 27 [38]
[13] 27 [38] 

对右侧 [76, 97, 65, 49] 部分:

  • 选择 76 作为基准。
  • 分区为 [65] 76 [97]
[65] 76 [97]

组合结果

将所有部分组合起来,得到排序后的数组:

[13, 27, 38, 49, 49, 65, 76, 97] 

示例2:

初始状态

[9, -16, 30, 23, -30, -49, 25, 21, 30] 
  • 第一趟交换

    • 基准值:9
    • 低位指针和高位指针开始交换:
      • 第一次交换后: [-16, 9, 30, 23, -30, -49, 25, 21, 30]
      • 第二次交换后: [-16, -49, 30, 23, -30, 9, 25, 21, 30]
      • 第三次交换后: [-16, -49, -30, 23, 9, 30, 25, 21, 30]
  • 第二趟交换

    • 基准值:-30
    • 低位指针和高位指针开始交换:
      • 第一次交换后: [-49, -30, -16, 23, 9, 30, 25, 21, 30]
      • 第二次交换后: [-49, -30, -16, 23, 9, 30, 25, 21, 30]
  • 分割完成

    • 将数组分为左侧和右侧分别继续递归排序,最终达到有序。

6. 快速代码实现

#include <stdio.h>  // 快速排序入口函数 void quickSort(int arr[], int size) {     subSort(arr, 0, size - 1); }  // 辅助排序函数,递归实现 void subSort(int arr[], int start, int end) {     if (start < end) {         int base = arr[start];  // 选择基准值为第一个元素         int low = start;        // 初始化低位索引         int high = end + 1;     // 初始化高位索引          while (1) {             while (low < end && arr[++low] <= base);  // 从左向右扫描,找到第一个大于基准值的元素             while (high > start && arr[--high] >= base);  // 从右向左扫描,找到第一个小于基准值的元素              if (low < high) {                 int temp = arr[low];  // 交换找到的两个元素                 arr[low] = arr[high];                 arr[high] = temp;             } else {                 break;  // 如果low和high相遇,则退出循环             }         }         int temp1 = arr[start];  // 将基准值交换到正确的位置         arr[start] = arr[high];         arr[high] = temp1;                  subSort(arr, start, high - 1);  // 递归排序基准值左边的子数组         subSort(arr, high + 1, end);    // 递归排序基准值右边的子数组     } }  // 打印数组函数 void printArray(int arr[], int size) {     for (int i = 0; i < size; i++) {         printf("%d ", arr[i]);     }     printf("\n"); }  // 主函数 int main() {     int arr[] = {9, -16, 40, 23, -30, -49, 25, 21, 30};     int length = sizeof(arr) / sizeof(int);      // 排序前遍历数组     printArray(arr, length);      // 调用快速排序     quickSort(arr, length);      // 排序后遍历数组     printArray(arr, length);      return 0; } 

7. 选择排序

选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是不断地从未排序的部分中选择最小(或最大)的元素,放到已排序部分的末尾,从而不断扩大已排序的部分,直到整个数组有序。选择排序的时间复杂度为O(n^2),空间复杂度为O(1),是一种不稳定的排序算法。

算法原理

  1. 初始状态:整个数组为未排序部分。
  2. 找到最小值:从未排序部分中找到最小(或最大)的元素。
  3. 交换位置:将找到的最小(或最大)元素与未排序部分的第一个元素交换位置。
  4. 已排序部分增加:将已排序部分扩大一个元素,未排序部分减小一个元素。
  5. 重复步骤2-4:对未排序部分重复上述步骤,直到未排序部分为空,排序完成。

优点

  1. 简单易懂:选择排序的算法原理非常直观,容易理解和实现,特别适合教学和初学者学习。

  2. 不需要额外空间:选择排序是就地排序(in-place sorting)算法,只需要常数级别的额外空间,空间复杂度为O(1)。

  3. 适合小规模数据:对于小规模数据集,选择排序的实现简单且运行时间可以接受。

缺点

  1. 时间复杂度高:选择排序的时间复杂度为O(n^2),不适合大规模数据集,随着数据量的增加,性能会显著下降。

  2. 不稳定:选择排序是不稳定的排序算法,即相同元素的相对顺序在排序过程中可能会被改变。

  3. 数据交换多:在选择排序过程中,每次找到最小值后都会进行数据交换,如果数组元素较多且数据量较大,频繁的数据交换会影响性能。

过程示例:

初始数组

[29, 10, 14, 37, 14] 

 第一轮:找到最小值10,交换29和10。

[10, 29, 14, 37, 14] 

第二轮:找到最小值14,交换29和14。

[10, 14, 29, 37, 14] 

第三轮:找到最小值14,交换29和14。

[10, 14, 14, 37, 29] 

第四轮(最终结果):找到最小值29,交换37和29。

[10, 14, 14, 29, 37] 

选择排序通过不断选择未排序部分的最小值,将其移动到已排序部分的末尾,逐步完成整个排序过程。虽然选择排序的时间复杂度较高,但其实现简单,适用于数据量较小或对稳定性要求不高的场景。

8. 选择代码实现

#include <stdio.h>  // 选择排序函数 void selectionSort(int arr[], int size) {     // 外层循环,逐步扩大已排序部分     for (int i = 0; i < size - 1; i++) {         // 假设当前位置i为最小值索引         int minIndex = i;         // 内层循环,从i+1位置开始寻找未排序部分的最小值         for (int j = i + 1; j < size; j++) {             if (arr[j] < arr[minIndex]) {                 // 更新最小值索引                 minIndex = j;             }         }         // 交换当前位置i和找到的最小值位置minIndex的元素         if (minIndex != i) {             int temp = arr[i];             arr[i] = arr[minIndex];             arr[minIndex] = temp;         }     } }  // 打印数组函数 void printArray(int arr[], int size) {     for (int i = 0; i < size; i++) {         printf("%d ", arr[i]);     }     printf("\n"); }  // 主函数 int main() {     // 定义并初始化一个待排序的数组     int arr[] = {29, 10, 14, 37, 14};     int length = sizeof(arr) / sizeof(arr[0]);      // 排序前遍历数组并打印     printf("排序前的数组: ");     printArray(arr, length);      // 调用选择排序函数对数组进行排序     selectionSort(arr, length);      // 排序后遍历数组并打印     printf("排序后的数组: ");     printArray(arr, length);      return 0; } 

9. 插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理类似于我们整理扑克牌的过程,从左到右逐步扩大已排序的部分,将当前元素插入到已排序部分的适当位置,直到整个序列有序。

算法原理

  1. 初始状态:已排序部分只有第一个元素。
  2. 从第二个元素开始:逐一取出元素,将其插入到已排序部分的适当位置。
  3. 重复步骤2:直到所有元素均插入到已排序部分。

插入排序的优缺点

优点

  • 算法简单,易于理解和实现。
  • 对于少量元素的数组或几乎已经排好序的数组,插入排序非常高效。
  • 是稳定排序算法,保证相等元素的相对位置不变。

缺点

  • 对于大规模数组,插入排序的效率较低,时间复杂度为O(n^2)。

插入排序的步骤示例

初始状态

[5, 2, 9, 1, 5, 6] 
  • 已排序部分:[5]
  • 第二个元素2

    • 将2插入到已排序部分 [5] 之前。
[2, 5, 9, 1, 5, 6] 
  • 已排序部分:[2, 5]

  • 第三个元素9

    • 将9插入到已排序部分 [2, 5] 之后。
[2, 5, 9, 1, 5, 6] 
  • 已排序部分:[2, 5, 9]

  • 第四个元素1

    • 将1插入到已排序部分 [2, 5, 9] 之前。
[1, 2, 5, 9, 5, 6] 
  • 已排序部分:[1, 2, 5, 9]

  • 第五个元素5

    • 将5插入到已排序部分 [1, 2, 5, 9] 的适当位置。
[1, 2, 5, 5, 9, 6] 
  • 已排序部分:[1, 2, 5, 5, 9]

  • 第六个元素6

    • 将6插入到已排序部分 [1, 2, 5, 5, 9] 的适当位置。
[1, 2, 5, 5, 6, 9] 

10. 插入代码实现

#include <stdio.h>  // 插入排序函数 void insertionSort(int arr[], int size) {     // 从数组的第二个元素开始,逐个插入到已排序部分     for (int i = 1; i < size; i++) {         int key = arr[i]; // 当前待插入的元素         int j = i - 1;          // 将已排序部分中大于key的元素向后移动         while (j >= 0 && arr[j] > key) {             arr[j + 1] = arr[j];             j = j - 1;         }         arr[j + 1] = key; // 将key插入到正确的位置     } }  // 打印数组函数 void printArray(int arr[], int size) {     for (int i = 0; i < size; i++) {         printf("%d ", arr[i]);     }     printf("\n"); }  // 主函数 int main() {     // 定义并初始化一个待排序的数组     int arr[] = {5, 2, 9, 1, 5, 6};     int length = sizeof(arr) / sizeof(arr[0]);      // 排序前遍历数组并打印     printf("排序前的数组: ");     printArray(arr, length);      // 调用插入排序函数对数组进行排序     insertionSort(arr, length);      // 排序后遍历数组并打印     printf("排序后的数组: ");     printArray(arr, length);      return 0; } 

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!