1.歸并排序
package sort;
import java.util.Arrays;
public class MergeSort {
/**
* 歸并排序 簡介：將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)有序表，即把待排序的序列分成若干個(gè)子序列，每個(gè)序列是有序的。
* 然后再把有序的子序列合并成整體有序的序列。 時(shí)間復(fù)雜度為o(nlogn) 穩(wěn)定排序方式
*
* @param nums 待排序數(shù)組
* @return 輸出有數(shù)數(shù)組
*/
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左邊
sort(nums, low, mid);
// 右邊
sort(nums, mid + 1, high);
// 左右歸并
merge(nums, low, mid, high);
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指針
int j = mid + 1;// 右指針
int k = 0;
// 把較小的數(shù)先移到新數(shù)組中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右邊邊剩余的數(shù)移入數(shù)組
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
// 歸并排序的實(shí)現(xiàn)
public static void main(String[] args) {
int[] nums = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
MergeSort.sort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
}
2.冒泡排序
package sort;
import java.util.Arrays;
//簡單冒泡排序
//冒泡排序重復(fù)地走過要排序的數(shù)列，一次比較兩個(gè)元素，若順序錯(cuò)誤就把他們交換，直到?jīng)]有需要交換
public class BubbleSort1 {
//比較相鄰的元素，若第一個(gè)比第二個(gè)大，就交換，對(duì)每一對(duì)相鄰元素做同樣工作，從開始第一對(duì)到結(jié)尾最后一對(duì)。
//針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)，持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
/*public static? void bubble(int[] nums){int temp;int size = nums.length;for(int i=0;inums[j]){
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
}*///嚴(yán)格上說這段代碼不是標(biāo)準(zhǔn)的冒泡排序，因?yàn)樗粷M足“兩兩比較”，應(yīng)該是最簡單的交換排序，效率非常低
/*public static void bubble(int[] nums){int temp;int size = nums.length;for(int i=0;ii;j--){
if(nums[j-1]>nums[j]){
temp = nums[j-1];
nums[j-1] = nums[j];
nums[j] = temp;
}
}
}
}*///這樣的冒泡排序還可以優(yōu)化，如果待排序的序列是{2，1，3，4，5，6，7，8，9}，第一和第二的關(guān)鍵字交換后就沒必要再交換了。
public static void bubble(int[] nums){int temp;int size = nums.length;int flag = 1;for(int i=0;ii;j--){
if(nums[j-1]>nums[j]){
temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
flag = 1;
}
}
}
}//對(duì)于{2，1，3，4，5，6，7，8，9}，當(dāng)i=2時(shí)已經(jīng)對(duì)9和8，8和7..做了比較，沒有交換的數(shù)據(jù)，說明序列已有序，不需要增加循環(huán)，可以增加一個(gè)標(biāo)記變量flag實(shí)現(xiàn)改進(jìn)
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums ={7,6,4,9,5,2,0,1,3,8};
bubble(nums);
System.out.println(Arrays.toString(nums));
}
}
