点击蓝字，关注我们

往期回顾

挑战全网，详细的介绍自下而上的迭代法——一种让你的电脑飞速运行的归并排序方法，你不可不知！

免费赠送EPLAN部件库，全网最全部件库：包含全部常用的品牌部件，一次性交给你们

01

本节重点

C语言快速排序的原理

快速排序是一种非常流行的排序算法，它的优点是速度快，效率高，而且易于实现。

基本思想：

通过不断地将一个序列分成两个子序列，并对每个子序列进行排序，最终得到一个完全有序的序列。快速排序的时间复杂度在平均情况下是O(nlogn)，在最坏情况下是O(n^2)，但是后者很少发生，而且可以通过一些技巧来避免。快速排序的空间复杂度是O(logn)，因为它需要递归调用栈空间。

核心：分区操作

目的是将一个序列按照一个基准（pivot）元素划分成两个部分，使得左边的元素都小于等于基准，右边的元素都大于等于基准。这样，基准元素就找到了它在最终排序后的正确位置，而且左右两边的元素也分别形成了一个新的子序列，可以继续进行分区操作。

操作步骤

1、从序列中选择一个元素作为基准，可以是第一个元素，也可以是随机的元素，或者是中位数等；

2、定义两个指针i和j，分别指向序列的首尾；

3、重复以下步骤，直到i和j相遇：

3.1、从右向左移动j，找到第一个小于等于基准的元素，将其与i所指的元素交换，然后将i向右移动一位；

3.2、从左向右移动i，找到第一个大于等于基准的元素，将其与j所指的元素交换，然后将j向左移动一位；

4、返回i的位置，作为基准的最终位置。

// 分区操作，返回基准的最终位置int partition(int arr[], int left, int right)  {  int pivot = arr[left]; // 选择第一个元素作为基准  int i = left; // 定义左指针  int j = right; // 定义右指针  while(i < j)  {    // 当左右指针未相遇时    while(i < j && arr[j] >= pivot)      {      // 从右向左移动j，找到第一个小于等于基准的元素     	 j--;      } if(i < j)    {    // 如果左右指针未相遇，交换i和j所指的元素，并将i向右移动一位    arr[i] = arr[j];    i++;    }	while(i < j && arr[i] <= pivot)    {    // 从左向右移动i，找到第一个大于等于基准的元素    i++;    }  if(i < j)      {      // 如果左右指针未相遇，交换i和j所指的元素，并将j向左移动一位      arr[j] = arr[i];      j--;      }  }arr[i] = pivot; // 将基准元素放到最终位置return i; // 返回基准的位置}

有了这个分区操作，我们就可以定义一个递归函数，用来对一个序列进行快速排序。

函数的参数

一个待排序的序列（数组）arr；

一个序列的起始索引left，和一个序列的结束索引right。

函数的步骤

（一）、如果left大于等于right，那么说明序列只有一个或零个元素，无需排序，直接返回；

（二）、如果left小于right，那么说明序列有多个元素，需要排序，继续执行以下步骤：

1、调用分区操作，对序列进行划分，得到基准的位置p；

2、对左子序列进行快速排序，调用自身函数，传入arr，left和p-1作为参数；

3、对右子序列进行快速排序，调用自身函数，传入arr，p+1和right作为参数。

// 对一个序列进行快速排序void quick_sort(int arr[], int left, int right){  if(left >= right)  {  // 如果序列只有一个或零个元素，无需排序，直接返回    return;  }if(left < right)  {    // 如果序列有多个元素，需要排序    int p = partition(arr, left, right);     // 调用分区操作，对序列进行划分，得到基准的位置p    quick_sort(arr, left, p - 1); // 对左子序列进行快速排序，递归调用    quick_sort(arr, p + 1, right); // 对右子序列进行快速排序，递归调用  }}

这样，我们就完成了快速排序的递归方法的实现。

还想了解什么内容，可以给我留言，能解答的话会一一解答各位，感谢各位的阅读！

可以的话麻烦各位点赞和在看点一点，码字不易，再次感谢你的阅读

点赞＋关注，学习不迷路！

微信公众号：工控小新

学习工控知识就来工控小新，为你提供工控笔记知识：EPLAN电气绘图 | TIA博图基础 | CAD | C语言教学 | 单片机基础 | 三菱PLC ... 每日持续更新中

原文：全网讲解最全：一文诠释了C语言快速排序法的原理，简单又高效！

#来点儿干货#