(兔C残篇)快速排序的代码实现与讲解

本文主要是介绍(兔C残篇)快速排序的代码实现与讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天周三，这篇博文讲解数组八个基本排序的快速排序。

文章目录

- - - - 1.快速排序的理论概念
      - 2. 举例讲解
      - 3. 代码实现

1.快速排序的理论概念

快速排序的思想在于分而治之。

先进行元素大小的比较，然后进行分区
也就是在排序开始时，先取出一个数，把这个数作为基数，然后进行分区，

分区也就是说和这个基数进行大小的比较，比基数大的数或者是等于它的数，全部放到它的右边。然后小于基数的数，全部放到基数的左边。

然后在对左右区间的数，重复上一步，直到区间只有一个数。

2. 举例讲解

挖坑填数，此时有一个数组，定义为：
int arr ={5,4,6,3,8,9,7,2,1};

进行上述理论概念的说明。
挖出第一个数，作为基数，
也就是下标(index =0)指向的第一个元素5，他是一个坑位，记坑位1。此时产生了第一个坑位。

然后进行第二步，由后向前找比他小的数，找到后挖出此数，填到坑位1中，也就是下标指向8，指向的元素为1。
1填到坑位1中，然后形成第二个坑位。

然后继续进行第三步，由前向后找，比他大或者是等于它的数，找到后挖出此数，填到上一个坑位中，也就是下标为2，元素值为6。将元素6填到坑位2中。并形成坑位3。

然后在重复第二步的操作，由后向前找，比他小的数，元素2，填到坑位2中，并形成坑位3.
继续从前向后找，比它大的数，或者等于它的数，元素8，填到上一个坑位中，也就是坑纹3中，并形成坑位4。

如此重复，当坑位挖到相邻时，在将基数填入当前循环的最后一个坑位中，形成第一步的闭环。

可以在纸上画着玩一下理论知识。
第一步闭环之后，会发现比5大的数都在右边，比5小的数都在5的左边。虽然是这样但是左右两边分区中的数字还是没有顺序的。所以我们需要继续对左右两遍继续重复动作。
也就是将左边分区的数，看成是一个区，继续重复挖坑填坑。右边的分区的数，也是一个独立的区域，也重复挖坑和填坑。
如此重复，最后，会把元素按照有序，重新排序好。

3. 代码实现

//我们先定义一个实现该算法的工具类
public class ArraySortUtils{//定义快速排序的方法public static void vauleSort(int arr[],int start,int end){//接收三个参数//1.数组，2.起始位置，3.结束位置//找出左右两区，分区的索引位置，然后进行递归调用if(start < end){int index = getReturnIndex(arr,start,end);vauleSort(arr,start,index-1);valueSort(arr,index+1,end);}}public static int getReturnIndex(arr,start,end){int i = start;//开始位置int j = end;//结束位置int x = arr[i];//挖到的基数//i<j 的环境下开始进行循环while(i < j){//从后往前找，如果j比基数大，移动下标while(i<j&& arr[j]>= x){j--;}if(i<j){//将挖出来的数填到坑中。arr[i] =arr[j];i++;}//从前往后找，如果i比基数小，移动下标while(i<j &&arr[i] <=x){i++;}if(i<j){arr[j] = arr[i];j--;}//最后将基数填到，循环挖出的最后一个坑位中arr[i] =x;}//最后的索引返回i和j都行，因为此时的i和j已经重合了。return i;}
}