当前位置：首页 > 行业知识 > 数据结构——排序（1）

行业知识

数据结构——排序（1）

2026-11-14 20:57:00 来源：互联网转载

��录

1. 何为排序

1.1 排序的概念

1.2 排序的运用

编辑 1.3 常见的排序算法

2.常见排序算法的实现

2.1 插入排序

2.1.1 直接插入排序

2.2.2 希尔排序

2.2 选择排序

2.2.1 直接选择排序

2.2.2 堆排序

2.3 交换排序

2.3.1 冒泡排序

2.3.2 快速排序

1. 何为排序

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
内部排序：数据元素全部放在内存中的排序。

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

1.2 排序的运用

1.3 常见的排序算法

2.常见排序算法的实现

PS：本篇文章将会讲解插入排序，选择排序以及交换排序，其中交换排序中的快速排序的优化将会在下一篇文章中讲解，本篇文章只会讲解快速排序的Hoare方法，更详细的优化以及其他的一些排序将会在之后的文章中介绍。

2.1 插入排序

2.1.1 直接插入排序

直接插入排序就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

以下是一个动态的展示图：

那么具体应该如何实现呢？

void InsertSort(int* a, int n){int i = 0;for (i = 0; i = 0){            //下一个位置的元素比end所在位置的元素要小，就把end的元素给到下一个位置上if (tmp   测试：
  void InsertSortTest(){int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };int sz = sizeof(a) / sizeof(int);printf("排序前：");PrintArray(a, sz);printf("排序后：");InsertSort(a, sz);PrintArray(a, sz);}
   
    直接插入排序的特性总结：

元素集合越接近有序，直接插入排序算法的时间效率越高

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

2.2.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个gap组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

动态展示如下：

实现方法：

方法一：

void ShellSort(int* a, int n){int gap = n;    //当gap > 1 时，将所有元素分成gap组，当==1的时候，就是直接插入排序while (gap > 1){        //gap没有专门的给法，通常采用 /3+1的方式        //但是无论采用什么方法都要保证最后一次进循环的时候gap == 1gap = gap / 3 + 1; int i = 0;        //这里采用的是一组一组比较的形式for (i = 0; i = 0){if (tmp   方法二：
  void ShellSort(int* a, int n){int gap = n;while (gap > 1){gap = gap / 3 + 1;int i = 0;        //这里采用一个一个进行比较，注意不同for (i = 0; i = 0){if (tmp   测试：
  void ShellSortTest(){int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };int sz = sizeof(a) / sizeof(int);printf("排序前：");PrintArray(a, sz);printf("排序后：");ShellSort(a, sz);PrintArray(a, sz);}
      希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

一般来说，希尔排序的时间复杂度是 O(N^1.3)。

2.2 选择排序

2.2.1 直接选择排序
- 基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
- 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素；
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换；
- 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
  实现方法：
```
void swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}void SelectSort(int* a, int n){int begin = 0;int end = n - 1;while (begin    测试：
  void SelectSortTest(){int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };int sz = sizeof(a) / sizeof(int);printf("排序前：");PrintArray(a, sz);printf("排序后：");SelectSort(a, sz);PrintArray(a, sz);}
      直接选择排序的特性总结：
  
```
  - 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用；
  - 时间复杂度：O(N^2)。
    2.2.2 堆排序
    - 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
    - 这里运用到了堆的相关知识，学过二叉树的都知道，堆排序的思想就是先把所有的数据运用向下调整的方法建好堆，之后堆头元素和堆尾元素进行交换，在进行向下调整建堆。
    - 需要特别注意的是每次建堆都要采用向下调整建堆而不是向上调整，因为向下调整建堆的时间复杂度更低，效率更好，向下调整建堆的时间复杂度是 O(N)，而向上调整建堆的时间复杂度是 O(N*logN)。
    - 动图如下：
    - 实现方法：
```
void swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}void AdjustDown(int* a, int parent,int n){    //先假设左孩子是两个孩子中较大的那个int child = (parent * 2) + 1;while (child  a[child]){++child;}if (a[parent] = 0; --i){AdjustDown(a, i, n);}int j = 0;    // 建堆完成后和堆尾元素交换，在进行向下调整建堆    // 因为建大堆每次堆头元素都最大for (j = n - 1; j >= 0; --j){swap(&a[0], &a[j]);AdjustDown(a, 0, j);}}
```
      测试：
```
void HeapSortTest(){int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };int sz = sizeof(a) / sizeof(int);printf("排序前：");PrintArray(a, sz);printf("排序后：");HeapSort(a, sz);PrintArray(a, sz);}
```
      堆排序性能分析：
      - 堆排序使用堆来选数，效率就高了很多。
      - 时间复杂度：O(N*logN)
        2.3 交换排序
        
        2.3.1 冒泡排序
        
        冒泡排序就不用太多赘述了，作为算法界的 "Hello World",直接看代码吧：
        
        动图：
        
        void BubbleSort(int* a, int n){for (int i = 0; i a[j + 1]){swap(&a[j], &a[j + 1]);exchange = 1;}}if (exchange == 0){break;}}}
        
        测试：
        
        void BubbleSortTest(){int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };int sz = sizeof(a) / sizeof(int);printf("排序前：");PrintArray(a, sz);printf("排序后：");BubbleSort(a, sz);PrintArray(a, sz);}
        
        冒泡排序的特性总结：
        
        冒泡排序是一种非常容易理解的排序
        时间复杂度：O(N^2)
        2.3.2 快速排序
        
        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法；
        其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列；
        左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
        本篇文章只讲解Hoare的快速排序，至于更优化的结构，将会再之后的文章中讲解。
        
        动图如下：
        
        实现方法：
        
        void QuickSort(int* a, int begin, int end){if (begin >= end)return;int left = begin; int right = end;int keyi = begin;while (left = a[keyi]){--right;}// 左边找大while (left