各種排序筆記---基于比較排序部分

1. 選擇排序 selection sort

  大循環 從左到右每次以一個點開始掃描array

    小循環 找到從當前起始點開始的最小值

  時間復雜度為O(N^2)

//selection sort an array array[]
public class Solution {public int[] solve(int[] array) {if (array == null || array.length == 0) {return array;}for (int i = 0; i < array.length - 1; i++) {int gobalMin = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[gobalMin]) {gobalMin = j;}}swap(array, i, gobalMin);}return array;}private void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}
Selection sort

?

?

2. 歸并排序 Merge sort

歸并排序是基于一種被稱為“分治”(divide and conquer)的策略。

Merge sort array:

public int[] mergeSort(int[] array) {if (array == null || array.length == 0) {return array;}int[] temp = new int[array.length];mergeSortHelper(array, 0, array.length - 1, temp);return array;}private void mergeSortHelper(int[] array, int start, int end, int[] temp) {if (start == end) {return;}int mid = start + (end - start) / 2;mergeSortHelper(array, start, mid, temp);mergeSortHelper(array, mid + 1, end, temp);merge(array, start, mid, end, temp);}private void merge(int[] array, int start, int mid, int end, int[] temp) {int left = start;int right = mid + 1;int index = start;while (left <= mid && right <= end) {if (array[left] < array[right]) {temp[index++] = array[left++];} else {temp[index++] = array[right++];}}while (left <= mid) {temp[index++] = array[left++];}while (right <= end) {temp[index++] = array[right++];}for (index = start; index <= end; index++) {array[index] = temp[index];}}
merge sort array

復雜度分析:

?

                         1 2 3 4 5 6 7 8?

                          / ?              當前層拆分需要劈1刀 O(1)

                       1 2 3 4

                       /                 當前層拆分需要劈2刀  O(2)

                     12                      ...

                    /

?                  1 ?                      當前層拆分需要劈n ?/2刀

                  1 + 2 + 4 + 8+ ... + n/2 -> n ?= O(n) ?可以這樣理解,終極狀態下每個數字被切分成一個單位,n個數字,需要被切n-1刀

                  所以devide and conquer的上半部分的時間復雜度是O(n) 而不是log(n)

                  空間復雜度:考慮計算機里面只要保存的額外開銷,其實是粉色部分,因為在任意時刻,計算機只有一個確定的狀態,call stack在同一個確定的層只能保留部分的結果。比如最底層只能保留1,或者保留2,而不會1,2同時在棧里面!

                  所以空間復雜度:1 + 2 + 4 + 8 + ... + n = O(2n) = O(n)

?                   ==============================================

            devide and conquer的上半部分,merge 部分, totoal time complexity is O(nlogn):

                      1 ? ? ?2 ? ? ? ? 3 ? ? 4 ? ? ? 5 ? ?6 ? ? ?7 ? ? ? 8

                       \/ ? ? ? ? ? ? ? ?\/ ? ? ? ? ? ? \/ ? ? ? ? ? ? ?\/            this level time complexity is O(n)

                       12 ? ? ? ? ? ? ? 34 ? ? ? ? ? ?56 ? ? ? ? ? ?78

                         \ ? ? /    ? ? ? ? ? ? ? \ ? ? ? ?/             this level time complexity is O(n)

                         1234        5678

                            \ ? ? ? ? ? ? ? ? ? ? ? ? ?/              this level time complexity is O(n)

                             12345678

?

3. 快速排序

Array quick sort:

重點在于理解左右兩個擋板的物理意義!!!

a. [0,....., left]: left 的左側(不包含left)全部為比pivot小的數

b. [left, right]: left 和 right之間為未探索的區域

c. [right, ..... n-1]: right的右側(不包含)全部為比pivot大或者等于的數字

