自己总结的一个快速排序算法及思想:
package main.com.xia.test3;
import java.util.Arrays;
public class Answer1{
/* 采用分治思想将数组进行排序,通过获取基数的中间位置将数组分成左右两个数组。分别再对两个数组进行调用分治思想排序算法。
我们假定从数组左边选择一个数作为基数,寻找其在数组的应该位置,该位置在数组中左边比基数小,右边比基数大。
为了获取基数的中间位置,我们设定两个哨兵,数组最左边的一个哨兵,数组右边一个哨兵。然后将哨兵与基数比较大小。算法寻找基数的位置的算法如下:
从右边寻找一个比基数小的值,然后与左哨兵更换值,。然后从右面哨兵起步,寻找一个比基数大的与右面的哨兵进行交换值。结束后,判断start是否比end小,如果是,继续本循环;
不是,退出循环。并且将基数的值赋给start。返回start的数值*/
public static void main(String[] args){
int[] test2 = new int[]{10,1,2,9,6,3,7,8,4,5};
quickSort(0,test2.length - 1,test2);
System.out.println(Arrays.toString(test2));
}
public static void quickSort(int start,int end,int[] array){
if(start < end){
int partion = getPosition(start,end,array);
quickSort(start,partion,array);
quickSort(partion + 1,end,array);
}
}
public static int getPosition(int start,int end,int[] array){
int tmp = array[start];
while(start < end){
//从数组右面开始寻找一个比tmp小的值。
while(start < end && array[end] >= tmp){
end--;
}
array[start] = array[end];
//从数组右面开始寻找一个比tmp小的值。
while(start <end && array[start] <= tmp){
start++;
}
array[end] = array[start];
}
array[start] = tmp;
return start;
}
}
大家仔细观察getPosition()的内容是不是很面熟。不错和普通的交换算法很相似
public static int getPosition(int start,int end,int[] array){
int tmp = array[start];
while(start < end){
//从数组右面开始寻找一个比tmp小的值。
while(start < end && array[end] >= tmp){
end--;
}
array[start] = array[end];
//从数组右面开始寻找一个比tmp小的值。
while(start <end && array[start] <= tmp){
start++;
}
array[end] = array[start];
}
array[start] = tmp;
return start;
}
如果把函数中的while循环注释掉,方法就变成了。
public static int getPosition(int start,int end,int[] array){
int tmp = array[start];
// while(start < end){
//从数组右面开始寻找一个比tmp小的值。
// while(start < end && array[end] >= tmp){
// end--;
// }
array[start] = array[end];
//从数组右面开始寻找一个比tmp小的值。
// while(start <end && array[start] <= tmp){
// start++;
// }
array[end] = array[start];
// }
array[start] = tmp;
return start;
}
普通冒泡算法:截图