排序
- 排序的穩定性
- 一、直接插入排序
- 二、希爾排序
- 三、選擇排序
- 四、冒泡排序
- 五、堆排序
- 六、快速排序
- Partition
- 挖坑法實作Partition
- Hoare法實作Partition
- 遞回分治
- 時間空間復雜度
- 優化
- 三數取中
- 非遞回分治
- 七、歸并排序
- 歸并排序（遞回）
- 非遞回的歸并排序
- 時間復雜度與空間復雜度
- 計算運行時間的小妙招
- 買七送一（基數排序）
排序的穩定性
兩個相等的資料，經過排序后，排序演算法保證其相對位置不發生變化，則稱這個排序演算法就有穩定性
判斷方法：如果再比較的程序中沒有發生跳躍式的交換（即非相鄰的交換），那么就是穩定的
一、直接插入排序
- 用 i 遍歷陣列，j = i - 1，將當前元素找到合適的位置插入，這個位置要滿足 前面元素小于它
- 將當前元素存在 temp 中，j 下標的元素與temp 比較，如果array[ j ]>temp,說明temp插入的位置 j 下標前面，將 j 下標的元素后移一位，j - -
- 再進入回圈判斷
- 當 j < 0 的時候，退出回圈，說明當前元素的位置是0下標
- 如果array[ j ] < temp , 將temp 放到 j+1 下標中，退出回圈，說明當前元素已經找到了合適的位置
- 此時 temp 前的區間有序了
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{
array[j+1] = temp;
break;
}
}
if(j < 0){
array[0] = temp;
}
}
}
如果一組資料量比較小，越趨近于有序，用直接插入排序越快
二、希爾排序
-
希爾排序是對直接插入排序的優化
-
先分組進行預排序，即對每組進行直接插入排序，每組的資料量小，排序快
-
不斷減少組數，進行預排序，進一步提高整體資料的有序性
-
直到最后為一組，進行直接插入排序
-
大大的降低了直接插入排序的時間復雜度
-
每分一次組，就進行一次直接插入排序；資料量不同，分組的方式也不同，必須保證最后一次只有一組
-
gap越大，步子越大，移動的越快，越無序
public static void shell(int[] array, int gap){
for (int i = gap; i < array.length; i++) {
int temp = array[i];
int j = i-gap;
for (; j >=0 ; j -= gap) {
if(array[j] > temp){
array[j+gap] = array[j];
}else{
array[j+gap] = temp;
break;
}
}
if(j < 0){
array[gap+j] = temp;
}
}
}
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap = gap/3+1;
// gap = gap/2;
shell(array,gap);
}
}
三、選擇排序
- 用 i 遍歷一次整個陣列
- j = i+1, j 向后遍歷，如果當前 j 下標的元素小于當前 i 下標的元素，交換這兩個元素，j 繼續向后遍歷；第一次遍歷完成后 i 下標的元素就是當前陣列最小的元素
- 當 i 遍歷完成這個陣列，排序完畢
public void selectSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
for (int j = i+1; j < array.length; j++) {
if(array[i] > array[j]){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
四、冒泡排序
- i 表示排序的次數
- 通過 j 遍歷陣列，如果 j 下標的元素 > j + 1下標的元素，交換這兩個元素，j 繼續向后遍歷，第一趟排序后最后一個元素就是最大的元素
- 再進行第二趟排序，注意 j 的結束下標的位置
public static void bullerSort(int[] array){
boolean flg = true;
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flg = false;
}
}
if(flg){
break;
}
}
}
五、堆排序
- 先將陣列變成一個大堆
- 堆頂元素與堆尾的元素互換
- 從堆頂元素向下調整，再次成為大堆，注意調整區間的范圍（較上一次-1）
- 堆頂元素和倒數第二個元素互換
- 再次向下調整
- 照此回圈，直至堆頂元素
//向下調整
//這里的end是結束區間的下標，注意不是長度len
public static void adjustDown(int[] array, int begin, int end){
int parent = begin;
int child = parent*2+1;
while(child <= end){
if(child+1 <= end && array[child+1] > array[child]){
child++;
}
if(array[parent] < array[child]){
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
}else{
break;
}
parent = child;
child = child*2+1;
}
}
//建立一個大堆
public static void creayHeap(int[] array){
int parent = (array.length-1-1)/2;
for (int i = parent; i >= 0; i--) {
adjustDown(array,i,array.length-1);
}
}
//堆排序
public static void heapSort(int[] array){
creayHeap(array);
int end = array.length-1;
while(end > 0){
int temp = array[0];
array[0] = array[end];
array[end] = temp;
end--;
adjustDown(array,0,end);
}
}
六、快速排序
- 從待排序區間里選一個數，作為基準值（pivot）
- Partition：遍歷整個區間，將比基準值小的放到基準值的左邊，將比基準值大的放到基準值的右邊
- 分治思想，對左右兩個小區間按照同樣的方式處理，知道小區間的長度為1，代表已經有序；或小區間的長度為0，代表沒有資料
Partition
挖坑法實作Partition
- 取第一個元素作為基準（pivot）
- low下標從左邊開始遍歷，high下標從右邊開始遍歷，low和high就是“坑”
- 首先low下標作為“坑”，需要比 pivot 小的元素填坑，high–，找到比pivot 小的元素，賦值給low
- 然后high下標作為“坑”，需要比pivot 大的元素填坑，low++，找到比pivot 大的元素，賦值給high
- 當low和high相遇時，此下標指向的元素就是 pivot
- 一次Patition結束，此時low/high的左邊是比pivot小的元素，low/high右邊是比pivot大的元素
- 回傳pivot的下標（low/high），作為下一次Patition的區間
public static int Partition(int[] array, int low, int high){
int pivot = array[low];
while(low < high){
//注意這兩個回圈的順序，先low后high，第一個坑沒法填，最后一個數白白喪失
//注意一定是>= / <= ，而不是> <,如果< , > 相等的也交換，死回圈
while(low < high && array[high] >= pivot){
high--;
}
array[low] = array[high];
while(low < high && array[low] <= pivot){
low++;
}
array[high] = array[low];
}
array[low] = pivot;
return low;
}
Hoare法實作Partition
- 第一個元素作為基準（pivot）
- high從右邊開始遍歷，left從左邊開始遍歷
- high找到比 pivot 小的元素，low找到比 pivot 大的元素，交換元素
- high與left相遇時，此下標指向的元素 小于pivot ，與 區間起點 的元素交換
- 回傳pivot的下標（low/high），作為下一次Patition的區間
public static void Swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static int Hoare(int[] array, int low, int high){
int start = low;
int pivot = array[low];
while(low < high){
//注意順序，先后再前，讓high去找low，兩者相遇的地方是比temp小的數
//同樣的必須是>= <=，如果是>,< 會死回圈的
while(low < high && array[high] >= pivot){
high--;
}
while(low < high && array[low] <= pivot){
low++;
}
Swap(array,low,high);
}
Swap(array,low,start);
return low;
}
遞回分治
- 通過遞回的方式對左右兩個小區間再進行快速排序，直到區間長度為1時，遞回結束
public static void quickSort(int[] array, int start, int end){
if(start >= end){
return;
}
int pivot = Partition(array,start,end);
quickSort(array,start,pivot-1);
quickSort(array,pivot+1,end);
}
public static void quickSort(int[] array){
quickSort(array,0,array.length-1);
}
時間空間復雜度
穩定性：不穩定
最壞情況時，可能會出現堆疊溢位的情況
所以可以通過基準值的選擇進行優化
優化
- 基準值的選擇
- 選擇邊上（low或者high）
- 隨機選擇，可以將隨機下標的值與low下標的值互換
- 三數取中，要求 array[mid] <= array[low] <= array[high]
- 待排序區間小于一個閾值時，使用直接插入排序
三數取中
還是array[low] 作基準(pivot)
三數取中
array[mid] <= array[low] <= array[high]
可以確定其中最大/最小數的位置，在比較其余兩個數
//元素交換
public static void Swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//array[mid] <= array[low] <= array[high]
public static void ThreeMiddle(int[] array,int low, int high){
int mid = (low+high)/2;
if(array[low] < array[mid]){
Swap(array,low,mid);
}
if(array[high] < array[low]){
Swap(array,low,high);
}
if(array[low] < array[mid]){
Swap(array,low,mid);
}
//先確定mid的位置
if(array[mid] > array[start]){
swap(array,start,mid);
}
if(array[mid] > array[end]){
swap(array,mid,end);
}
//確定完成
if(array[start] > array[end]){
swap(array,start,end);
}
//先確定high的位置
if(array[mid] > array[high]){
Swap(array,mid,high);
}
if(array[low] > array[high]){
Swap(array,low,high);
}
//確定完成
if(array[mid] > array[low]){
Swap(array,mid,low);
}
}
非遞回分治
- 呼叫Partition后，找到pivot
- 把當前pivot的左區間和右區間的邊界下標放到堆疊中，當這個區間至少有兩個元素的時候，才入堆疊；若只有一個元素，說明有序了，不再入堆疊
- 判斷堆疊是否為空，如果不為空的話，彈出堆疊頂的兩個元素，放的順序決定第一個元素給low還是給high
- 再進行Partition
public static void quickSort2(int[] array){
if(array.length == 0){
return;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(array.length-1);
while(!stack.isEmpty()){
int high = stack.pop();
int low = stack.pop();
int pivot = Partition(array,low,high);
if(pivot > low+1) {
stack.push(low);
stack.push(pivot - 1);
}
if(pivot < high-1) {
stack.push(pivot + 1);
stack.push(high);
}
}
}
七、歸并排序
先將已有的序列分解成較短的子序列，使每個子序列有序，再將已經有序的子序列合并，得到完全有序的序列，即分解與合并
歸并排序（遞回）
- 將陣列通過遞回分解，直到low=high時（即只有一個元素的時候），遞回結束
- 將兩個有序陣列 合并成 一個有序陣列
public static void merge(int[] array, int low, int mid, int high){
int[] temp = new int[high-low+1];
int k = 0;
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
while(s1 <= e1 && s2 <= e2){
while(s1 <= e1 && array[s1] <= array[s2]){
temp[k++] = array[s1++];
}
while(s2 <= e2 && array[s2] <= array[s1]){
temp[k++] = array[s2++];
}
}
while(s1 <= e1){
temp[k++] = array[s1++];
}
while(s2 <= e2){
temp[k++] = array[s2++];
}
for (int i = 0; i < temp.length; i++) {
array[i+low] = temp[i];
}
}
public static void mergeSort(int[] array, int low, int high){
if(low == high){
return;
}
int mid = (low+high)/2;
mergeSort(array,low,mid);
mergeSort(array,mid+1,high);
merge(array, low, mid, high);
}
public static void mergeSort(int[] array){
mergeSort(array,0,array.length-1);
}
非遞回的歸并排序
- 通過gap控制需要合并的兩個序列的長度，1–>2–>4–>8…
- 在gap的一次回圈中，s1、e1、s2、e2遍歷所有的序列，合并兩個有序的序列
- 可能序列正好匹配 可能只剩下一段序列（沒有與之合并的第二段序列）；如果剩下無法合并的序列，不做改變
public static void merge(int[] array, int gap){
int[] temp = new int[array.length];
int k = 0;
int s1 = 0;
int e1 = s1+gap-1;
int s2 = e1+1;
int e2 = s2+gap-1 > array.length-1 ? array.length-1 : s2+gap-1;
//有兩段
while(s2 < array.length) {
while (s1 <= e1 && s2 <= e2) {
while (s1 <= e1 && array[s1] <= array[s2]) {
temp[k++] = array[s1++];
}
while (s2 <= e2 && array[s2] <= array[s1]) {
temp[k++] = array[s2++];
}
}
while(s1 <= e1) {
temp[k++] = array[s1++];
}
while(s2 <= e2){
temp[k++] = array[s2++];
}
s1 = e2+1;
e1 = s1+gap-1;
s2 = e1+1;
e2 = s2+gap-1 > array.length-1 ? array.length-1 : s2+gap-1;
}
//只有一段了
while(s1 < array.length && s1 <= e1){
temp[k++] = array[s1++];
}
for (int i = 0; i < temp.length; i++) {
array[i] = temp[i];
}
}
public static void mergeSort2(int[] array){
for (int gap = 1; gap < array.length; gap*=2) {
merge(array,gap);
}
}
時間復雜度與空間復雜度
計算運行時間的小妙招
long begin = System.currentTimeMillis();
insertSort(array);
long end = System.currentTimeMillis();
System.out.println(end - begin);
買七送一（基數排序）
基數排序又叫“桶子排序”
- 先給10個桶子 標號0~10
- 將所有元素按個位數放入對應的桶中
- 依次取出完成第一次排序
- 再將所有元素按十位數放入對應的桶中
- 依次取出完成第二次排序
- 注意從桶中取出元素的時候要 桶底元素先出，桶頂元素后出
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/305673.html
標籤：java