屬于內部排序 （4）歸并排序
1. 抽出一張牌，和當前元素之前的元素逐個比較，如果比當前元素小，該元素就后移，直到找到插入位置 初始時視第一個元素是有序的 ，之后通過排序逐漸增大有序序列的長度while 循環 （更規范 ）public static void insert_sort ( int [ ] arr) { for ( int i = 1 ; i < arr. length; i++ ) { int insertvalue = arr[ i] ; int j = i - 1 ; while ( j >= 0 && insertvalue < arr[ j] ) { arr[ j + 1 ] = arr[ j] ; j-- ; } arr[ j + 1 ] = insertvalue; }
}
for 循環 public static void insert_sort_1 ( int [ ] arr) { for ( int i = 1 ; i < arr. length; i++ ) { int insertvalue = arr[ i] ; int j = i - 1 ; for ( ; j >= 0 ; j-- ) { if ( insertvalue < arr[ j] ) { arr[ j + 1 ] = arr[ j] ; } else { break ; } } arr[ j + 1 ] = insertvalue; }
}
public static void binary_insert_sort ( int [ ] arr) { for ( int i = 1 ; i < arr. length; i++ ) { int insertvalue = arr[ i] ; int left = 0 ; int right = i - 1 ; while ( left <= right) { int mid = left + ( ( right - left) / 2 ) ; if ( arr[ mid] < insertvalue) { left = mid + 1 ; } else { right = mid - 1 ; } } for ( int j = i - 1 ; j >= right + 1 ; j-- ) { arr[ j + 1 ] = arr[ j] ; } arr[ right + 1 ] = insertvalue; }
}
最后 gap 的值必須是一 ，每一輪排序對 gap 產生的序列進行排序“ 1 ” 的位置全部替換 成 “ gap ”
public static void shell_sort ( int [ ] arr) { int gap = arr. length / 2 ; while ( gap >= 1 ) { shell ( arr, gap) ; gap /= 2 ; }
}
public static void shell ( int [ ] arr, int gap) { for ( int i = gap; i < arr. length; i++ ) { int insertvalue = arr[ i] ; int j = i - gap; while ( j >= 0 && insertvalue < arr[ j] ) { arr[ j + gap] = arr[ j] ; j -= gap; } arr[ j + gap] = insertvalue; }
}
public static void bubble_sort ( int [ ] arr) { for ( int i = 0 ; i < arr. length - 1 ; i++ ) { for ( int j = 0 ; j < arr. length - 1 - i; j++ ) { if ( arr[ j] > arr[ j + 1 ] ) { int temp = arr[ j] ; arr[ j] = arr[ j + 1 ] ; arr[ j + 1 ] = temp; } } }
}
改進版本 減少比較次數
public static void bubble_sort_improve ( int [ ] arr) { for ( int i = 0 ; i < arr. length - 1 ; i++ ) { int flag = 0 ; for ( int j = 0 ; j < arr. length - 1 - i; j++ ) { if ( arr[ j] > arr[ j + 1 ] ) { flag = 1 ; int temp = arr[ j] ; arr[ j] = arr[ j + 1 ] ; arr[ j + 1 ] = temp; } } if ( flag == 0 ) { break ; } }
}
把第一個元素當作樞紐，然后通過兩個指針 left 和 right right ： 在后面 找比樞紐小 的元素搬到 樞紐的前面 public static int partition ( int [ ] arr, int left, int right) { int pivot = arr[ left] ; while ( left < right) { while ( arr[ right] >= pivot && left < right) { right-- ; } arr[ left] = arr[ right] ; while ( arr[ left] <= pivot && left < right) { left++ ; } arr[ right] = arr[ left] ; } arr[ left] = pivot; return left;
} public static void quicksort ( int [ ] arr, int left, int right) { if ( left < right) { int pivot = partition ( arr, left, right) ; quicksort ( arr, left, pivot - 1 ) ; quicksort ( arr, pivot + 1 , right) ; }
}
最小的數 ，避免重復的覆蓋，減少比較次數區別冒泡排序 的優化 冒泡排序 中是比較相鄰兩個元素之間 是否有序，如果有序就不交換位置 public static void select_sort ( int [ ] arr) { for ( int i = 0 ; i < arr. length; i++ ) { for ( int j = i + 1 ; j < arr. length; j++ ) { if ( arr[ j] < arr[ i] ) { int temp = arr[ j] ; arr[ j] = arr[ i] ; arr[ i] = temp; } } }
}
改進版本 public static void select_sort_improve ( int [ ] arr) { for ( int i = 0 ; i < arr. length; i++ ) { int min_index = i; for ( int j = i + 1 ; j < arr. length; j++ ) { if ( arr[ j] < arr[ min_index] ) { min_index = j; } } if ( min_index != i) { int temp = arr[ i] ; arr[ i] = arr[ min_index] ; arr[ min_index] = temp; } }
}
堆的性質是符合完全二叉樹的，在結構上是遞歸定義的樹結構 非葉子節點節點 的物理位置為 “ i ” 數組大小為 n （1）最后一個元素（葉子節點 ）在樹中的標號對應的數組下標是n / 2 從左到右，從上到下依次標號 對應數組下標 ） 0 / \1 2 / \ / \3 4 5 6
大根堆 ：對于完全二叉樹中的任意一個節點，其值都大于或等于其子樹 中所有節點的值。這意味著大根堆的根節點是堆中最大的元素 10 / \8 6 / \ / \5 3 2
1 / \3 4 / \ / \6 8 9
堆排序思想 從后面的=第一個非葉子節點 （下標：n / 2 - 1 ）開始，依次遞歸的往上調整，使得整棵樹形成大根堆的結構 交換思想：交換的過程就是排序的過程，把最大的和最小的交換，即把最大的放入有序區，數組從后往前依次遞減排序 理解：在調整過程中，指向的最大根節點會發生變化，對根節點調整即可實現對左右子樹的調整 ） n - 1 的說明 （1）進行n - 1 趟排序 堆的大小的變化 ，每一輪排序一個元素（交換的過程），堆中需要調整的元素總數減小一
public static void heapify ( int [ ] arr, int n, int i) { int max_index = i; int left = 2 * i + 1 ; int right = 2 * i + 2 ; if ( left < n && arr[ left] > arr[ max_index] ) { max_index = left; } if ( right < n && arr[ right] > arr[ max_index] ) { max_index = right; } if ( max_index != i) { int temp = arr[ i] ; arr[ i] = arr[ max_index] ; arr[ max_index] = temp; heapify ( arr, n, max_index) ; }
}
public static void heap_sort ( int [ ] arr) { int n = arr. length; for ( int i = n / 2 - 1 ; i >= 0 ; i-- ) { heapify ( arr, n, i) ; } for ( int i = n - 1 ; i > 0 ; i-- ) { int temp = arr[ 0 ] ; arr[ 0 ] = arr[ i] ; arr[ i] = temp; heapify ( arr, i, 0 ) ; }
}
遞歸思想
Step-Back 回答回退策略擴大檢索范圍)
