1.快速排序双边循环发和单边循环法
package sort;
public class QuickSort {
public static void main(String[] args){
int a[] = {6,4,22,67,89,12,34,65,12,3,6,22,99};
quickSort(a,0,a.length-1);
for(int i : a)
System.out.print(i + " ");
}
private static void quickSort(int[] a, int startIndex, int endIndex) {
if(startIndex >= endIndex)
return;
//快速排序双边循环法
int pivotIndex = twowayPartion(a,startIndex,endIndex);
//快速排序单边循环法
// int pivotIndex = singlePartition(a,startIndex,endIndex);
quickSort(a,startIndex,pivotIndex -1);
quickSort(a,pivotIndex + 1,endIndex);
}
/**
* 双边循环法思路：
* 1.将第一个元素作为基准元素，记录初始和结束位置
* 2.先从右边开始遍历,当元素大于基准元素时，指针前移
* 3.再从左边开始遍历，当元素小于或等于基准元素时，指针后移
* 4.交换两者的位置
* 5.循环结束后，交换基准元素和最终的初始位置的元素
* 6.返回最终的初始位置
*
* 注意点：必须先从右边开始遍历，然后才能进行左边遍历
* 因为快排是要基准元素左边都是比它小的元素，如果先从左边开始遍历，
* 可能会在比它大的位置停止循环，跳出循环后跟基准元素交换位置，导致左边的元素比基准元素打
* 例子：
* <>
* 6 1 2 7 9
* 如果先从左边开始，第一次循环会在7的位置结束，然后 6跟7 交换位置导致错误
*/
private static int twowayPartion(int[] a, int startIndex, int endIndex) {
int pivot = a[startIndex];
int start = startIndex;
int end = endIndex;
while(start < end){
if(start < end && a[end] > pivot) end--;
if(start < end && a[start] <= pivot) start++;
if(start < end){
int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
}
}
a[startIndex] = a[start];
a[start] = pivot;
return start;
}
/**
* 单边循环法思路：
* 1.将第一个元素作为基准元素
* 2.用mark标识第一个元素位置，标识小于基准元素的区域
* 3.在基准元素的后一个位置开始遍历，如果大于基准元素，指针后移
* 4.如果遍历的元素小于基准元素，先后移mark指针，然后交换当前位置跟mark位置的元素
* 5.最后交换第一个元素和mark指针位置的元素
*/
private static int singlePartition(int[] a, int startIndex, int endIndex) {
//小于主元素的区域标识
int mark = startIndex;
//主元素
int pivot = a[startIndex];
for(int i = startIndex +1; i<= endIndex;i++){
if(a[i] < pivot){
mark++;
int tmp = a[mark];
a[mark] = a[i];
a[i] = tmp;
}
}
//最后主元素跟mark位置的元素交换位置
a[startIndex] = a[mark];
a[mark] = pivot;
return mark;
}
}
2.堆排序
package sort;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int a[] = {6,4,22,67,89,12,34,65,12,3,6,22,99};
heapSort(a);
System.out.println(Arrays.toString(a));
}
/**
*堆排序思路
*1.先从最后一个非叶子节点(n-2)/2开始，进行下沉操作，使父节点大于子节点
*2.非叶子节点从最后一个遍历到第一个，构建最大堆
*3.删除堆顶，将堆顶元素和最后一个元素交换位置（传入数组长度减1）
*4.最后出来的数组就是升序数组（从小到大数组构建最大堆，从大到小数组构建最小堆）
*/
private static void heapSort(int[] a) {
int len = a.length;
if(len <= 1) return;
for(int i = (len -2)/2; i >= 0; i--){
downAdjust(a,i,len);
}
for(int i = len - 1; i >= 0; i--){
int tmp = a[i];
a[i] = a[0];
a[0] = tmp;
downAdjust(a,0,i);
}
}
/**
* 下沉操作思路：
* 1.在数组长度len范围内，找到parentIndex的第一个子节点 childIndex = parentIndex * 2 + 1
* 2.若有第二个子节点，则需要比较，将较大的子节点序号赋值给childIndex
* 3.如果父节点的值已经大于两个子节点了，需要跳出循环
* 4.每次循环结束，都要先交换父子节点的值，然后建父节点的下标设置为子节点下标，重新计算子节点下标
* 5.跳出循环后，需要将之前缓存的第一个父节点的值赋值给最后的parentIndex
*/
private static void downAdjust(int[] a, int parentIndex, int len) {
int parentVal = a[parentIndex];
int childIndex = 2 * parentIndex + 1;
while(childIndex < len){
if(childIndex + 1 < len && a[childIndex + 1] > a[childIndex])
childIndex++;
if(a[parentIndex] > a[childIndex])
break;
a[parentIndex] = a[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
a[parentIndex] = parentVal;
}
}
3.快排和堆排序的对比
（1）快排的堆排序的时间复杂度都是（nlogn）,但是快排的最差时间是n^2,堆排序稳定在（nlogn）
（2）快排和堆排序都是不稳定排序
（3）快排的平均控件复杂度为（logn）,堆排序的空间复杂度为（1）
（4）快排的效率一般比堆排序高。
- 一是堆排序构建完最大（小）堆后，都需要将最后一个元素跟第一个元素交换，然后重新构建最大（小） 堆，这导致了许多无谓的比较，而快排每次比较交换值都是在向最终结果靠近；
- 二是堆排序大多是随机存取数据，而快排则是顺序存储数据。
这导致的结果虽然快排和堆排序都是（n*logn），但是两者的常数基数不一样，快排比堆排序要小。
