快速排序(代码通俗易懂,干净整洁)

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言

快速排序的特点
1、快速排序是对冒泡算法的改进。
2、快速排序的基本思想是对要排序的数组进行划分,使左边的小于某个数,右边的大于某个数。重复执行以上划分,直到有序为止。(这里主要针对递增排序)


提示:以下是本篇文章正文内容,下面案例可供参考

一、快速排序思路

(1)定义两个变量low、high分别标识数组的第一个元素下标和最后一个元素下标。
(2)定义变量key先存储第一个数组arr[0],以后key的值都为划分后的第一个元素
(3)先从数组的后面看起,high–直到发现有一个数小于key,arr[low]=arr[high],由于此时已经确定arr[low]比key小了,所以low++。直到low=high。
(4)利用递归来实现对已经划分的数组再次划分,直到划分的左右两边都只有一个数。

二、快速排序代码

代码如下:

void QuickSort(int *arr,int low,int high){
		if(low<high){//不加这个条件会死循环 
		int i=low;
		int j=high;
		int key=arr[low];
		while(i<j){
			while(i<j&&arr[j]>=key)
				j--;
			if(i<j) 
				arr[i++]=arr[j];//先赋值在自增 
			while(i<j&&arr[i]<key)
				i++;
			if(i<j)
				arr[j--]=arr[i];//先赋值在自增				
		}
		arr[i]=key;
		QuickSort(arr,low,i-1);//给左边排序 
		QuickSort(arr,i+1,high);//给右边排序 
	   }
	}
	

三、读入数据

代码如下:

int main(){
		int a[11]={25,1,12,25,10,10,34,900,23,12,80};
		QuickSort(a,0,10);
		int i;
		for(i=0;i<11;i++){
			printf("%d ",a[i]);
		}
		return 0;
	}

执行结果:

1 10 10 12 12 23 25 25 34 80 900
--------------------------------
Process exited after 0.01681 seconds with return value 0
请按任意键继续. . .

总结

快速排序用到了划分的思想,递归算法。