超级哇塞的快排，你值得学会！

今天我们要讲的是快速排序，非常的哇塞！

简单了解一下快排------

下面介绍快排的三个方法，未优化和优化后的快排

First----hoare版本
 

也就是说先确立的一个下标为key的值为对比值，普遍可以认为左边第一个值就key值，然后，从右边发出，寻找比key值小的数字，当R停下时，L才动，然后找到比key大的值，然后进行L、R的交换，最终他们一定会相遇，相遇的下标对应的值就将key赋值给他，然后再分而治之，

[left,key-1]          key      [key+1,right]    就是一样一个递归

数据结构一定要学会画图来思考问题，让问题更加地清晰明了！

 

 

 完整代码：

//hoare版本
void QuickSort(int* arr, int begin, int end)
{
	//进来判断一下
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int key = left;
	while (left < right)
	{
		//先走右边
		while (left < right && arr[right] >= arr[key])
		{
			--right;
		}
		while (left < right && arr[left] <= arr[key])
		{
			++left;
		}
		//交换
		Swap(&arr[left], &arr[right]);
	}
	//最后相遇了
	Swap(&arr[key], &arr[left]);
	key = left;//更新key的位置
	QuickSort(arr, begin, key - 1);
	QuickSort(arr, key + 1, end);

}
void PrintSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,1,2,4,9,5,6};
	int len = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr,0, len-1);	
	
	PrintSort(arr, len);
}

下面介绍另外一种方法，被大神们优化一下， 比较好理解！

2、挖坑法-------顾名思义就是有一个坑

 

完整代码：

//挖坑法
void QuickSort(int* arr, int begin, int end)
{
    if (begin >= end)
    {
        return;
    }
    int left = begin;
    int right = end;
    int key = arr[left];
    int piti =left;//坑位
    while (left < right)//控制范围
    {
        while (left < right && arr[right] >= key)
        {
            --right;
        }
        arr[piti] = arr[right];
        piti = right;
        while (left < right && arr[left] <= key)
        {
            ++left;
        }
        arr[piti] = arr[left];
        piti = left;
    }
    //还有最后相遇的一个坑位
    arr[piti] = key;
    QuickSort(arr, begin, piti - 1);
    QuickSort(arr, piti + 1, end);
}

void PrintSort(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int arr[] = { 3,1,2,4,9,5,6};
    int len = sizeof(arr) / sizeof(arr[0]);
    QuickSort(arr,0, len-1);    
    
    PrintSort(arr, len);
}

第三种方法：前后指针版本

 

完整代码：

//前后指针版本
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int prev = begin;
	int cur = begin + 1;
	int key = begin;
	while (cur <= end)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	
	//最后只剩下一个prev
	Swap(&arr[prev], &arr[begin]);
	key = prev;
	QuickSort(arr, begin, key - 1);
	QuickSort(arr, key + 1, end);
}
void PrintSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,1,2,4,9,5,6};
	int len = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr,0, len-1);	
	
	PrintSort(arr, len);
}

 相信你学会这三种快排的方法不算难事，但是那都是没进行过优化的，接下来让我们来优化一下吧！前面三种方法的时间复杂度都是O（N），在效率上并没有提升太多

优化方法—：三数取中（在前后指针版本上面改善）

影响效率的障碍就是key，要不每次key都是最小，要        不key每次都是最大，那么效率肯定就上不去，如果我们让key是区域内的middle 那么效率更上一层了，所以三数取中。

//前后指针版本
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int prev = begin;
	int cur = begin + 1;
	int key = begin;

	//三数取中
	int mid = GetMidIndex(arr, begin, end);
	Swap(&arr[key], &arr[mid]);
	while (cur <= end)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	
	//最后只剩下一个prev
	Swap(&arr[prev], &arr[begin]);
	key = prev;
	QuickSort(arr, begin, key - 1);
	QuickSort(arr, key + 1, end);
}

优化方法二：递归到小的子区间时，可以考虑使用插入排序

因为在数据有序或者接近有序的时候，插入排序的效率非常可观，至于为什么不用希尔，堆，是因为在大数据下用他们比较快，但是接近有序的时间复杂度插入排序更胜一筹！

 

 

这些数据划分区域就知道最后接近有序的递归次数就占了一半，所以说非常的庞大。

区域优化代码：
 

 这里的插入排序的arr如果不加begin的话，那么每次都是最前面的20个数进行排序，那么无意义，arr+begin就是不同区域内的begin----end

这个优化就非常的爽了！

这些快排都是运用了递归的方式，递归也是一定的劣势，所以我们也必须要掌握非递归的方式

非递归我们运用的是栈完成快排

栈的性质是先进后出，我们可以完美地运用这个性质！

思路：

 这完全就像是树的工作方式，先完成左树的排序，然后再进行右树的排序，穷尽到最后一个区域，最后再销毁一下栈就可以实现非递归的快排了

更形象一点：当然用队列也是一样的，运用好队列的性质就行好，控制好

 

因为这是纯C所以要先手搓一个栈，到C++就不用这么麻烦了，

非递归完整代码:

//栈
typedef struct Stack
{
	int* arr;
	int top;
	int capacity;
}Stack;

void InitStack(Stack* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps,int x)
{
	//检测是否满了
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int tmp = (int *)realloc(ps->arr,sizeof(int )*newcapacity);
		ps->arr = tmp;
		ps->capacity = newcapacity;

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

void StackPop(Stack* ps)
{
	ps->top--;
}

void DestoryStack(Stack* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

int StackTop(Stack* ps)
{
	return ps->arr[ps->top-1];
}

bool StackEmpty(Stack* ps)
{
	return ps->top==0;
}

//栈来实现非递归的快排
void QuickSort(int* arr, int begin, int end)
{
	Stack st;
	InitStack(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);

		int keyi = QuickSort2(arr, left, right);
		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
	}
	DestoryStack(&st);
}
void PrintSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,1,2,4,9,5,6};
	int len = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr,0,len-1);	
	
	PrintSort(arr, len);
}

伙伴们！快来试一下吧！！

如有错误，请指出！