遞歸與排序演算法
- 2021 年 2 月 5 日
- 筆記
遞歸
自己調用自己調用方法時傳入不同的參數，使程式碼更加簡潔
遞歸的調用機制:
-
每次調用方法時，會創建一個新的棧空間(獨立的)，以及私有的局部變數(獨立不會相互影響)
-
當方法使用的是引用變數時,每個開闢的棧空間共用這一引用變數
-
遞歸必須無限向遞歸結束條件靠近，否則會出現StackOverFlowError棧溢出錯誤
-
遞歸可以解決的問題
-
問題描述是遞歸的(階乘，斐波那契數列)
-
問題的解法是遞歸的(漢諾塔問題)
-
數據結構遞歸的(樹的遍歷，圖的深度優先搜索)
八大排序演算法
分類：
-
內部排序：使用記憶體進行排序
-
外部排序：使用外部存儲排序
內部排序分類：
-
插入排序
-
直接插入排序
-
希爾排序
-
-
交換排序
-
冒泡排序
-
快速排序
-
-
選擇排序
-
簡單選擇排序
-
堆排序
-
-
歸併排序
-
基數排序
冒泡排序-時間複雜度O(n2)
演算法規則:
遍曆數組如果遇到逆序則進行數據交換
public class BubbleSort
{
public static void main(String[] args)
{
int arr[]= {1,2,3,5,4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr【】 待排序數組
public static void bubbleSort(int arr[]) {
boolean flag=false;//作為標記數組數據是否發生交換
int temp;//作為交換數據的臨時變數
//外層控制循環次數
for(int i=0;i<arr.length-1;i++) {
System.out.println("第"+i+"次排序");
//內層控制數據排序
for(int j=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
//前面大於後面
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=true;
}
}
if(!flag) {
break;
}else {
flag=false;
}
}
}
}
冒泡演算法優化：
定義一個標記變數flag，判斷flag的值是否發生改變，若沒改變則數組已經有序則可以提前跳出循環
選擇排序-時間複雜度O(2)
演算法規則：遍曆數組，將每次遍歷得到的最小值，與起始位置數據做交換
arr[0]-arr[n-1],找出最小值與arr[0]交換
arr[1]-arr[n-1],找出最小值與arr[1]交換,以此類推
public class SelectSort
{
public static void main(String[] args)
{
int arr[]= {101,34,119,1,-1,90,123};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序數組
public static void selectSort(int arr[]) {
int min;//最小值記錄
int minIndex;//最小值下標記錄
//外層控制循環次數
for(int i=0;i<arr.length-1;i++) {
min=arr[i];
minIndex=i;
//內層從i開始遍曆數組進行排序
for(int j=i+1;j<arr.length-1;j++) {
//存在小於臨時最小值則替換最小值並記錄下標
if(arr[j]<min){
min=arr[j];
minIndex=j;
}
}
//數據交換
if(minIndex!=i) {
arr[minIndex]=arr[i];
arr[i]=min;
}
}
}
}
選擇排序優化:
判斷最小值位置是否發生改變，若沒有則不需要進行數據交換
插入排序-時間複雜度O(n2)
演算法規則:
假定兩個數組，一個是原數組(大小為n-1)，一個是有序數組(大小為1，存放原數組的第一個元素)。將原數組中的數據依次取出放入有序數組中的適當位置，將原數組數據取出完畢後，則排序完畢
public class InsertSort
{
public static void main(String[] args)
{
int arr[]= {101,34,119,1,-1,89};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序數組
public static void insertSort(int arr[]) {
int value,insertIndex;
//假定第一個為有序，從下一位開始插入
for(int i=1;i<arr.length;i++) {
value=arr[i];
insertIndex=i-1;
//循環條件：插入位置沒到數組第一位以及插入位置數據大於待插入數據
while(insertIndex>=0 && arr[insertIndex]>value) {
arr[insertIndex+1]=arr[insertIndex];//插入位置數據後移
insertIndex--;//插入位置前移
}
//找到插入位置
if(insertIndex!=i) {
arr[++insertIndex]=value;
}
}
}
}
演算法優化：
判斷插入位置是否發生改變決定是否進行數據插入
希爾排序-時間複雜度O(nlog2n)
演算法規則:
將數組按照一定增量分組，對每組進行插入排序，繼續減少增量，插入排序，當增量減少為1時，則進行最後的插入排序，結果即為有序的
public class ShellSort
{
public static void main(String[] args)
{
int arr[]= {8,9,1,7,2,3,5,4,6,0,11,0,12,3,7};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序數組
public static void shellSort(int arr[]) {
int value,index;
//定義增量(組數),每次除以2
for(int gap=arr.length/2;gap>0;gap/=2) {
//組內進行插入排序
for(int i=gap;i<arr.length;i++) {
value=arr[i];
//循環條件：當插入位置(i-gap)>=0並且插入位置的值大於待插入數據
while(i-gap>=0&&arr[i-gap]>value) {
arr[i]=arr[i-gap];
i-=gap;
}
//找到插入位置
arr[i]=value;
}
}
}
}
快速排序-時間複雜度O(nlog2n)
演算法規則：
將數組按照大於小於中間值分類，向左向右遞歸得到有序數組
public class QuickSort
{
public static void main(String[] args)
{
int arr[]= {-9,78,0,23,-567,70};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序數組，left數組左邊索引，right數組右邊索引
public static void quickSort(int arr[],int left,int right) {
int l=left;//當前數組左索引
int r=right;//當前數組右索引
int pivot=arr[(left+right)/2];//中間值用於判斷數據
int temp;
while(l<r) {
//找左邊大於等於中間值的數據
while(arr[l]<pivot) {
l++;
}
//找右邊大於等於中間值的數據
while(arr[r]>pivot) {
r--;
}
//判斷是否循環結束
if(l>=r) {
break;
}
//左右數據交換
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
//防止存在相同值時死循環
if(arr[l]==pivot) {
r--;
}
if(arr[r]==