一、基本概念
找到元素作为基准(pivot )，对数组进行分割操作，使基准左侧的元素的值不大于基准值，使基准右侧的元素的值不小于基准值，将基准元素调整到重新排列后的正确位置。 递归排序，其他n-1个元素也调整到排序后的正确位置。 最后一个元素位于排序后的正确位置，排序完成。 因此，快速排序算法的中心算法是如何调整分割操作(即，基准的位置)以及如何调整返回基准的最终位置以进行分割递归。
二.选择基准元
1、固定基准元
如果输入序列是随机的，则处理时间是可以接受的。 如果序列已经有序，此时的分割是非常差的分割。 在这种情况下，最差的情况是快速排序，因为每个分区只能减少一个要排序的序列，并且时间复杂度为(n^2)。 此外，输入的数据有序或部分有序的情况相当常见。 因此，把第一个要素作为基准来使用是非常糟糕的事情，应该马上放弃这个想法。
2、随机基准元
这是一个比较安全的战略。 因为基准原始位置是随机的，所以生成的分割也不是总是坏的分割。 整个序列数字均相等时，仍然是最坏的情况，时间复杂度为o(n^2)。 实际上，随机化高速排序得到理论最坏情况的可能性只有1/(2^n )。 因此，随机化高速排序可以实现对大多数输入数据的o(nlog )所期望的时间复杂度。
三三的数字对
最佳分割是将要排序的序列分割成等长的子序列，最佳状态可以使用序列的中间值，即，第N/2个数量。 但是，这很难计算，快速排序的速度明显变慢。 通过随机选择三个元素并以这些中值为基准元素，可以得出这样的中值估计。 事实上，随机性没什么用。 因此，通常使用三个元素(左端、右端和中心位置)的中值作为基准元素。
三.分区算法
分区算法是快速排序的核心。 在学习快速排序之前，请先学习这个算法。 事先贴好代码：
publicintpartition(int[]num，int left，intright ) if ) num==null|| num.length=0||| right=num.light
(int prio=num [ left (右左)/2]； //获取数组中间元素的下标
while(left=right )//从两端交替向中间扫描
wile(num[left]
左足； while(num[right]prio ) )。
right----； if(left=right ) {
swap(num、left、right )； //最终返回基准数
左足；
right----；
}
}返回左；
}
这种方法的想法是，首先找到枢轴，从数组两侧(具体来说，从哪里到哪里由传输额参数决定)生成两个指针left和right，每当左侧的元素大于枢轴I，右侧的元素小于枢轴j时停止，然后停止直到两个指针left，right相遇。 然后，将集线器插入left的位置，即它应该所在的位置。
这样的结果，在排列的[left，right]部分出现两个部分，集线器的最终位置在左侧为集线器以下，在右侧为集线器以上。 集线器已插入到绝对正确的位置。
四.排序算法的实现
打包软件； /**快速排序
快速排序采用分割策略。 就是在一个数组中取基准数字，把小的放在基准的左边，把大的放在基准的右边。
*标准的左边和右边分别是新序列。 在新序列中再取一个基准数字，小的放在左边，大的放在右边。
*用于此的递归。 需要三个参数。 一个是数组，另两个是数组的边界
*@authorHJS*/
公共类快速排序{ void sort (intnum [ ]，int left，intright ) { if } left }
sort(num，left，index-1 )； //对低个子表递归排序
sort(num，index 1，right )； //递归排序高子表
}
}/* * *调用分区(num、left、right )时为num ) )。
*返回基准记录位置
*@paramnum
*@paramleft
*@paramright
*@return
*/
publicintpartition(int[]num，int left，intright ) if ) num==null|| num.length=0||| right=num.light
(int prio=num [ left (右左)/2]； //获取数组中间元素的下标
while(left=right )//从两端交替向中间扫描
wile(num[left]
左足； while(num[right]prio ) )。
right----； if(left=right ) {
swap(num、left、right )； //最终返回基准数
左足；
right----；
}
}返回左；
}公共void swap (int [ ] num，int left，intright ) {int temp=num[left]；
num[left]=num[right]；
num[right]=temp；
} publicstaticvoidmain (string args () int ) ) num={ 7、3、5、1、2、8、9、2、6 }； new QuickSort ().sort ) num，0，num.length-1 )； for(intn3360num ) {
system.out.print(n ' )；
}
}
}