public class Solution {/*** @param A an integer array* @return void*/public void sortIntegers2(int[] A) {quickSort(A, 0, A.length - 1);}private void quickSort(int[] A, int start, int end) {if (start >= end) {return;}int left = start, right = end;// key point 1: pivot is the value, not the indexint pivot = A[(start + end) / 2];// key point 2: every time you compare left & right, it should be // left <= right not left < rightwhile (left <= right) {// key point 3: A[left] < pivot not A[left] <= pivotwhile (left <= right && A[left] < pivot) {left++;}// key point 3: A[right] > pivot not A[right] >= pivotwhile (left <= right && A[right] > pivot) {right--;}if (left <= right) {int temp = A[left];A[left] = A[right];A[right] = temp;left++;right--;}}quickSort(A, start, right);quickSort(A, left, end);}
}
array quick sort

?

偽代碼:

function quicksort(q)var list less, pivotList, greaterif length(q) ≤ 1 {return q} else {select a pivot value pivot from qfor each x in q except the pivot elementif x < pivot then add x to lessif x ≥ pivot then add x to greateradd pivot to pivotListreturn concatenate(quicksort(less), pivotList, quicksort(greater))}

?

?

?

?

?

Linkedlist quick sort

public class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode mid = findMedian(head); // O(n)//new three dummmy node with a tail point to itListNode leftDummy = new ListNode(0), leftTail = leftDummy;ListNode rightDummy = new ListNode(0), rightTail = rightDummy;ListNode middleDummy = new ListNode(0), middleTail = middleDummy;//sprate to three part while (head != null) {if (head.val < mid.val) {leftTail.next = head;leftTail = head;} else if (head.val > mid.val) {rightTail.next = head;rightTail = head;} else {middleTail.next = head;middleTail = head;}head = head.next;}//make the tail to nullleftTail.next = null;middleTail.next = null;rightTail.next = null;//recurisive do the sortListNode left = sortList(leftDummy.next);ListNode right = sortList(rightDummy.next);//connect the three parts togetherreturn concat(left, middleDummy.next, right);}private static ListNode findMedian(ListNode head) {ListNode fast = head.next;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private static ListNode concat(ListNode left, ListNode mid, ListNode right) {ListNode dummy = new ListNode(0), dummyTail = dummy;dummyTail = connect(dummyTail, left);dummyTail = connect(dummyTail, mid);dummyTail = connect(dummyTail, right);return dummy.next;}private static ListNode connect(ListNode dummyTail, ListNode current) {while (current != null) {dummyTail.next = current;dummyTail = dummyTail.next;current = current.next;}return dummyTail;}
}
sortList

?

?

相關題目整理: //to do?

轉載于:https://www.cnblogs.com/jiangchen/p/5935343.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/254160.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/254160.shtml
英文地址,請注明出處:http://en.pswp.cn/news/254160.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

是什么讓深度學習再次崛起并超越人類?

作者潘爭&#xff0c;格靈深瞳計算機視覺工程師&#xff0c;清華大學自動化系博士&#xff0c;師從智能技術與系統國家重點實驗室副主任張長水。深度學習(Deep Learning)這個詞最近借著AlphaGO與李世石的人機大戰又火了一把。深度學習其實是機器學習(Machine Learning)的一個分…

常見的流量問題

常見的流量問題 冗余內容同類請求被間隔執行&#xff0c;請求的內容包含一些相對靜態的信息&#xff0c;正確的處理是第一次請求包括靜態信息就好&#xff0c;后面的同類請求只包含必要的即時變化信息即可。錯誤的處理方式是每次請求服務器都返回一次靜態信息。 冗余請求有的時…

halcon使用點擬合圓形時候,點集順序紊亂,不影響圓形擬合效果

read_image (Image, 截圖20201226094342972.bmp) * Matching 01: BEGIN of generated code for model initialization set_system (border_shape_models, false) * Matching 01: Obtain the model image * Matching 01: The image is assumed to be made available in the * Ma…

Socket理解。

其他大部分系統&#xff0c;例如CRM/CMS/權限框架/MIS之類的&#xff0c;無論怎么復雜&#xff0c;基本上都能夠本地代碼本地調試&#xff0c;性能也不太重要。&#xff08;也許這個就是.net的企業級開發的戰略吧&#xff09; 可是來到通訊系統&#xff0c;一切變得困難復雜。原…

多元化時代敏捷軟件開發的崛起與傳統軟件工程的延續

多元化時代敏捷軟件開發的崛起與傳統軟件工程的延續 1.傳統軟件開發模式 1.1瀑布模型 1.1.1概念 瀑布模型&#xff0c;顧名思義&#xff0c;軟件開發的過程如同瀑布飛流一般&#xff0c;自上而下&#xff0c;逐級下落。瀑布模型的核心思想是將問題按照工序進行簡化&#xff0c;…

Linux中的cron計劃任務配置詳解

cron來源于希臘單詞chronos&#xff08;意為“時間”&#xff09;&#xff0c;指Linux系統下一個自動執行指定任務的程序&#xff08;計劃任務&#xff09; ####1. crontab命令選項代碼如下: #crontab -u <-l, -r, -e> -u指定一個用戶 -l列出某個用戶的任務計劃 -r刪除某…

new和delete

和 sizeof 類似&#xff0c;sizeof不是函數&#xff0c;它是一個操作符&#xff0c;它在編譯期就完成了計算&#xff0c;在函數運行期間它已經是一個常數值了。 int a;sizeof(int) 4;sizeof(a) 4;sizeof a ——也是4 不需要括號&#xff01;此時要注意&#xff1a;sizeof in…

char a[]和char *a的比較,數組名,數組首地址,a,a,a[0]

char a[]和char *a的比較 指針和數組存在著一些本質的區別。當然&#xff0c;在某種情況下&#xff0c;比如數組作為函數的參數進行傳遞時&#xff0c;由于該數組自動退化為同類型的指針&#xff0c;所以在函數內部&#xff0c;作為函數參數傳遞進來的指針與數組確實具有一定的…

