C语言：排序（一）

目录

1. 前言

2. 冒泡排序

2.1 动态演示

2.2 代码实现

3. 插入排序

3.1 直接插入排序

3.1.1 动态演示

3.1.2 代码实现

3.2 希尔排序

3.2.1 代码实现

4. 选择排序

4.1 动态演示

4.2 代码实现

5. 堆排序

5.1 代码实现

1. 前言

本篇主要讲解基础的排序算法，教学意义较大，实践意义较小。

在排序代码中会频繁使用自定义函数Swap，因此在前言中进行声明，后文不再过多赘述。

void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }

2. 冒泡排序

• 时间复杂度O( N )
• 思想：重复遍历数组，依次比较相邻的两个元素，如果左边比右边大，就交换它们的位置。每一轮遍历，都会把当前未排序部分中最大的那个元素“冒泡”到最右边。

2.1 动态演示

2.2 代码实现

//冒泡排序 void BubbleSort(int* a, int n) { for(int i=0; i<n-1; i++) { for(int j=0; j<n-1-i; j++) { if(a[j] > a[j+1]) { Swap(&a[j], &a[j+1]); } } } }

3. 插入排序

3.1 直接插入排序

• 时间复杂度O( N^2 )，最好情况O( N )
• 思想：将数组分为“已排序”和“未排序”两部分，每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。

3.1.1 动态演示

3.1.2 代码实现

//插入排序 void InsertSort(int* a, int n) { for(int i=0; i<n-1; i++) //小于n-1是因为后面涉及end+1，如果小于n会越界 { int end = i; int obj = a[end + 1]; while(end >= 0) { if(a[end] > obj) { a[end + 1] = a[end]; //也可以用Swap end--; } else { break; } a[end + 1] = obj; } } }

3.2 希尔排序

• 时间复杂度O( N^1.3 )左右
• 思想：希尔排序是插入排序的改进版，通过“分组跳跃式插入”让数组先变得“大致有序”，最后再用一次插入排序完成精细调整。

3.2.1 代码实现

//希尔排序（预排序+插入排序，插入排序已被预排序包含） //法一：逐组进（三层循环） void ShellSort1(int* a, int n) { int gap = n; while(gap > 1) //gap为1时为插入排序 { gap = gap / 3 + 1; for(int j=0; j<gap; j++) //一共有gap数量的组 { for(int i=0; i<n-gap; i+=gap) //改为n-gap，否则会越界 { int end = i; while(end >= 0) { if(a[end] > a[end+gap]) { Swap(&a[end], &a[end+gap]); end-=gap; } else { break; } } } } } }

//法二：多组并行 void ShellSort2(int* a, int n) { int gap = n; while(gap > 1) { gap = gap / 3 + 1; for(int i=0; i<n-gap; i++) { int end = i; while(end >= 0) { if(a[end] > a[end + gap]) { Swap(&a[end], &a[end + gap]); end -= gap; } else { break; } } } } }

4. 选择排序

• 时间复杂度O( N^2 )
• 思想：每次从待排序部分选出最小（或最大）的元素，放到已排序部分的末尾。

4.1 动态演示

// 这是最直接的选择排序，但在代码中采用了首尾双指针的方法进行选择排序：

同时找出区间内的最大和最小元素，放在区间首尾

4.2 代码实现

//选择排序（双指针） void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while(begin < end) { int mini = begin, maxi = begin; for(int i=begin+1; i<=end; i++) { if(a[i] > a[maxi]) { maxi = i; } if(a[i] < a[mini]) { mini = i; } } Swap(&a[maxi], &a[end]); //避免刻舟求剑TvT if(mini == end) mini = maxi; Swap(&a[mini], &a[begin]); begin++; end--; } }

5. 堆排序

• 时间复杂度O( NlogN )
• 思想：向上调整算法 + 模拟堆删除操作。顺序建大堆，倒序建小堆

详细介绍可以阅读博主之前写的这篇博客：

堆（C语言）-CSDN博客

5.1 代码实现

//堆排序（向下调整建大堆->每次交换首尾元素并end--，向下调整） void HeapSort(int* a, int n) { //向下调整 for(int i=(n-1-1)/2; i>=0; i--) { int parent = i; int child = parent * 2 + 1; while(child < n) { //假设法（右孩子存在且右孩子更大） if(child+1<n && a[child+1] > a[child]) { child += 1; } if(a[parent] < a[child]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //设置end，交换首尾元素 int end = n-1; while(end) { Swap(&a[end], &a[0]); //向下调整 int parent = 0; int child = parent * 2 + 1; while(child < end) { if(child+1<end && a[child+1] > a[child]) { child += 1; } if(a[parent] < a[child]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } end--; } }

//感谢阅读~(●'◡'●)