快速排序
基本算法：
归并排序讲数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
快速排序通过一个切分元素将数组分为两个子数组，左子树组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
图解快速排序
public class QuickSort<T extends Comparable<T> extends Sort<T>{
@Override
public void sort(T[] nums){
shuffle(nums);
sort(nums,0,nums.length - 1);
}
private void sort(T[] nums,int 1,int h){
if(h <=1)
return;
int j = partition(nums,1,h);
sort(nums,1,j - 1);
sort(nums,j + 1,h);
}
private void shuffle(T[] nums){
List<Comparable> list = Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
}
选择排序
基本算法：
选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要~N²/2次比较和~N次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
图解选择排序
public class Selection<T extends Comparable<T>> extends Sort<T>{
@Override
public void sort(T[] nums){
int N = nums.length;
for(int i = 0;i < N - 1;i++){
int min = i;
for (int j = i + 1; j < N;j++){
if(less(nums[j],nums[min])){
min = j;
}
}
swap(nums,i,min);
}
}
}
冒泡排序
基本算法：
从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让末排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出，以下演示了在一轮循环中，将最大的元素5上浮到最右侧。
图解冒泡排序
public class Bubble<T extends Comparable<T>> extends Sort<T>{
@Override
public void sort(T[] nums){
int N = nums.length;
boolean hasSorted = false;
for(int i = N - 1;i > 0 && !hasSorted; i --){
hasSorted = true;
for(int j = 0; j < i; j++){
if(less(nums[j + 1],nums[j])){
hasSorted = false;
swap(nums,j,j + 1);
}
}
}
}
}
网友评论