Java中繼承thread類與實現Runnable接口的區別

Java中線程的創建有兩種方式&#xff1a; 1&#xff0e; 通過繼承Thread類&#xff0c;重寫Thread的run()方法&#xff0c;將線程運行的邏輯放在其中 2&#xff0e; 通過實現Runnable接口&#xff0c;實例化Thread類 在實際應用中&#xff0c;我們經常用到多線程&#xff0c;…

【VMware vSAN 6.6】6.2.啟用性能服務:vSAN硬件服務器解決方案

目錄 1. 簡介 1.1.適用于HCI的企業級存儲2. 體系結構 2.1.帶有本地存儲的服務器2.2.存儲控制器虛擬系統套裝的缺點2.3.vSAN在vSphere Hypervisor中自帶2.4.集群類型2.5.硬件部署選項3. 啟用vSAN 3.1.啟用vSAN3.2.輕松安裝3.3.主動測試4. 可用性 4.1.對象和組件安置4.2.重新構建…

Android eclipse導入項目后出現Unable to resolve target #39;android-17#39;解決方法

eclipse導入項目后出現Unable to resolve target android-17解決方法。在最后附帶還有一種編譯邏輯不成功情況解決方法。 一、問題情況 二、解決的方法 1、改動項目的目標版本號與當前Android sdk相相應的版本號 2、自己主動修復一下項目 三、這個問題不是上面的。是另外情況&a…

多個圓點,鼠標選取兩個,求兩個點的距離,用于計算像素尺寸(halcon實現)

read_image (Image, C:/Users/22967/Desktop/晶圓找位置/0.bmp) dev_close_window () dev_open_window_fit_image (Image, 0, 0, -1, -1, WindowHandle) dev_display (Image)binary_threshold (Image, Region1, max_separability, dark, UsedThreshold) connection (Region1, C…

修改UBOOT和LINUX調試串口(TI達芬奇芯片--DM6467)

Posted on 2011-10-31 10:53 jamiedu 閱讀(889) 評論(0) 編輯 收藏 1.1 概述 TI針對DM6467提供的UBOOT和內核默認都是串口0作為調試串口輸出的&#xff0c;但現在我需要使用DM6467的UART0的modem功能&#xff0c;所以修改代碼&#xff0c;改變調試串口為串口2。 需要修改的主要…

Java List與數組之間的轉換

http://blog.csdn.net/kingzone_2008/article/details/8444678轉載于:https://www.cnblogs.com/longshiyVip/p/5985981.html

受歡迎的五個開源可視化工具——你的選擇是?

摘要&#xff1a;大數據時代&#xff0c;數據為王&#xff0c;還在對一堆數據而發愁嗎&#xff1f;試試可視化工具吧&#xff0c;相信本文提到的五款工具有一款能夠幫助到你。人工智能時代&#xff0c;數據和算法以及硬件資源是非常重要的&#xff0c;相關行業的大公司也越來越…

halcon車刀崩邊檢測

list_files (新建文件夾, files, Files) read_image (Image, Files[0]) dev_close_window () get_image_size (Image, Width, Height) dev_open_window (0, 0, Width/1.5, Height/1.5, black, WindowHandle) dev_set_draw (margin) dev_set_colored (12) for Index:0 to |Files…

FFMPEG解碼264文件步驟

本文以H264視頻流為例&#xff0c;講解解碼流數據的步驟。 為突出重點&#xff0c;本文只專注于討論解碼視頻流數據&#xff0c;不涉及其它&#xff08;如開發環境的配置等&#xff09;。如果您需要這方面的信息&#xff0c;請和我聯系。 準備變量 定義AVCodecContext。如果…

Storm概念學習系列之storm的特性

不多說&#xff0c;直接上干貨&#xff01; storm的特性 Storm 是一個開源的分布式實時計算系統&#xff0c;可以簡單、可靠地處理大量的數據流。 Storm支持水平擴展&#xff0c;具有高容錯性&#xff0c;保證每個消息都會得到處理&#xff0c;而且處理速度很快&#xff08;在一…

Confluence 6 配置服務器基礎地址示例

2019獨角獸企業重金招聘Python工程師標準>>> 如果 Confluence 的安裝是沒有安裝在非根目錄路徑&#xff08;這個是上下文路徑&#xff09;&#xff0c;然后服務器基礎 URL 地址應該包括上下文地址。例如&#xff0c;你的 Confluence 正在運行在下面的地址&#xff1…

BootstrapValidator驗證

bootstrap&#xff1a;能夠增加兼容性的強大框架. 因為項目需要數據驗證&#xff0c;看bootstrapValidator 還不錯&#xff0c;就上手一直&#xff0c;完美兼容&#xff0c;話不多說。 需要引用css&#xff1a; bootstrap.min.css bootstrapValidator.min.css js: jquery-1.10.…