【第22次讨论主题：排序】
1）快排的原理是什么？快速写一段核心代码实现。
快速排序原理:采用的是分治法,同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较 和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端， 而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移 动到数列一边，
比它小的元素移动到数列的另一边，从而把数列拆解 成两个部分。快速排序算法总体的平均时间复杂度 是O(nlogn)。
基准元素的选择，以及元素的交换， 都是快速排序的核心问题。
基准元素的选择：最简单的方式是选择数列的第1个元素，或者就是随机选取一个
元素的交换：1. 双边循环法。2. 单边循环法
public static void quickSort(int[] arr, int startIndex,int endIndex){
// 递归结束条件：startIndex大于或等于endIndex时
if (startIndex >= endIndex) {
return;
}
//获取基准元素的下标位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两部分进行递归排序
//左边的
quickSort(arr, startIndex, pivotIndex - 1);
//右边
quickSort(arr, pivotIndex + 1, endIndex);
}
// 单边循环
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1个位置（也可以选择随机位置）的元素作为基准元素
int pivot = arr[startIndex];
int mark = startIndex;
for(int i=startIndex+1; i<=endIndex; i++){
//获得小于基准位置元素的元素
if(arr[i]<pivot){
//1.mark 向右移动,使得左侧空间变大
mark ++;
//2.交换元素
int p = arr[mark];
arr[mark] = arr[i];
arr[i]=p;
}
}
//最后将 mark 位置的元素和pivot基准元素做交换
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}2) DualPivotQuicksort的sort代码实现int排序的原理和关键步骤。
1. sort(int[] a, int left, int right,int[] work, int workBase, int workLen);中
// 如果排序长度小于286,这直接进入双轴快排
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
//如果排序长度大于67个，进行双轴快排，否则使用归并排序。
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
2.//sort（sort(int[] a, int left, int right, boolean leftmost)）方法中
//长度小于此值 47 使用插入排序
if (length < INSERTION_SORT_THRESHOLD) {
...
}else{
...大于此值使用快速排序
}
参考链接：
作业：图解快速排序原理以及java实现
https://blog.csdn.net/u010430495/article/details/88388057
https://blog.csdn.net/fjtooo/article/details/90244584
Dual-Pivot QuickSort
https://www.jianshu.com/p/2c6f79e8ce6e 快速排序算法
https://blog.csdn.net/Backee/article/details/90048052 单轴快排（SinglePivotQuickSort）和双轴快排（DualPivotQuickSort）及其JAVA实现
https://blog.csdn.net/holmofy/article/details/70245895 常见排序算法及JAVA实现
==========优秀同学的回答：
姚子健
12日15日 23.59.59截止
【第22次讨论主题：排序】
1）快排的原理是什么？快速写一段核心代码实现。
1.1快排核心原理
首先快排的核心思想是算法常用四大思想贪心、分治、回溯、动态规划中的分治
分治是解决复杂问题拆分并简单化的一种思维
贪心就是求解过程多个步骤选择最优解
配合回溯可以减少遍历，也就是缓存思想
动态规划就是复杂问题简单化公式化递归思想。
我算法也不是特别好一直在学习，算法思想只能描述到这。
其次具体操作就是选择一个核心数据结点当作比较值Pivot
通过遍历数组中的数据和Pivot做比较
小于的放左边大于的放右边
同时该算法也演变出很多具体场景的优化算法
比如三路快排就是为了解决数组中重复元素比较多的情况下的无效比较。
但是三路快排在绝对无重复的情况下性能并不如普通快排
因为维护了多个无意义的指针以及无意义的比较。
这里测试数据就不放出来了
因为计算机硬件和使用的语言不一样，都会导致结果的误差，这个我非常肯定。
举个例子归并排序的合并有一个优化就是合并之前对中间数据的比较减少有序合并代码如下
sort(arr, l, mid);
sort(arr, mid + 1, r);
if( arr[mid]>arr[mid+1] ){
merge(arr, l, mid, r);}
理论上可以起到优化，实际上性能可能会更差，我用的可能谁能保证你是一台什么计算机。。
因为这里多了一个if判断，但是读取arr[i]的数据严重依赖cpu的cache line
所以如果arr[mid]和arr[mid+1]都在cpu缓存那性能很高，否则的话不见得能快到哪里，速度甚至更慢。
速度甚至更慢，这也是DualPivotQuicksort的核心优化点。
现代计算机算法不能用以前的传统意义上的时间复杂度来衡量！
应该从交换次数，数据访问次数，比较次数，cpu缓存
1.2代码如下：
首先这个代码只是基础快排，并没有再优化绝对有序的情况下算法退化问题
因为绝对有序的情况下会退化成O(n2)的时间复杂度
一般就是随机数和第一个元素替换,这样可以避免退化
不过更好的优化是直接遍历一下是否有序或者逆序，然后再选择合适的算法
这也是看DualPivotQuicksort学来的，归并排序对于相对有序数组来说比快排性能要更好。
/**
- Todo if判断之后随机获取数组一个数和第一个元素交换，swap( arr, left , random() );
*/
public static void sort(int a[],int left,int right){
if (a==null||left>=right){
return;
}
int j =left;
int v = a[left];
for (int i=left+1;i<=right;i++){
if(a[i]<v){
j ++;
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
a[left] = a[j];
a[j] = v;
sort(a,left,j-1);
sort(a,j+1,right);}
2) DualPivotQuicksort的sort代码实现int排序的原理和关键步骤。
DualPivotQuicksort主要实现原理是利用了各种算法的特性综合实现
先说代码实现步骤再说具体原理为代码如下
可以分为两个大步骤
2.1 归并或者快排的选择
1.if(arr<286)使用快速排序
2.判断数组是否有序以及有序程度，如果发现数组并不是特别有序使用快排
3.以上判断结束有序则直接返回，否则使用归并排序，
这里归并排序直接初始化了一个排序数组一样大小工作空间数组，减少数组空间的开辟算一个优化点。
2.2 快排
这里已经进入到快排的代码块主要步骤如下
1.if (length < INSERTION_SORT_THRESHOLD)如果下于47则使用插入排序
这个插入排序真心牛逼的不行，优化到了极致，后面再说具体怎么优化
因为得了解DualPivotQuicksort的排序做法才能懂。
2.超过47的情况下将数据除以近似7
int seventh = (length >> 3) + (length >> 6) + 1;
int e3 = (left + right) >>> 1; // The midpoint取中间值
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
接着给上面五个元素手动排序，注意是手动也是一个优化，避免重复循环，《逆序对》思想其实在这有体现。
3.比较上面五个元素，如果都重复说明数组重复概率很大，使用三路快排。
三路快排就是为了解决重复元素无效比较而出现。
4.否则使用双轴快排，这个其实就是在单轴的普通快排上面多增加了一个比较轴
这有什么好处了？
首先使得快排数据拆分更均匀，快排的不稳定也是由于拆分不均匀导致
比如说绝对有序的数组使用快排就会导致一边倒，直接O(n2)
在步骤2中其实也涉及到拆分均匀的思路在里面
其次使得数组可以拆分成更小的模块，这有利于cpu缓存的利用提高性能。
众所周知计算机多级缓存，cpu中运行最快但是空间最小。
合理拆分小数组可以在cpu中加载的比较数据更多，比较速度自然快
不得不佩服 Vladimir Yaroslavskiy的思路，打破了常规的算法性能认知。
5.最后统一的递归
sort(a, left, less - 1, leftmost);
sort(a, great + 1, right, false);
这里就是步骤一中说到的优化
到这里我们自然很明白左边的数据肯定是小于右边的数据
所以当leftmost为true使用传统插入排序
false使用优化过后的双数据插入
主要优化点还是false情况下的优化代码具体如下，
//直接一个while完全不用管越界问题了
while (a1 < a[--k]) {
a[k + 2] = a[k];}
传统的如下，每次循环都要判断越界
if (j-- == left) {
break;}
为什么左边的不使用这种方式
这根本不用想，不是不能实现，而是强行排序几个小元素放前面性能下滑太厉害
还不如直接使用传统方式
插入排序在数组较小的情况下理论上同样的确不如快排，但是稳定啊
并且减少了递归的消耗，数据全在cpu中计算，毕竟几十k的空间还是有的
高级排序算法的优化常用手段就是配合插入排序一块玩
最后有几个关键数字比如为什么是47还有为什么是286
其实DualPivotQuicksort这个代码的执行逻辑我在上个星期就能说明白
一直在思考的也是这个问题，后面我得出结论
根据时间复杂度的计算魔法数的选择范围
接着作者对于代码的优化，加上不同场景的数据测试选择了这么一个数字
群名片名字:张浩
【第22次讨论主题：排序】
1）快排的原理是什么？快速写一段核心代码实现。
原理：基于“分治”（divide-and-conquer）的思想，所以第一步就是“分”，把数据分成几分（两份），选取一个关键数a，把数据集合分成两部分，array1中的所有数都小于a，array2的所有数都不小于a；然后用 递归排序，来对两个子集合的数据进行排序。时间复杂度比较复杂，最好的情况是O(n)，最差的情况是O(n2)，所以平时说的O(nlogn)，为其平均时间复杂度。空间复杂度为O(log2n)。为什么说这个排序算法是非常优秀的算法了，抛开最好和最差的两种情况，即，在一般情况下，他的时间复杂度都是趋近于O(nlogn)，换一种说法就是，快排的运行时间不依赖于输入序列的顺序。在排序考虑算法的时候，我们要考虑的都是最普通的情况而不是特殊的情况，由于快排在很多普通的情况下，时间复杂度都是O(nlogn)，所以说快排很稳点，对内存的占用也非常小，相比于 其他算法，节省了内存空间。
我觉得核心的代码，就是递归方法
//快速排序split实现方法
//划分数组
public static int split(int a[], int low, int high)
{
int i = low; //i指向比较元素的期望位置
int x = a[low]; //将该组的第一个元素作为比较元素
//从第二个元素开始，若当前元素大于比较元素，将其跳过
for(int j = low+1; j <= high; j++)
//若找到了小于比较元素的元素，将其与前面较大的元素进行交换
if(a[j] <= x)
{
i++;
if(i != j)
swap(a, i, j);
}
swap(a, i, low); //将比较元素交换到正确的位置上
return i; //返回比较元素的位置
}
2) DualPivotQuicksort的sort代码实现int排序的原理和关键步骤。
DualPivotQuicksort使用了两个pivot加速。思想如下：
1) 选择两个点作为轴心,P1,P2。
2)P1必须比P2要小，现在将整个数组分为四部分：
（1）第一部分：比P1小的元素。
（2）第二部分：比P1大但是比P2小的元素。
（3）第三部分：比P2大的元素。
（4）第四部分：待比较的部分。
在开始比较前，除了轴点，其余元素几乎都在第四部分，直到比较完之后第四部分没有元素。
3）.从第四部分选出一个元素a[K]，与两个轴心比较，然后放到第一二三部分中的一个。
4）.移动L，K，G指向。
5）.重复 3）和4） 步，直到第四部分为空。
6）.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。
7）.递归的将第一二三部分排序。
DualPivotQuicksort提出了一种“扫描元素个数”的思想，我们知道，以前的算法都是基于“元素比较次数”来评价一个算法好坏的，在这种新的算法里面，我们把对于数组里面一个元素的访问:array[i] 称为一次扫描。但是对于同一个下标，并且对应的值也不变得话，即使访问多次我们也只算一次。而且我们不管这个访问到底是读还是写。
其实这个所谓的扫描元素个数反应的是CPU与内存之间的数据流量的大小。
在这种新的算法下面经典快排和Dual-Pivot快排的扫描元素个数分别为:
1.5697nlnn VS 1.4035nlnn
也就是说经典快排确实进行了更多的元素扫描动作，因此也就比较慢。在这种新的算法下面，Dual-Pivot快排比经典快排t节省了12%的元素扫描，从实验来看节省了10%的时间。
参考：
1.http://open.163.com/newview/movie/free?pid=M6UTT5U0I&mid=M6V2T7IS4，这个是网易公开课，是外国大学教授讲快排的原理和为什么快排很优秀的原因，
也是我第一个回答主要参考的对象；
2.https://blog.csdn.net/u010786672/article/details/42580899
3.https://www.jianshu.com/p/2c6f79e8ce6e
4.https://blog.csdn.net/jek123456/article/details/79727686
5.https://www.cnblogs.com/su
刘鹏飞【第22次讨论主题：排序】
1）快排的原理是什么？快速写一段核心代码实现。
原理：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边（这种处理方式称为分治法）。
3．再对左右区间重复第二步，直到各区间只有一个数。
数据的移动是基准元素中比较重要的点，有两种方式实现，挖坑填数法和指针交换法。
核心代码：
public class DiyQuickSort {
public static void sort(int a[], int low, int length) {
int i, j, index;
if (low > length) {
return;
}
i = low;
j = length;
index = a[i];
while (i < j) {
while (i < j && a[j] >= index) {
j--;
}
if (j > i) {
a[i] = a[j];
i = i + 1;
}
while (i < j && a[i] < index) {
i = i + 1;
}
if (j > i) {
a[j] = a[i];
j--;
}
}
a[i] = index;
sort(a, low, i - 1);
sort(a, i + 1, length);
}}
2) DualPivotQuicksort的sort代码实现int排序的原理和关键步骤。
JDK里面直到JDK6用的都是这种经典快排的算法。但是到了JDK7的时候JDK内置的排序算法已经由经典快排变成了Dual-Pivot排序算法。在经典快排里面有一个pivot的概念，它是用来分隔大数和小数的 -- 这个pivot把一个数组分成两份。那么所谓的Dual-Pivot其实就是用两个Pivot, 把整个数组分成三份。
原理：首先检查数组的长度，比一个阈值小的时候直接使用双轴快排。其它情况下，先检查数组中数据的顺序连续性。把数组中连续升序或者连续降序的信息记录下来，顺便把连续降序的部分倒置。这样数据就被切割成一段段连续升序的数列。
代码中的关键步骤：
sort排序主要目的最短的时间完成排序，所以会通过不同长度的int，来使用相对效率最高的排序方法，步骤如下：
第一段：
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}第二段：
先判断排序的长度，如果长度小于（QUICKSORT_THRESHOLD = 286 ）此值使用快速排序，大于此值使用归并排序。
if (length < INSERTION_SORT_THRESHOLD) {
…
}
判断排序的长度，如果长度小于（INSERTION_SORT_THRESHOLD = 47 ）此值使用插入排序，大于此值使用快速排序。
第三段：
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
判断数组中有序数列的个数超过了（MAX_RUN_COUNT=67）使用快速排序，否则使用归并排序。
第四段：
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
数列中有至少（MAX_RUN_LENGTH=33）的数据相等的时候，直接使用快速排序。
常量中除了QUICKSORT_THRESHOLD其余都是用来选择排序算法的，选择排序算法主要考虑元素个数。
- 当元素个数大于元素种数，使用归并排序。
- 当元素个数较多且基本有序（递增片段较少），使用归并排序。
- 当元素个数较多且较为无序，使用快速排序。
- 当元素个数较少，使用插入排序。
双轴快速排序：
通过1/7的近似值，获取靠近中间的5段数列排序。
使用5个元素中的2，4两个位置，他们两个大致处在四分位的位置上, 称之为pivot1和pivot2。
pivot1和pivot2都从数组中选出, pivot1在pivot2的右侧, 且pivot1必须小于pivot2, 如果不是, 则交换pivot1和pivot2的值;
接下来令数组中的每一个元素和基准进行比较, 比pivot1小的放在pivot1左边, 比pivot2大的放在pivot2右边, 介于两者之间的放在中间.
这样, 最终我们会的得到三个数组, 比pivot1小元素构成的数组, 介于pivot1和P2之间的元素构成的数组, 以及比pivot2大的元素构成的数组.
最后, 递归地对这三个数组进行排序, 最终得到排序完成的结果。
