Super wow fast row, you are worth learning!

Today we are going to talk about quick sorting , Very wow ！

Take a brief look at the quick row ------

Here are three methods of fast platoon , Non optimized and optimized fast platoon

First----hoare edition
 

That is to say, the first established subscript is key The value of is the comparison value , It is generally believed that the first value on the left is key value , then , From the right , Look for a comparison key Small numbers , When R When you stop ,L Just move , Then find something better than key Big value , Then proceed L、R In exchange for , Eventually they will meet , The value corresponding to the encountered subscript will key Assigned to him , Then divide and rule ,

[left,key-1]          key      [key+1,right]    It's just a recursion

Data structure must learn to draw pictures to think about problems , Make the problem clearer ！

 

 

  Complete code ：

//hoare edition 
void QuickSort(int* arr, int begin, int end)
{
	// Come in and judge 
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int key = left;
	while (left < right)
	{
		// Go first to the right 
		while (left < right && arr[right] >= arr[key])
		{
			--right;
		}
		while (left < right && arr[left] <= arr[key])
		{
			++left;
		}
		// In exchange for 
		Swap(&arr[left], &arr[right]);
	}
	// Finally met 
	Swap(&arr[key], &arr[left]);
	key = left;// to update key The location of 
	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);
}

Here's another way , Be optimized by the great gods , It's easy to understand ！

2、 Excavation method ------- As the name suggests, there is a pit

 

Complete code ：

// Excavation method
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;// Pit position
    while (left < right)// Control range
    {
        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;
    }
    // And the last pit we met
    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);
}

The third method ： Front and back pointer versions

 

Complete code ：

// Front and back pointer versions 
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;
	}
	
	// There's only one left 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);
}

  I believe it's not difficult for you to learn these three methods of fast platoon , But that is not optimized , Next, let's optimize it ！ The time complexity of the first three methods is O（N）, Not much improvement in efficiency

An optimization method —： Take the three Numbers （ Improve the front and back pointer versions ）

The obstacle to efficiency is key, Not every time key It's the smallest , want          No key Every time is the biggest , Then efficiency will definitely not go up , If we let key It's in the area middle Then efficiency goes to a higher level , So three numbers are taken in .

// Front and back pointer versions 
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int prev = begin;
	int cur = begin + 1;
	int key = begin;

	// Take the three Numbers 
	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;
	}
	
	// There's only one left prev
	Swap(&arr[prev], &arr[begin]);
	key = prev;
	QuickSort(arr, begin, key - 1);
	QuickSort(arr, key + 1, end);
}

Optimization method 2 ： Recursion to a small subinterval , Consider using insert sort

Because when the data is in order or close to order , The efficiency of insertion sorting is very impressive , As for why not use hill , Pile up , Because it is faster to use them under big data , But the near ordered time complexity insertion sort is better ！

 

 

These data can be divided into regions. Finally, the number of recursions close to order accounts for half , So it's very huge .

Area optimization code ：
 

  The insertion sort here arr If not begin Words , Then every time it is the front 20 Number to sort , So meaningless ,arr+begin It's in different areas begin----end

This optimization is very cool ！

These quick rows are recursive , Recursion is also a disadvantage , So we must also master non recursive methods

Non recursive, we use the stack to complete fast scheduling

The nature of stack is first in and last out , We can use this property perfectly ！

Ideas ：

  It's exactly like the way trees work , Finish sorting the left tree first , Then sort the right tree , Exhausted to the last area , Finally, destroy the stack again to realize non recursive fast sorting

A little more vivid ： Of course, using queues is the same , Just make good use of the nature of the queue , Control it

 

Because this is pure C So first rub a stack , To C++ There's no need for such trouble ,

Non recursive complete code :

// Stack 
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)
{
	// Check whether it is full 
	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;
}

// Stack to achieve non recursive fast scheduling 
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);
}

partners ！ Give it a try ！！

If there is a mistake , Please point out ！