文章目錄

• 前言
• 一、排序
• • 1.1 選擇排序
  • 1.2 冒泡排序
  • 1.3 插入排序
  • 1.4 歸并排序
  • 1.5 快速排序
• 二、查找
• • 2.1 二分查找（有序數組找某個數是否存在）
• 三、尋找最大數字
• 四、兩數之和

---

前言

目前是算法橫行的時代，邏輯很重要，特出此文章做一個總結會持續更新

---

一、排序

swap異或算法用的前提是交換的數組的元素a和b分別在不同的內存里。如果在數組中想進行交換，一定要保證i和j不能相等。

1.1 選擇排序

將第循環里的第一個元素和后面的比，誰小把誰放到前面，時間復雜度為n的平方

class SelectionSort(int[] arr){public void selectionSort(int[] arr){//排除雜條件if(arr == null || arr.length < 2){return;}for (int i = 0; i < arr.length; i++){//外層循環的每一個i先設置為此循環的最小值的索引，給到內層循環進行比較minIndex = i;for (int j = i+1; j<arr.length;j++){minIndex = arr[j] < arr[minIndex] ? j : minIndex;}//每次一個大循環找到一個該輪最小值放到第一個swap(arr,i,minIndex)}}public void swap(int[] arr;int i;int minIndex){int tmp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = tmp;} }

1.2 冒泡排序

選擇排序是將最小的放到第一位，而冒泡排序是將最大的放到最后一位，并且每次都是相鄰兩個在比。

class Solution {public int[] sortArray(int[] nums) { bubbleSort(nums); return nums;}public void bubbleSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i = 0;i<arr.length;i++){for(int j=0;j<arr.length-1-i;j++){if(arr[j]>arr[j+1]){swap(arr,j,j+1);}}}}public void swap(int[] arr,int i,int j){//異或還可以理解為無進位相加，下面方法的使用前提是arr[i]指向的內存和arr[j]指向的內存是兩塊不同的內存，因為同樣的內存異或會成為0int tmp = arr[i] ;arr[i] = arr[j];arr[j] = tmp;}}

1.3 插入排序

按照算法可能情況的最差估計時間復雜度為n的平方，每次循環都保證0-n的地方是有序排序的，而且每次都是先跟前一位比，不行了才會進行互換，否則不互換，這樣他最好的實現狀況是時間復雜度為n。

class InsertionSort(){public insertSort(int[] arr){//排除雜條件if(arr == null || arr.length < 2){return;}//i從1開始是因為0-0上已經實現了排序for (int i = 1; i < arr.length; i++){//0到i做到有序,此時已經做到了0~i-1上的數有序，所以現在比較i-1（j）和第i位置的數的大小，換到不比左邊位置的數小了就停止for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){swap(arr, j, j + 1);}}}public void swap(int[] arr,int i,int j){//異或還可以理解為無進位相加，下面方法的使用前提是arr[i]指向的內存和arr[j]指向的內存是兩塊不同的內存，因為同樣的內存異或會成為0arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];} }

1.4 歸并排序

左邊排好序右邊也排好序,復雜度為N*logN

public class MergeSort{public static void process(int[] arr, int L,int R){if(L==R){return;}int mid = L+((R-L)>>1);//先兩邊有序，后歸并mergeprocess(arr,L,mid);process(arr,mid,R);merge(arr,L,mid,R);}public static void merge(int[] arr,int L,int M,int R){//新設置一個數組放比較值int[] help = new int[R-L+1];int i = 0;int p1 = L;int p2 = M + 1;// 哪個小放哪個，并移動相應的指針while (p1 <= M && p2 <= R){help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]}//下面兩個循環只會走一個while (p1<=M){help[i++] = arr[p1++];}while (p2<=R){help[i++] = arr[p2++];}for(i = 0,i < help.length;i++){//拷貝回原來數組arr[L+i] = help[i]}} }

1.5 快速排序

class Solution {public void swap(int[] nums,int L,int R){int tmp = nums[L];nums[L] = nums[R];nums[R] = tmp;}public int[] sortArray(int[] nums) {int L = 0,R = nums.length-1;quickSort(nums,L,R);return nums;}public void quickSort(int[] nums,int L,int R){if(L<R){//遞歸終止條件swap(nums,L+(int)(Math.random()*(R-L+1)),R);//找隨機一個數字和最后一個元素互換，記住加一int[] middleIndex = partiton(nums,L,R);//進行分區，返回的是等于區的左索引坐標和右索引indexquickSort(nums,L,middleIndex[0]-1);//減一是因為小于區的最右邊界處是等于區最左邊界減一quickSort(nums,middleIndex[1]+1,R);//加一是因為大于區最左邊界是等于區最右邊界加一}}public int[] partiton(int[] nums,int L,int R){//L相當于此時的第三個指針int less = L-1;//減一是因為小于區的起始索引還沒有比較，所以先將小于區的指針指向第一個索引的前面一個，不能改成L+1，這樣就默認第一個數字確實比被比較的數字小了，萬一沒有一個就會出錯int more = R;//這里R不減一是因為最后一個是被比較數字，所以開始的大于區的指針是在他前面的while(L<more){if(nums[L]<nums[R]){//L代表現在這一段的比較數字的指針swap(nums,++less,L++);}else if(nums[L]>nums[R]){ swap(nums,--more,L);//指針不前移，因為此時大于區的左邊界換過來的數據還沒有進行比較}else{L++;}} swap(nums,more,R);return new int[]{less+1,more};//返回的more沒有加1是因為最后進行了交換，也就是上一行代碼，此時more指向的是等于區的最后一個元素，把最后一個元素交換過來的就是被比較數字} }

二、查找

2.1 二分查找（有序數組找某個數是否存在）

時間復雜度為log2N

三、尋找最大數字

尋找某一個數組里的某一段區間的最大值

public class GetMax{public static int process(int[] arr, int L,int R){if(L==R){return arr[L]; }int mid = ((R-L)>>1);//尋找到中點//遞歸調用int leftMax = process(arr,L,mid);int rightMax = process(arr,mid+1,R);return Math.max(leftMax,rightMax);} }

四、兩數之和

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++) {if(map.containsKey(target - nums[i])) {return new int[] {map.get(target-nums[i]),i};}map.put(nums[i], i);}throw new IllegalArgumentException("No two sum solution");} }

總結

以上是生活随笔為你收集整理的速来围观！leetcode java实现汇总的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。