C语言实现快速排序的三种方法（挖坑法，前后指针法，左右指针法）

#pragma once
#include<stdio.h>

//直接插入排序
//时间复杂度0（n^2）
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
           

#pragma once
#include<stdio.h>
#include"Insertsort.h"

//快速排序-----加上三数取中，让其效率整体提升
//时间复杂度0（N*N）

void Swap3(int* a1, int* a2)
{
	int tmp = *a1;
	*a1 = *a2;
	*a2 = tmp;
}

//三数取中---去中间位置的数----为防止有序的在让其排序那么效率就很低
int GetMinindex(int* a, int left, int right)
{
	int mid = (left + right) / 2;

	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//法一：挖坑法---设置key，右边找小填坑，左边找大填坑
int quickSort1(int* a, int left,int right)
{
	int index = GetMinindex(a, left, right);//取出合适的位置
	Swap3(&a[left], &a[index]);//进行交换，把其放在第一位，方便快排取数

	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[begin];
	while (begin < end)
	{
		//右边找小，放在左边填坑，
		while (begin < end && a[end] >= key)
			--end;

		a[pivot] = a[end];
		pivot = end;

		//左边找大，放在右边填坑，
		while (begin < end && a[begin] <= key)
			++begin;

		a[pivot] = a[begin];
		pivot = begin;	
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}


//法二：左右指针法---设置key，右边找小，左边找大，直接交换两个
int quickSort2(int* a, int left, int right)
{
	int index = GetMinindex(a, left, right);//取出合适的位置
	Swap3(&a[left], &a[index]);//进行交换，把其放在第一位，方便快排取数

	int begin = left;
	int end = right;
	int keyi = a[begin];

	while (begin < end)
	{
		//右边找小
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}
		
		//左边找大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}
		Swap3(&a[begin], &a[end]);
	}
	Swap3(&a[begin], &a[keyi]);
	return begin;
	
}

//法三：前后指针法---设置key，pre，cur找小，与pre交换，++pre；
int quickSort3(int* a, int left, int right)
{
	int index = GetMinindex(a, left, right);//取出合适的位置
	Swap3(&a[left], &a[index]);//进行交换，把其放在第一位，方便快排取数

	int keyi = left;
	int pre = left; 
	int cur = left+1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			++pre;
			Swap3(&a[pre], &a[cur]);
		}
		++cur;
	}
	Swap3(&a[keyi], &a[pre]);
	return pre;
}

//快排
void quickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	//法一：挖坑法
	//int keyindex = quickSort1(a, left, right);
	
	//法二：左右指针法
	//int keyindex = quickSort2(a, left, right);

	//法三：前后指针法
	int keyindex = quickSort3(a, left, right);

	if (keyindex - 1 - left > 10)
		quickSort(a, left, keyindex - 1);
	else
		InsertSort(a + left, keyindex - 1 - left + 1);

	if( right - (keyindex+1) > 10)
		quickSort(a, keyindex + 1, right);
	else
		InsertSort(a + keyindex + 1, right-(keyindex + 1) + 1);
}

           

void test()//快速排序
{
	int a[] = { 6,8,4,5,0,12,9,8,7,62,1,44,56,6 };
	int sz = sizeof(a) / sizeof(int);
	quickSort(a, 0,sz-1);
	printA(a, sz);
}

int main()
{
	test();
	return 0;
}