一.快速排序补充
快速排序的分治部分还有其他方法，如挖坑法，快慢指针法。
1.挖坑法（重要）
思路：先将基准位置元素用tmp保存，假定基准位置没有值（有个坑），然后分别从前后向中间遍历，右边大于基准就减减，遇到小于基准的就放到基准值位置的坑中，左边亦然，遍历整个数组后，将基准值填入最后一个左边遍历值。
//挖坑法
public static int partition2(int[] array,int start,int end) {
int pivot = array[start];
int i = start;
while(start < end) {
while(start < end && array[end] >= pivot) {
end--;
}
array[start] = array[end];
while(start < end && array[start] <= pivot) {
start++;
}
array[end] = array[start];
}
array[start] = pivot;
return start;
}细节注意：填坑不是互换
2.快慢指针法
通过建立两个指针，一个满足小于基准值++，另一个在前一个指针不大于基准时++，大于后不再++；从而与前一个快指针换位。
//快慢指针法
public static int partition3(int[] array,int start,int end) {
int prev = start;
int cur = start+1;
while(cur <= end) {
if(array[cur] < array[start] && array[cur] != array[++prev]) {
swap(array,prev,cur);
}
cur++;
}
//把最后一个小于[prev]的值换到开头
swap(array,prev,start);
return prev;//start不行
}3.非递归法快速排序实现
思路：反复利用栈的push，pop来实现递归的效果。核心就是把分别把要排序的数据的left，right压入栈，在排序时弹出用于排序。
public static void quickSort2(int[] array) {
int left = 0;
int right = array.length-1;
int par = partition3(array,left,right);
Stack<Integer> stack = new Stack<>();
if(par > left+1) {
//left+1是为了保证最少左边右一个元素
stack.push(left);
stack.push(par-1);
}
if(par < right-1) {
//right-1是为了
stack.push(par+1);
stack.push(right);
}
while(!stack.empty()) {
right = stack.pop();
left = stack.pop();
par = partition3(array,left,right);
if(par > left+1) {
//left+1是为了保证最少左边右一个元素
stack.push(left);
stack.push(par-1);
}
if(par < right-1) {
//right-1是为了
stack.push(par+1);
stack.push(right);
}
}
}
时间复杂度：
O(N*logN)
空间复杂度：
O(logN)
稳定性：不稳定
二.归并排序（递归）
思想：
采用分治法的一个非常典型的应用，将数组分解成若干子列，先使若干子列有序，再进行合并操作递归使整个数组有序。
1.分解
利用中间值mid递归分解
public static void mergeSortFunc(int[] array,int left,int right) {
if(left == right) {
return;
}
int mid = (left + right) / 2;
//分解
mergeSortFunc(array,left,mid);
mergeSortFunc(array,mid+1,right);
}最终分解结果是各子列被分解为长度不超过2的单元
2.合并
先对最终子列排序，之后沿用这个方法递归得数组。
public static void merge(int[] array,int left,int mid,int right) {
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2= right;
int k = 0;
int[] tmpArray = new int[right - left + 1];
while(s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmpArray[k++] = array[s1++];
}else {
tmpArray[k++] = array[s2++];
}
}
while(s1 <= e1) {
tmpArray[k++] = array[s1++];
}
while(s2 <= e2){
tmpArray[k++] = array[s2++];
}
for (int i = 0; i < tmpArray.length; i++) {
array[i + left] = tmpArray[i];
}
}总代码：
public static void mergeSort1(int[] array) {
mergeSortFunc(array,0,array.length-1);
}
public static void mergeSortFunc(int[] array,int left,int right) {
if(left == right) {
return;
}
int mid = (left + right) / 2;
//分解
mergeSortFunc(array,left,mid);
mergeSortFunc(array,mid+1,right);
//合并
merge(array,left,mid,right);
}
public static void merge(int[] array,int left,int mid,int right) {
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2= right;
int k = 0;
int[] tmpArray = new int[right - left + 1];
while(s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmpArray[k++] = array[s1++];
}else {
tmpArray[k++] = array[s2++];
}
}
while(s1 <= e1) {
tmpArray[k++] = array[s1++];
}
while(s2 <= e2){
tmpArray[k++] = array[s2++];
}
for (int i = 0; i < tmpArray.length; i++) {
array[i + left] = tmpArray[i];
}
}时间复杂度：O(n*logN)
空间复杂度：O(n)
稳定性：稳定性
三.归并排序（非递归）
思路：手动分组，利用for循环将数组分解成若干子列，在分解过程中排好序，再循环回原数组。
分解：
public static void mergeSort2(int[] array) {
int gap = 1;
while(gap < array.length) {
for (int i = 0; i < array.length; i+=2*gap) {
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if(mid >= array.length) {
mid = array.length-1;
}
if(right >= array.length) {
right = array.length-1;
}
}
gap *= 2;
}
}注意：mid，right可能会越界。
合并：因为分解是从最小子列开始，所以可以在每次循环中排序合并。
public static void mergeSort2(int[] array) {
int gap = 1;
while(gap < array.length) {
for (int i = 0; i < array.length; i+=2*gap) {
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if(mid >= array.length) {
mid = array.length-1;
}
if(right >= array.length) {
right = array.length-1;
}
merge(array,left,mid,right);
}
gap *= 2;
}
}四.计数排序（了解）
将要统计元素大小作为数组下标，通过统计要排序的元素的个数，然后按顺序打印统计数组元素遍的数组下标，完成排序。
public static void countSort(int[] array) {
int min = array[0];
int max = array[0];
for (int i = 0; i < array.length; i++) {
if(array[i] < min) {
min = array[i];
}
if(array[i] > max) {
max = array[i];
}
}
int len = max - min + 1;
int[] tmpArray = new int[len];
//制作计数数组
for (int i = 0; i < array.length; i++) {
tmpArray[array[i] - min]++;
}
//完成排序
int Index = 0;
for (int i = 0; i < len; i++) {
while(tmpArray[i] != 0) {
array[Index++] = i + min;
tmpArray[i]--;
}
}
}