改进版快速排序：针对部分有序列的策略与优化技巧" - 随机选枢轴：当数据部分有序时，传统快速排序通过固定枢轴可能导致效率低下。为此，我们采用随机选取枢轴的方法，代码如下： ```c int SelectPivotRandom(int arr[], int low, int high) { srand(time(0)); int pivotPos = (rand() % (high - low)) + low; swap(arr[pivotPos], arr[low]); return arr[low]; } ``` - 优化小数组交换：针对小且部分有序的数组，快速排序不如插入排序高效。因此，当待排序序列长度小于等于10时，我们会切换至插入排序： ```c #define MAX_LEN 10 void quicksort_optimized(int *arr, int left, int right) { int length = right - left; if (l

#include<iostream>
using namespace std;
int partition(int *arr,int left,int right)
{
	int temp=arr[left];
	while(left<right)//直达left和right重合的时候，才找到合适的位置
	{
		//先从后往前找比基准小的
		while(left<right  &&  arr[right]>=temp)//当right的值大于temp的值的时候才执行
		        //等号一定得写，因为可能会出现，保存的temp元素和数据中的元素一样的，不写会出现死循环的现象
		{
			right--;
		}
		arr[left]=arr[right];//当right的值小于temp的值的时候执行
		//从前往后找，找比基准大的
		while(left<right  && arr[left] <=temp)//当left的值小于temp的值的时候执行
		{
			left++;
		}
		arr[right]=arr[left];//当left的值大于temp的时候执行
	}
	arr[left]=temp;//此时的left和right在同一个位置，此时为合适的位置，把temp的值给left
	return left;//此时返回的值是temp合适的位置，即小于它的在它的左边，大于它的在它的右边
}
 void quick(int *arr,int left,int right)
{
	if(left<right)
	{
		int pivot=partition(arr,left,right);
		quick(arr,left,pivot-1);
		quick(arr,pivot+1,right);
	}
}
void quick_sort(int *arr,int len)
{
	quick(arr,0,len-1);
}
int main()
{
	int arr[]={9,5,7,10,45,12};
	int len=sizeof(arr)/sizeof(arr[0]);
	quick_sort(arr,len);
	for(int k=0;k<len;++k)
	{
		cout<<arr[k]<<"  ";
	}
	cout<<endl;
}

#include<stack>
#include<iostream>
using namespace std;
 
int partition(int *arr,int left,int right)
{
	int temp=arr[left];//基准
	while(left<right)
	{
		//先从后往前找比基准小的
		while(left<right && temp<=arr[right])
		{
			right--;
		}
		arr[left]=arr[right];
		//从前往后找比基准大的
		while(left<right  && temp>=arr[left])
		{
			left++;
		}
		arr[right]=arr[left];
	}
	arr[left]=temp;
	return left;
}
//其实就是用栈保存每一个待排序子串的首尾元素的下标
void q_sort(int *arr,int left,int right )
{
	stack<int>  st;
	int pos=0;
    st.push (left);
	st.push (right);
	while(!st.empty())
	{
		right=st.top();
		st.pop();
		left=st.top();
		st.pop ();//5,6,8,2,9,4,1,3,45,89,65
		pos=partition(arr,left,right);
		if(pos+1<right)//先入基准右边的，如果基准右边只有一个元素的时候，就不用入了
		{
			st.push (pos+1);
			st.push (right);
		}
		if(pos-1>left)//再入基准左边的，如果基准左边只有一个元素的时候，就不用入了
		{   
			st.push (left);
			st.push (pos-1);
			
		}
	}
}
 
void quick_sort(int *arr,int len)
{
	q_sort(arr,0,len-1);
}
int main()
{
	int arr[]={5,6,8,2,9,4,1,3,45,89,65};
	int len=sizeof(arr)/sizeof(arr[0]);
	quick_sort(arr,len);
	for(int i=0;i<len;i++)
	{
		cout<<arr[i]<<"  ";
	}
	cout<<endl;
}

//*************************************************************************
void swap(int *arr,int left,int right)
{
int temp;
temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;	
}
//***************************************************************************
int partition(int *arr,int left,int right)
{

//***************************
//e.g：9,1,5,8,3,7,4,6,2
int m=left+(right-left)/2;//找到中间的数字的下标
if(arr[left]>arr[right])//最左大于最右的时候，交换左右
{
swap(arr,left,right);
}
if(arr[m]>arr[right])//如果中间的>right ,交换
{
swap(arr,m,right);
}
if(arr[m]>arr[left])//如果中间的>left，交换
{
swap(arr,m,right);
}
//经过交换之后low变为3
//****************************
int temp=arr[left];//基准
while(left<right)//知道left和right重合的时候，才找到合适的位置
{ //从后向前找到比小的数字
while(left<right && arr[right]>=temp)//当right的值大于temp的值的时候才执行
{
right--;
}
arr[left]=arr[right];//当right的值小于temp的值的时候执行
while(left<right && arr[left] <= temp)//从前往后找到比基准大的数字
{
left++;
}
arr[right]=arr[left];//当left的值大于temp的时候执行
}
arr[left]=temp;//此时的left和right在同一个位置，此时为合适的位置，把temp的值给left
return left;//此时返回的值是temp合适的位置，即小于它的在它的左边，大于它的在它的右边
}

/*随机选择枢轴的位置，区间在low和high之间*/  
int SelectPivotRandom(int arr[],int low,int high)  
{  
  //产生枢轴的位置  
   srand((unsigned)time(NULL));  
  int pivotPos = rand()%(high - low) + low;   
  //把枢轴位置的元素和low位置元素互换，此时可以和普通的快排一样调用划分函数  
  swap(arr[pivotPos],arr[low]);  
   return arr[low];  
}  

#define  max_len  10
void quick(int *arr,int left,int right)
{
    int length=right-left;
    if(length>max_len )
    {
        int pivot=partition(arr,left,right);
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    else
    {
    //用插入排序
    }
}