转：微信公众号：程序员小灰
快排算法 是按分治算法的思路进行排序的。
选定参照元素后，每次比较都按分治算法将小的移到，
最坏情况时间复杂度：n(n*n)
平均时间复杂度：n(nlog2n)
最快情况时间复杂度：n(n-1)
实现的2种方法：
1.挖坑法
譬如：5（坑），1，7，6，2，8，3，4，9
以5为基准元素：
提示：
right<基准元素才会位置不动去填坑，
left>基准元素才会位置不动去填坑
最左边5为left,最右边9为right
先从右边right开始比较，right=9 > 5, 不需要填坑，
继续左移动，right = 4 <5,则需要用9去填5这个坑，right移动之后到left移动(此时right还是=4，原地不动，同时right=4=坑)，此时列表应为：：
4，1，7，6，2，8，3，4（坑），9
原坑5被填，故left自动右移一位，
left=1 < 5, 继续右移一位，
left = 7 > 5, 用7去填坑4，
left停留在7, 7同时也变成了坑，
此时列表为：
4，1，7（left,坑），6，2，8，3，7(right)，9
right左移一位，right=3 < 5,
用3 去填坑7，同时3也变成了坑，
列表：
4，1，3（left），6，2，8，3（right,坑），7，9
left右移一位，left=6,
6>5,用5去填坑3,
列表：
4，1，3，6（left,坑），2，8，6（right），7，9
right左移一位，right=8,8>5,
继续左移一位，right = 2, 2<5,
用2填坑6,
列表：
4，1，3，2（left），2（right，坑），8，6，7，9
left右移一位，
left=2=right
列表：
4，1，3，2，2（left, right，坑），8，6，7，9
由于left=2=right,
所以将一开始的基准元素5替换掉坑
列表：
4，1，3，2，5，8，6，7，9
此时5左边都是小于5，右边都是大于5
2.交换地址发法：
4，8，2，6，1，3，9，5，7
基准元素4，列表
4（left），8，2，6，1，3，9，5，7（right）
right=7 > 4 ,左移一位，
right=5>4 ,左移一位，
right=9>4, 左移一位，
right=3 <4,不动，记住位置
列表：
4（left），8，2，6，1，3（right），9，5，7
left=4=4,left右移一位，
left=8>4,left不动，记住位置，
然后left和right呼唤位置
列表：
4，3（left），2，6，1，8（right），9，5，7
right左移一位，right=1<4,不动，记住位置
left右移一位，left=2<4,
left右移一位，left=6>4, 不动，记住位置
left和right位置呼唤，
列表：
4，3，2，1（left），6（right），8，9，5，7
right左移一位，right=left=1，
列表：
4，3，2，1（left，right），6，8，9，5，7
第一轮呼唤位置完毕
拓展：
是否只能用递归实现快排呢？
不是，还可以用stack的方法
定义一个一个map类型的集合栈
map有startindex和endindex
然后把map压进栈
再一个循环，栈空则跳出
不停pop出map，map里的startindex和endindex可以定义新的pivot基准元素
if判断（左边分区要小于pivot基准元素）
是则map出一个新的集合，然后push进去stack
右边也类似！
代码:
package quickSort;
import java.util.Arrays;
public class quickSort {
//第一轮分区交换数据
private static int partition(int[] arr, int startIndex, int endIndex){
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while(left != right){
//arr[right]>=pivot基准元素时，左移一位
while(left < right && arr[right] >= pivot){
right--;
}
//arr[left]<=pivot基准元素时，右移一位
while(left < right && arr[left] <= pivot){
left++;
}
//交换位置
if(left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//跳出循环时，left==right,替换pivot和指针重合元素
int temp = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = temp;
return left;
}
//对数组进行多轮分区，迭代
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);
}
public static void main(String[] args) {
int[] arr = new int[]{3,8,2,4,1,3,3,5,7,8,9,4,2,845,4,14,8,6,814,};
quicksort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
网友评论