前面我们讲了插入排序的两种，接下来我们来学习其他几种排序算法吧

1. 选择排序

• 选择排序的思想：每次从待排序的数据中选取最小(最大)的元素，然后存放在序列的起始位置，直到数据全部排完序
• 选择排序分为两种：直接选择排序、堆排序

1.1 直接选择排序

• 直接选择排序的思想：首先选取待排序集合的最大(最小)的数据元素，如果最大的元素不是序列的最后一个位置，则让它与最后的元素交换；同样，最小的元素如果不再数据的起始位置，那么让它与第一个元素交换，之后继续重复上述操作待排序的数据，直到排好序

  下面我将用图示的方式来帮助大家理解

---

---

---

---

• 以上是我们对特殊情况的分析，接下来我们还是继第三步继续分析

---

---

---

---

• 接下来我们就看下代码是如何实现的吧

//直接选择排序
void SelectSort(int* arr, int sz)
{int begin = 0;int end = sz - 1;while (begin < end){int max = begin;int min = begin;//寻找最大、最小元素for (int i = begin + 1; i <= end; i++)//由于max和min都在首元素，这里直接从begin+1开始找就行{//寻找最大元素if (arr[i] > arr[max]){max = i;}//寻找最小元素if (arr[i] < arr[min]){min = i;}}//特殊情况处理(begin == max)if (begin == max){max = min;}//交换if (min != begin){Swap(&arr[min], &arr[begin]);}if (max != end){Swap(&arr[max], &arr[end]);}begin++;end--;}
}

• 直接选择排序的时间复杂度是O(n^2),空间复杂度是O(1)

1.2 堆排序

• 前面我们讲二叉树的时候就已经讲过堆了，这里只带大家简单熟悉一下，需要深入了解的小伙伴可点击下面的链接
• 链接: 【数据结构与算法】第8课—数据结构之二叉树(堆)

---

• 总体来讲，堆排序的时间复杂度是O(nlogn),它是一个比较好的排序算法
• 接下来附上堆排序的代码

//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子节点while (child < n){//先找最小的孩子if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//交换if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* arr, int sz)
{//向下调整算法建堆for (int i = (sz - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, sz);}//堆排序int end = sz - 1;while (end){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

2. 交换排序

• 交换排序的思想：就是根据序列交换数据的位置
• 交换排序的特点：数据大(小)的值向尾部移动，而数据小(大)的值向头部移动
• 交换排序也分为两种：冒泡排序和快速排序

2.1 冒泡排序

  学到这里我们对冒泡排序应该很熟悉了，尽管它是一个很差的排序算法，它的时间复杂度是O(N^2),如果还有小伙伴对冒泡排序不熟悉的，可点击下面的链接，不废话，直接上代码
  链接: C语言进阶版第8课—指针（2）

//冒泡排序
void BubbleSort(int* arr, int sz)
{for (int i = 0; i < sz; i++){int flag = 0;for (int j = 0; j < sz - i - 1; j++){if (arr[j] > arr[j + 1]){flag = 1;int tmp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = tmp;}}if (flag == 0)break;}
}

2.2 快速排序(找基准值法1----Hoare版本)

• 快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两字序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为⽌

---

---

---

---

---

---

---

• Hoare提出的快速排序其实可以看成二叉树递归，首先定义一个基准值，然后调整基准值位置，再根据基准值二分数组，将划分的每个子树重新定义一个基准值，再调整新的基准值位置，然后根据新的基准值再二分新的数组，直到最后只剩一个元素时结束递归，这时快速排序就完成了

2.2.1 特殊场景1

• 
  
  

2.2.2 特殊场景2

• 最特殊的场景

---

---

2.2.3 代码

• 接下来看看代码是如何实现的

//找基准值
int _QuickSort(int* arr, int left, int right)
{int key = left;left++;while (left <= right){//right:从右向左找比基准值小的数while (left <= right && arr[right] > arr[key]){right--;}//left:从左向右找比基准值大的数while (left <= right && arr[left] < arr[key]){left++;}//left和right交换if (left <= right){Swap(&arr[left], &arr[right]);left++;right--;}}//此时left>right，且arr[right]<arr[key],arr[left]>arr[key]//交换arr[key]和arr[right]Swap(&arr[key], &arr[right]);//此时right就是基准值校准后的下标return right;
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值int key = _QuickSort(arr, left, right);//二分QuickSort(arr, left, key - 1);//左子树QuickSort(arr, key + 1, right);//右子树
}

2.2.4 快速排序的时间复杂度

---

2.3 快速排序(找基准值法2—挖坑法)

• 创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准⼤的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）

---

---

---

---

---

---

---

---

2.3.1 特殊情况1处理

---

2.3.2 特殊情况2处理

---

• 代码实现

//找基准值法2---挖坑
int _QuickSort2(int* arr, int left, int right)
{int key = arr[left];//先定义基准值int hole = left;while (left < right){//right向左找比基准值小的数while (left < right && arr[right] >= key){right--;}//找到后arr[hole] = arr[right];hole = right;//left向右找比基准值大的数while (left < right && arr[left] <= key){left++;}//找到后arr[hole] = arr[left];hole = left;}//此时left=right,将基准值放入坑位arr[hole] = key;return hole;
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值int key = _QuickSort2(arr, left, right);//二分QuickSort(arr, left, key - 1);//左子树QuickSort(arr, key + 1, right);//右子树
}

2.4 快速排序(找基准值法3-----lomuto(双指针法))

• 双指针法法：定义两个指针prev和cur，cur指针用来探路，找比基准值要小的数

• 两种情况：
• cur未找到比基准值小的数据：cur++
• cur找到了比基准值小的数据：prev++，然后prev和cur位置的数据互换，cur再++找比基准值小的数，直到cur越界都未找到，那么交换prev位置的数据和基准值

---

---

---

---

---

---

• 代码实现

//找基准值法3---双指针法
int _QuickSort3(int* arr, int left, int right)
{int key = left;//基准值int prev = left;int cur = left + 1;//cur指针用来探路找比基准值小的数while (cur <= right){//cur找到比基准值小的数if (cur <= right && arr[cur] < arr[key]){prev++;if (prev != cur){Swap(&arr[prev], &arr[cur]);}}//cur未找到比基准值小的数，不论找没找到，cur都得++cur++;}//cur越界，交换arr[prev]和基准值Swap(&arr[prev], &arr[key]);return prev;//prev为校准后的基准值下标
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值int key = _QuickSort3(arr, left, right);//二分QuickSort(arr, left, key - 1);//左子树QuickSort(arr, key + 1, right);//右子树
}

2.5 快速排序(非递归版本)

• 非递归版本的思路：需要借助数据结构——栈，首先将数组的尾元素下标入栈，再让数组的首元素的下标入栈，保证栈不为空，然后取栈顶元素，先后将栈顶元素赋给begin和end，然后利用双指针法找基准值，找到基准值后将数组二分，然后先让右子树入栈，再让左子树入栈，入栈依然是尾元素下标优先，且入栈的都是子树的首尾元素下标，然后再取栈顶元素分别赋给begin和end，然后双指针找基准值，二分数组，入栈，取栈顶元素，以此往复，直到栈为空，排序完成

• 接下来我将用图示来帮助大家理解

---

---

---

---

---

---

---

---

---

• 代码实现

//快速排序---非递归版本
void QuickSortNone(int* arr, int left, int right)
{Stack st;//定义栈的变量StackInit(&st);//初始化//入栈StackPush(&st, right);StackPush(&st, left);//栈不为空while (!StackEmpty(&st)){//取栈顶元素int begin = StackTop(&st);StackPop(&st);//取出一个销毁一个int end = StackTop(&st);StackPop(&st);//找基准值---双指针法int key = begin;int prev = begin;int cur = prev + 1;//探路，找比基准值小的数while (cur <= end){//找比基准值小的数if (arr[cur] < arr[key]){prev++;//找到了，prev先往后走if (cur != prev){Swap(&arr[cur], &arr[prev]);}}//未找到/找到cur都得++cur++;}//cur越界,交换arr[prev]和基准值，此时prev就是校准后的基准值位置Swap(&arr[prev], &arr[key]);key = prev;//右子树先入栈if (key + 1 < end){StackPush(&st, end);//右子树尾元素下标StackPush(&st, key + 1);//右子树首元素下标}//左子树入栈if (begin < key-1){StackPush(&st, key - 1);//左子树尾元素下标StackPush(&st, begin);//左子树首元素下标}}StackDestroy(&st);//销毁栈
}