The C language implements an improved version of quicksort

The method of 3 - to - center is used to improve quicksort. The details are as follows

The implementation takes the middle element of the first, middle, and last element of the array as the partition element (otherwise the elements are excluded from the partition process). Arrays of size 11 or smaller are ignored during the partition process, and then the insertion sort is used to complete the sort.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
// Output function 
void Print(int a[], int l, int r)
{
 int i;
 for(i = l; i <= r; i++)
 {
  printf("%d ", a[i]);
 }
 printf("\n");
}
// Improved insertion sort 
void Insertion(int a[], int l, int r)
{
 int i, j;
 // Loop to find the minimum value in the array 
 for(i = r; i > l; i--)
 {
  if(a[i-1] > a[i])
  {
   swap(a[i-1], a[i]);
  }
 }
 // Because of the loop above ,a[0]a[1] Have already ordered 
 for(i = l+2; i <= r; i++)
 {
  int temp = a[i];
  j = i;
  // At this time a[j] The location has been recorded 
  //while Shift operation is performed for cyclic comparisons 
  while(temp < a[j-1])
  {
   a[j] = a[j-1];
   j--;
  }
  // Place the recorded values where they should be 
  a[j] = temp;
 }
}
// Partition function 
int partion(int a[], int left, int right)
{
 // Take the rightmost element as the partition element 
 int temp = a[right];
 // record  i = left, j = right
 int i = left, j = right-1;
 // Loop until the left and right Pointers meet 
 while(true)
 {
  // Scan from the left , When there are elements larger than the partition element , Scanning to stop 
  while(temp > a[i])
  {
   i++;
  }
  // Scan from the right , When there are elements smaller than partition elements , Scanning to stop 
  while(temp < a[j] && j >= left)
  {
   j--;
  }
  // if  i >= j,  Cycle as , The following exchange is not performed 
  if(i >= j) break;
  // The element when the exchange stops 
  swap(a[i], a[j]);
 }
 // Swap the element with the partition element 
 swap(a[i], a[right]);
 //printf("i = %d\n", i);
 //Print(a, 0, 6);
 // End of partition process 
 return i;
}
 
void qsort(int a[], int left, int right)
{
 int i;
 if(right-left <= 10)
  return;
 swap(a[(left+right)/2], a[right-1]);
 if(a[left] > a[right-1])
  swap(a[left], a[right-1]);
 if(a[left] > a[right])
  swap(a[left], a[right]);
 if(a[right] > a[right-1])
  swap(a[right-1], a[right]);
 i = partion(a, left+1, right-1);
 qsort(a, left, i-1);
 qsort(a, i+1, right);
}
void Sort(int a[], int left, int right)
{
 qsort(a, left, right);
 Insertion(a, left, right);
}
 
int main()
{
 int a[12] = {2, 5, 3, 7, 6, 1, 4, 11, 8, 10, 9, 12};
 // Quick Sort improvement 
 printf(" right 0~11 The sorting \n");
 Sort(a, 0, 11);
 Print(a, 0, 11);
 return 0;
}