[数据结构与算法]数据结构与算法-快速排序

一.快速排序

1.快速排序的思想

选择一个数，选出比这个数小的放在左边，选出比这个数大的放在右边。接着，用递归处理左边和右边的数。

2.递归的处理思想

不断地去执行快速排序的思想。

3.快速排序的核心

分而治之。

4.传送门

快速排序算法

二.代码

#include<iostream> 
using namespace std;
//1.初始化数组 
int arr[]={23,4,13,10,76,7,12,100,72};
//2.获取长度 
int len=sizeof(arr)/sizeof(arr[0]);

void  quickSort(int arr[],int len){   //5.传入数组元素和长度 
    //7.写返回条件 
	if(len<=1){
		return;
	}
	else{
		//6.pivot是划分序列的基准 (支点 → 基数) 
    	int pivot=arr[0]; 
    	int left=0; //左边的下标 
		int right=len-1; //右边的下标 
		while(left!=right){  //直到位置重合，再结束循环 
		 	//找一个比基数更小的数 
		 	while(left<right && arr[right]>=pivot){
		     	right--;
		 	}
		 	//找一个比基数更大的数 
			while(left<right && arr[left]<=pivot){
		     	left++;
			}
		 	//交换元素 
		 	swap(arr[right],arr[left]); 		  
		} 
		//基数和中间值交换 
		arr[0]=arr[left];
		arr[left]=pivot;
		//基数左右两侧分别用递归进行快排
		quickSort(arr,left); 
		quickSort(arr+left+1,len-left-1);  
    }  
} 

int main(){
   //3.调用函数
   quickSort(arr,len); 
   //4.遍历输出 
   for(int i=0;i<len;i++){
   	    cout<<arr[i]<<" "; 
   }
   return 0;
}

输出样例

4 7 10 12 13 23 72 76 100

三.图文解析

1.采取随机数的方式

根据前面的输出样例，可以得出：左边会排好序，右边也会排好序。

2.基数的选择方式

①选取数组中的第一个元素。

②随机选取数组中的元素。

③取中位数。（采取头、中、尾的方式，筛选出最适合的基数）

左边下标=0
右边下标=len-1
中间=（左边下标+右边下标）/ 2 = 4
              ?
结果是向下取整（floor）得出来的 ? 下标为4 ? 得出数组元素76 

四.动态图

快速排序 ? 传送门