快排的优化思想及基于C语言的实现

野性酷女 2023-06-23 13:28 16阅读 0赞

## 快排的优化三大方法 ##

> 方法一：随机值法  
> 方法二：三位取中法  
> 方法三：插排替代法

对于代码写的很细，便于理解原理，所有思路都很简单。

##### 方法一：随机值法 #####

优化思路：普通快排每次选择基准的时候一般选择为左端点，但是如果此序列是一个有序或基本有序序列，则选择最左或最右为基准反而是最坏情况。所以我们对此进行优化。  
**主要思想：最简单的想法，我们不以最左或最右为基准，我们随机挑选一个数作为基准，这个方法虽然简单但是优化程度完全看你运气了哈哈哈。**  
如果想要更优可以看后面方法，但此方法较为简单，便于理解，且有时候运气好还真挺好。

#include<stdio.h>
    #include<stdlib.h>
    
    void quicksort(int arr[],int len);			//快排总函数
    void quick(int arr[],int left,int right);			//快排递归函数
    int partition(int arr[],int left,int right);		//快排的核心交换函数
    void swap(int arr[],int a,int b);			//交换函数
    void print(int arr[],int len);				//打印函数
    
    void quicksort(int arr[],int len)
    { 
    	if(arr == NULL || len < 2)
    		return;
    	quick(arr,0,len-1);
    }
    void quick(int arr[],int left,int right)
    { 
    	int k;
    	if(left < right)
    	{ 
    		swap(arr,left,rand() % (right-left+1) + left);	//随机选取一个数置于左端点作为基准（优化程度完全看运气了） 
    		k = partition(arr,left,right);
    		quick(arr,left,k-1);
    		quick(arr,k+1,right);
    	}
    }
    int partition(int arr[],int left,int right)
    { 
    	int stad = arr[left];
    	while(left < right)
    	{ 
    		while(arr[right] >= stad && left < right)
    			right--;
    		arr[left] = arr[right];
    		while(arr[left] <= stad && left < right)
    			left++;
    		arr[right] = arr[left];
    	}
    	arr[left] = stad;
    	return left;
    }
    void swap(int arr[],int a,int b)
    { 
    	int t;
    	t = arr[a];
    	arr[a] = arr[b];
    	arr[b] = t;
    }
    void print(int arr[],int len)
    { 
    	for(int i = 0;i < len;i++)
    	{ 
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    }
    
    int main()
    { 
    	int i,n,a[100];
    	scanf("%d",&n);
    	for(i = 0;i < n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    	quicksort(a,n);
    	print(a,n);
    	
    	return 0;
    }

##### 方法二：三位取中法 #####

优化思路：普通快排每次选择基准的时候一般选择为左端点，但是如果此序列是一个有序或基本有序序列，则选择最左或最右为基准反而是最坏情况。所以我们对此进行优化。

**主要思想：先取三个特殊位置（左端点、中点、右端点）的数进行排序，将最大的数交换到右端点，将最小的数交换到中间，将中间值放在左端点，再以左端点为基准进行快排。**

#include<stdio.h> 
    void quicksort(int arr[],int len);				//快排总函数
    void quick(int arr[],int left,int right);		//快排递归函数
    void FindMiddleNumber(int arr[],int left,int mid,int right);	//完成三位排序，从小到大为中、左、右 
    void swap(int arr[],int a,int b);				//交换函数
    void print(int arr[],int len);					//打印函数
    int partition(int arr[],int left,int right);	//快排的核心交换函数
    
    void quicksort(int arr[],int len)
    { 
    	if(arr == NULL || len < 2)		//递归退出条件
    		return;
    	quick(arr,0,len-1);
     } 
    void quick(int arr[],int left,int right)
    { 
    	int k,mid;
    	if(left < right)
    	{ 
    		mid = (left+right) / 2;
    		FindMiddleNumber(arr,left,mid,right);		//三位排序
    		k = partition(arr,left,right);
    		quick(arr,left,k-1);
    		quick(arr,k+1,right);
    	}
    }
    void FindMiddleNumber(int arr[],int left,int mid,int right)
    { 
    	if (arr[mid] > arr[right])
    	{ 
    		swap(arr, mid, right);
    	}
    	if (arr[left] > arr[right])
    	{ 
    		swap(arr, left, right);
    	}
    	if (arr[left] < arr[mid])
    	{ 
    		swap(arr, left, mid);
    	}
    }
    int partition(int arr[],int left,int right)
    { 
    	int stad = arr[left];
    	while(left < right)
    	{ 
    		while(arr[right] >= stad && left < right)
    			right--;
    		arr[left] = arr[right];
    		while(arr[left] <= stad && left < right)
    			left++;
    		arr[right] = arr[left];
    	}
    	arr[left] = stad;
    	return left;
    }
    void swap(int arr[],int a,int b)
    { 
    	int t;
    	t = arr[a];
    	arr[a] = arr[b];
    	arr[b] = t;
    }
    void print(int arr[],int len)
    { 
    	for(int i = 0;i < len;i++)
    	{ 
    		if(i == len-1)
    		{ 
    			printf("%d",arr[i]);
    			return;
    		}
    		printf("%d ",arr[i]);
    	}
    }
    
    int main()
    { 
    	int i,n,a[100];
    	scanf("%d",&n);
    	for(i = 0;i < n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    	quicksort(a,n);
    	print(a,n);
    	return 0;
    }

##### 方法三 插排替代法 #####

优化思路：当数据长度较短时，用快排需要多重递归还不如插排来得快，而且快排的每次递归要排的数很少，递归明显要浪费很多的时间，用快排就太划不来了。  
**主要思想：因此，对于这个问题，我们就只需加一个判断解决，当数据长度小于某值时，我们就用插排来代替，直接排好。**  
在这里我就用20分界，长度大于20就快排，小于20时直接插排就好。

#include<stdio.h>
    #include<stdlib.h>
    
    void quicksort(int arr[],int len);			//快排总函数
    void quick(int arr[],int left,int right);			//快排递归函数
    int partition(int arr[],int left,int right);		//快排的核心交换函数
    void swap(int arr[],int a,int b);			//交换函数
    void print(int arr[],int len);				//打印函数
    void insort(int arr[],int start,int end);			//插入排序 
    
    void quicksort(int arr[],int len)
    { 
    	if(arr == NULL || len < 2)
    		return;
    	quick(arr,0,len-1);
    }
    void quick(int arr[],int left,int right)
    { 
    	int k;
    	if(right - left <= 20)		//这里我们随便设置一个分界点长度为20 
    	{ 
    		insort(arr,left,right);
    		return;
    	}
    	if(left < right)
    	{ 
    		k = partition(arr,left,right);
    		quick(arr,left,k-1);
    		quick(arr,k+1,right);
    	}
    }
    int partition(int arr[],int left,int right)
    { 
    	int stad = arr[left];
    	while(left < right)
    	{ 
    		while(arr[right] >= stad && left < right)
    			right--;
    		arr[left] = arr[right];
    		while(arr[left] <= stad && left < right)
    			left++;
    		arr[right] = arr[left];
    	}
    	arr[left] = stad;
    	return left;
    }
    void insort(int arr[],int start,int end)
    { 
    	int t,i,j;
    	for(i = start + 1;i <= end;i++)
    	{ 
    		t = arr[i];
    		for(j = i - 1;j >= start && arr[j] > t;j--)
    		{ 
    			arr[j+1] = arr[j];
    		}
    		arr[j+1] = t;
    	}
    }
    void swap(int arr[],int a,int b)
    { 
    	int t;
    	t = arr[a];
    	arr[a] = arr[b];
    	arr[b] = t;
    }
    void print(int arr[],int len)
    { 
    	for(int i = 0;i < len;i++)
    	{ 
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    }
    
    int main()
    { 
    	int i,n,a[100];
    	scanf("%d",&n);
    	for(i = 0;i < n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    	quicksort(a,n);
    	print(a,n);
    	
    	return 0;
    }