快速排序-挖坑法
思路：
创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的坑，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的坑，结束循环后将最开始存储的分界值放入当前的坑中，返回当前坑下标（即分界值下标）
代码：
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>//打印
void PrintArr(int* arr, int n);
//快速排序
//挖坑法
void QuickSort(int* arr, int left, int right);
Sort.c
#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//快速排序找基准值
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{int hole = left;//找到坑位int key = arr[hole];//存储第一个坑位的值while (left < right)//left = right就跳出循环{while (left < right && arr[right] > key)//找到arr[right] < key的right{--right;}arr[hole] = arr[right];//填坑hole = right;//确定新的坑位while (left < right && arr[left] < key)//找到arr[left] > key的left{++left;}arr[hole] = arr[left];//填坑hole = left;//确定新的坑位}arr[hole] = key;//最后的坑位放上初始值return hole;//返回基准值
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值keyiint keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi + 1, right);
}
test.c
#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);QuickSort(a, 0, n - 1);printf("排序后：");PrintArr(a, n);return 0;
}
当然这里会有一点小问题的。比如数据是升序的时候，基准值找起来会有点问题。但因为这里是初阶数据结构，所以先不讨论基准值。后面的高阶数据结构里面会讲三数取中。