本篇內(nèi)容介紹了“Java中常用的排序算法有哪些”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
成都創(chuàng)新互聯(lián)公司是一家專注于成都網(wǎng)站建設(shè)、成都網(wǎng)站制作與策劃設(shè)計,玄武網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:玄武等地區(qū)。玄武做網(wǎng)站價格咨詢:13518219792
一:排序的概念
1.排序:所謂排序,就是使一串記錄,按照其中的某個或某些關(guān)鍵字的大小,遞增或遞減的排列起來的操作。
2.穩(wěn)定性:假定在待排序的記錄序列中,存在多個具有相同的關(guān)鍵字的記錄,若經(jīng)過排序,這些記錄的相對次序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,則稱這種排序算法是穩(wěn)定的;否則稱為不穩(wěn)定的。
3.內(nèi)部排序:數(shù)據(jù)元素全部放在內(nèi)存中的排序。
4.外部排序:數(shù)據(jù)元素太多不能同時放在內(nèi)存中,根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。
二:常見的排序方法:
三:各種排序算法的實現(xiàn)原理:`
(1)插入排序的基本思想:
直接插入排序是一種簡單的插入排序法,其基本思想是:把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中,直到所有的記錄插入完為止,得到一個新的有序序列 。**
當(dāng)插入第i(i>=1)個元素時,前面的array[0],array[1],…,array[i-1]已經(jīng)排好序,此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較,找到插入位置即將array[i]插入,原來位置上的元素順序后移。
直接插入排序的特性總結(jié):
元素集合越接近有序,直接插入排序算法的時間效率越高
時間復(fù)雜度:O(N^2)
空間復(fù)雜度:O(1),它是一種穩(wěn)定的排序算法
穩(wěn)定性:穩(wěn)定
(2)希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是:先選定一個整數(shù),把待排序文件中所有記錄分成個組,所有距離為的記錄分在同一組內(nèi),并對每一組內(nèi)的記錄進行排序。然后,取,重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_=1時,所有記錄在統(tǒng)一組內(nèi)排好序。
希爾排序的特性總結(jié):
希爾排序是對直接插入排序的優(yōu)化。
當(dāng)gap > 1時都是預(yù)排序,目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時,數(shù)組已經(jīng)接近有序的了,這樣就
會很快。這樣整體而言,可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
希爾排序的時間復(fù)雜度不好計算,需要進行推導(dǎo),推導(dǎo)出來平均時間復(fù)雜度: O(N^1.3—N^2)
穩(wěn)定性:不穩(wěn)定
(3) 選擇排序
基本思想:
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素,存放在序列的起始位置,直到全部待排序的
數(shù)據(jù)元素排完 。
直接選擇排序:
在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
若它不是這組元素中的最后一個(第一個)元素,則將它與這組元素中的最后一個(第一個)元素交換
在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重復(fù)上述步驟,直到集合剩余1個元素
直接選擇排序的特性總結(jié):
直接選擇排序思考非常好理解,但是效率不是很好。實際中很少使用
時間復(fù)雜度:O(N^2)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
(4)堆排序
堆排序(Heapsort)是指利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法,它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆,排降序建小堆。
堆排序使用堆來選數(shù),效率就高了很多。
時間復(fù)雜度:O(N*logN)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
(5)冒泡排序
基本思想:所謂交換,就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置,交換排序的特點是:將鍵值較大的記錄向序列的尾部移動,鍵值較小的記錄向序列的前部移動。
冒泡排序的特性總結(jié):
冒泡排序是一種非常容易理解的排序
時間復(fù)雜度:O(N^2)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
(6)快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法,其基本思想為:任取待排序元素序列中的某元素作為基準(zhǔn)值,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有元素均小于基準(zhǔn)值,右子序列中所有元素均大于基準(zhǔn)值,然后最左右子序列重復(fù)該過程,直到所有元素都排列在相應(yīng)位置上為止。
快速排序的特性總結(jié):
快速排序整體的綜合性能和使用場景都是比較好的,所以才敢叫快速排序
時間復(fù)雜度:O(N*logN)
空間復(fù)雜度:O(logN)
穩(wěn)定性:不穩(wěn)定
(7)歸并排序
基本思想:
歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide andConquer)的一個非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。
歸并排序的特性總結(jié):
歸并的缺點在于需要O(N)的空間復(fù)雜度,歸并排序的思考更多的是解決在磁盤中的外排序問題。
時間復(fù)雜度:O(N*logN)
空間復(fù)雜度:O(N)
穩(wěn)定性:穩(wěn)定
四:各種排序算法的時間復(fù)雜度,空間復(fù)雜度以及穩(wěn)定性的比較。
“Java中常用的排序算法有哪些”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!