快速排序
基本算法：
歸并排序講數(shù)組分為兩個子數(shù)組分別排序，并將有序的子數(shù)組歸并使得整個數(shù)組排序；
快速排序通過一個切分元素將數(shù)組分為兩個子數(shù)組，左子樹組小于等于切分元素，右子數(shù)組大于等于切分元素，將這兩個子數(shù)組排序也就將整個數(shù)組排序了。
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);
}
}
選擇排序
基本算法：
選擇出數(shù)組中的最小元素，將它與數(shù)組的第一個元素交換位置。再從剩下的元素中選擇出最小的元素，將它與數(shù)組的第二個元素交換位置。不斷進(jìn)行這樣的操作，直到將整個數(shù)組排序。
選擇排序需要~N2/2次比較和~N次交換，它的運行時間與輸入無關(guān)，這個特點使得它對一個已經(jīng)排序的數(shù)組也需要這么多的比較和交換操作。
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);
}
}
}
冒泡排序
基本算法：
從左到右不斷交換相鄰逆序的元素，在一輪的循環(huán)之后，可以讓末排序的最大元素上浮到右側(cè)。在一輪循環(huán)中，如果沒有發(fā)生交換，就說明數(shù)組已經(jīng)是有序的，此時可以直接退出，以下演示了在一輪循環(huán)中，將最大的元素5上浮到最右側(cè)。
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);
}
}
}
}
}
