一.快速排序补充
快速排序的分治部分还有其他方法,如挖坑法,快慢指针法。
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]--;
}
}
}
标签:right,int,mid,---,length,排序,array,数据结构,left
From: https://blog.csdn.net/a15670247200/article/details/143532894