排序
1.直接插入排序
當前有一組待排序序列，大部分是有序的，請問哪種排序方式更適合？
答 ： 直接插入排序
時間復雜度：
最壞情況（當資料無序） O(n^2)
最好情況(當資料有序) O(n)
空間復雜度：O(1)
穩定性：穩定
代碼實作：
public class DirectInsertSort {
/**
* 時間復雜度：最壞情況（當資料無序） O(n^2)
* 最好情況(當資料有序) O(n)
*
* 所以---》對于直接插入排序：越有序越快
* 空間復雜度：O(1)
* 穩定性：穩定
* @param array
*/
public static void insertSort(int[] array) {
for(int i = 1;i < array.length;i++){
int temp = array[i];
int j = i-1;
for(;j>=0;j--){
if(array[j] > temp){//如果這里是 >= 號就不穩定了
array[j+1] = array[j];
} else {
break;
}
}
//代碼走到這里可能是回圈退出的，j<0了
array[j+1] = temp;
}
}
public static void main(String[] args) {
int[] array = {10,3,2,7,19,78,65,127};
System.out.println(Arrays.toString(array));
insertSort(array);
System.out.println(Arrays.toString(array));
}
}
2.希爾排序
希爾排序是對直接插入排序的優化
希爾排序中的增量序列中的值沒有除1之外的公因子，并且最后一個增量值必須等于1
時間復雜度：最壞情況: O(n^2)
空間復雜度：O(1)
穩定性：不穩定
public class XiErSort {
public static void shell(int[] array ,int gap) {
for(int i = 0;i<array.length;i++){
int temp = array[i];
int j = i-gap;
for(;j>=0;j = j-gap){
if(array[j] > temp){
array[j+gap] =array[j];
}else {
break;
}
}
array[j+gap] = temp;
}
}
public static void shellSort(int[] array) {
int[] drr = {5,3,1};//增量陣列
for (int i = 0; i < drr.length; i++) {
shell(array,drr[i]);
}
}
public static void main(String[] args) {
int[] array = {10,7,5,6,90,32};
shellSort(array);
System.out.println(Arrays.toString(array));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/256019.html
標籤：java
下一篇：單片機新手跪求大佬指點