快速排序——排序算法中平均情况下速度最快的一种排序方法

1 概述

快速排序（quick sorting）是对气泡排序的一种改进，是关键字次数少，速度较快的一种排序方法。

2 基本思想

简单概括就是：给基准数据找到其正确的索引位置；
具体原理如下：
1）如下图所示，假设目前的基准数据是第一个，也就是元素15，用一个临时变量temp保存元素15，temp=15；然后分别用low和high记录数组的最大和最小下标。

2）首先从后往前开始扫描，如果high对应的元素不小于基准数据，那么high–，也就是把high往前移动一个位置，如果high对应的元素小于基准数据，那么将high所对应的元素赋值给low所对应的元素，。上图中2<15,那么结果如下：

3）然后从前往后开始扫描，如果low对应的元素不大于基准数据，那么low++，也就是把low往后移动一个位置，如果low对应的元素大于基准数据，那么将low所对应的元素赋值给high所对应的元素。上图中2<15,那么结果如下：

此时依旧从前往后开始扫描，直到发现low对应的元素大于基准数据。此时的low对应元素24大于基准元素15，因此，结果如下：

4）重复2）步骤，结果如下：

重复2）步骤，结果如下：

5）重复3）步骤，结果如下：

重复3）步骤，结果如下：

重复3）步骤，结果如下：

6）重复2）步骤，结果如下：

重复2）步骤，结果如下：

重复2）步骤，结果如下：

此时low等于high，那么说明这个位置就是基准数据的正确索引位置；结果如下

如此重复，其实会发现，这种做法的实质就是将不大于基准数据的元素放在基准数据的左边，不小于基准数据的元素放在基准数据的右边，然后使用递归的方式对数据的前后半部分进行排序，直到结束即可。

3 代码演示

#include<stdio.h>

int main()
{
	int arr[]={47,34,66,84,70,19,22,47},*p=arr;
	int i,j,len;
	printf("请将以下数据升序排列！n");
	len = sizeof(arr)/sizeof(arr[0]);
	for(i=0;i<len;i++){
		printf("%-4d",*(arr+i));
	}
	
	void quick_sorting_all(int *p,int low,int high);
	quick_sorting_all(p,0,len);
	
	printf("n排序后的序列如下！n");
	for(i=0;i<len;i++){
		printf("%-4d",*(p+i));
	}
	return 0;
} 


//  用于实现移动的函数，返回基准值所对应的下标值
int quick_sorting_part(int *p,int low,int high)
{
	int temp=*(p+low);  // 基准值
	while(low<high){  // 只要low小于high值 
		while(low<high && temp<=*(p+high)){  //low小于high，并且基准值小于其右边的值 
			high--;
		}
		*(p+low)= *(p+high);  //如果基准值大于其右边儿的值，将 high的值赋值给low 
		while(low<high && temp>=*(p+low)){  //low小于high，并且基准值小于其右边的值 
			low++;
		}  
		*(p+high)= *(p+low);  //如果基准值小于其左边儿的值，将 low的值赋值给high
	}
	*(p+low)=temp;
	return low;
}


void quick_sorting_all(int *p,int low,int high)
{
	if(low<high){
		int index=quick_sorting_part(p,low,high);
		quick_sorting_all(p,low,index-1);
		quick_sorting_all(p,index+1,high);
	}
}

最后

以上就是彩色电源为你收集整理的快速排序——排序算法中平均情况下速度最快的一种排序方法的全部内容，希望文章能够帮你解决快速排序——排序算法中平均情况下速度最快的一种排序方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。