【排序算法】实现快速排序（霍尔法&&三指针法&&挖坑法&&优化随即选key&&中位数法&&小区间法&&非递归版本）

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

//Hoare经典随机快排
void QuickSort1(int* a, int left, int right)
{
	// 如果左指针大于等于右指针,表示数组为空或只有一个元素,直接返回
	if (left >= right)
		return;

	// 区间只有一个值或者不存在就是最小子问题
	int begin = left, end = right;// begin和end记录原始整个区间
	// keyi为基准值下标,初始化为左指针
	int keyi = left;

	 // 循环从left到right
	while (left < right)
	{
		// right先走，找小，这里和下面的left<right一方面也是为了防止,right一路走出区间，走到left-1越界
		while (left<right && a[right] >= a[keyi])
		{
			--right;
		}
		// 左指针移动,找比基准值大的元素   
		while (left<right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	// 交换左右指针所指元素
	Swap(&a[left], &a[keyi]);
	// 更新基准值下标
	keyi = left;
	
	// 递归排序左右两部分
	//[begin , keyi-1]keyi[keyi+1 , end]
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);

}

void QuickSort2(int* a, int left, int right)
{
	// 如果左指针大于等于右指针,表示数组为空或只有一个元素,直接返回
	if (left >= right)
		return;
		
	// keyi为基准值下标,初始化为左指针
	int keyi = left;
	
	// prev记录每次交换后的下标
	int prev = left;

	// cur为遍历指针
	int cur = left+1;
	
	// 循环从左指针+1的位置开始到右指针结束
	while (cur <= right)
	{
		// 如果cur位置元素小于基准值,并且prev不等于cur
	    // 就将prev和cur位置元素交换
	    // 并将prev后移一位
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;//不管是cur小于还是大于，是否交换,cur都后移一位      cur都++
	}
	// 将基准值和prev位置元素交换
	Swap(&a[keyi], &a[prev]);
	 // 更新基准值下标为prev
	keyi = prev;
	
	// 递归调用左右两部分
	// [left, keyi-1]keyi[keyi+1, right]
	QuickSort2(a, left, keyi - 1);
	QuickSort2(a, keyi + 1, right);
}

//挖坑法
void Dig_QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	//一趟的实现
	int key = a[begin];
	int pivot = begin;
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pivot] = a[right];
		pivot = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[pivot] = a[left];
		pivot = left;
	}

	//补坑位
	a[pivot] = key;
	
	//递归分治
	//[begin, piti - 1] piti [piti + 1, end]
	Dig_QuickSort(a, begin, pivot - 1);
	Dig_QuickSort(a, pivot + 1, end);
}

// 交换元素
void swap(int* a, int* b) 
{
    int t = *a;
    *a = *b;
    *b = t;
}

// 分区操作函数
int partition(int arr[], int low, int high) 
{

    // 取最后一个元素作为基准值
    int pivot = arr[high];

    // 初始化左右索引  
    int i = (low - 1);

    // 从左到右遍历数组
    for (int j = low; j <= high - 1; j++) 
    {

        // 如果当前元素小于或等于基准值
        if (arr[j] <= pivot) 
        {

            // 左索引向右移动一位
            i++;

            // 将当前元素与左索引位置元素交换  
            swap(&arr[i], &arr[j]);
        }
    }

    // 将基准值和左索引位置元素交换
    swap(&arr[i + 1], &arr[high]);

    // 返回基准值的最终位置
    return (i + 1);
}


// 快速排序主函数
void quickSort(int arr[], int low, int high) 
{

    // 如果低位索引小于高位索引,表示需要继续排序
    if (low < high) 
    {

        // 调用分区函数,得到基准值的位置
        int pi = partition(arr, low, high);

        // 对基准值左边子数组递归调用快速排序
        quickSort(arr, low, pi - 1);

        // 对基准值右边子数组递归调用快速排序   
        quickSort(arr, pi + 1, high);
    }
}

// 测试
int main() 
{
    // 测试数据
    int arr1[] = { 5,3,6,2,10,1,4 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    quickSort(arr1, 0, n1 - 1);
    // 输出排序结果
    for (int i = 0; i < n1; i++)
    {
        printf("%d ", arr1[i]);
    }
    printf("\n");

    int arr2[] = { 5,3,6,2,10,1,4,29,44,1,3,4,5,6 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    quickSort(arr2, 0, n2 - 1);
    // 输出排序结果
    for (int i = 0; i < n2; i++)
    {
        printf("%d ", arr2[i]);
    }
    printf("\n");

    // 测试数据
    int arr3[] = { 10,1,4,5,3,6,2,1 };
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    quickSort(arr3, 0, n3 - 1);
    // 输出排序结果
    for (int i = 0; i < n3; i++)
    {
        printf("%d ", arr3[i]);
    }
    printf("\n");

    return 0;
}

//快排，随机选key
void QuickSort3(int* a, int left, int right) 
{

  //区间只有一个值或者不存在就是最小子问题
  if (left >= right)
    return;

  int begin = left, end = right;

  //选[left,right]区间中的随机数做key
  int randi = rand() % (right - left + 1);  
  //rand() % N生成0到N-1的随机数
  randi += left;  

  //将随机索引处的元素与区间起始元素交换
  Swap(&a[left], &a[randi]);

  //用交换后的元素作为基准值keyi
  int keyi = left;

  while (left < right) 
  {
    
    //从右向左找小于key的元素
    while (left < right && a[right] >= a[keyi]) 
    {
      --right;
    }
    
    //从左向右找大于key的元素      
    while (left < right && a[left] <= a[keyi]) 
    {
      ++left; 
    }

    //交换元素
    Swap(&a[left], &a[right]);
  }

  //将基准值与交叉点元素交换
  Swap(&a[left], &a[keyi]);
  keyi = left;

  //递归处理子区间
  QuickSort3(a, begin, keyi - 1);
  QuickSort3(a, keyi + 1, end);
}

// 三数取中  left  mid  right
// 大小居中的值，也就是不是最大也不是最小的
int GetMidi(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 // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

		int begin = left, end = right;
		// 三数取中
		int midi = GetMidi(a, left, right);
		//printf("%d\n", midi);
		Swap(&a[left], &a[midi]);

//三数取中  left  mid  right
//大小居中的值，也就是不是最大，也不是最小的
int GetMid(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//a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


void QuickSort4(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left, end = right;
	//三数取中
	int midi = GetMid(a, left, right);
	//printf("%d\n",midi);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	QuickSort4(a, begin, keyi - 1);
	QuickSort4(a, keyi + 1, end);

}

void QuickSort5(int* a, int left, int right)
{
	if (left >= right)
		return;

	// 小区间选择走插入，可以减少90%左右的递归
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		int begin = left, end = right;
		//三数取中
		int midi = GetMid(a, left, right);
		//printf("%d\n",midi);
		Swap(&a[left], &a[midi]);

		int keyi = left;
		while (left < right)
		{
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		QuickSort4(a, begin, keyi - 1);
		QuickSort4(a, keyi + 1, end);
	}
}

#include "Stack.h"

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

		//单趟
		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[prev], &a[cur]);
			++cur;
		}

		Swap(&a[prev], &a[keyi]);
		keyi = prev;

		//[begin,keyi-1]keyi[keyi+1,end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (keyi - 1 > begin)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}
	
	STDestroy(&st);
}

#include"Stack.h"

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 栈顶
// 11:55
void STPush(ST* ps, STDataType x)
{
	assert(ps);

	// 满了， 扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);

// 栈顶
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);