Java 直接插入排序的三種實(shí)現(xiàn)
直接插入排序(Insertion Sort)的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。
設(shè)數(shù)組為a[0…n-1]。
1. 初始時(shí)，a[0]自成1個(gè)有序區(qū)，無(wú)序區(qū)為a[1..n-1]。令i=1
2. 將a[i]并入當(dāng)前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間。
3. i++并重復(fù)第二步直到i==n-1。排序完成。
下面給出嚴(yán)格按照定義書寫的代碼（由小到大排序）：
void Insertsort1(int a[], int n)
{
int i, j, k;
for (i = 1; i < n; i++)
{
//為a[i]在前面的a[0...i-1]有序區(qū)間中找一個(gè)合適的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一個(gè)合適的位置
if (j != i - 1)
{
//將比a[i]大的數(shù)據(jù)向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//將a[i]放到正確位置上
a[k + 1] = temp;
}
}
}
這樣的代碼太長(zhǎng)了，不夠清晰。現(xiàn)在進(jìn)行一下改寫，將搜索和數(shù)據(jù)后移這二個(gè)步驟合并。即每次a[i]先和前面一個(gè)數(shù)據(jù)a[i-1]比較，如果a[i] > a[i-1]說(shuō)明a[0…i]也是有序的，無(wú)須調(diào)整。否則就令j=i-1,temp=a[i]。然后一邊將數(shù)據(jù)a[j]向后移動(dòng)一邊向前搜索，當(dāng)有數(shù)據(jù)a[j]<a[i]時(shí)停止并將temp放到a[j + 1]處。
void Insertsort2(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
if (a[i] < a[i - 1])
{
int temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
}
再對(duì)將a[j]插入到前面a[0…j-1]的有序區(qū)間所用的方法進(jìn)行改寫，用數(shù)據(jù)交換代替數(shù)據(jù)后移。如果a[j]前一個(gè)數(shù)據(jù)a[j-1] > a[j]，就交換a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。這樣也可以實(shí)現(xiàn)將一個(gè)新數(shù)據(jù)新并入到有序區(qū)間。
void Insertsort3(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
Swap(a[j], a[j + 1]);
}
以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，同時(shí)也希望多多支持腳本之家！
相關(guān)文章
詳談spring boot中幾種常見(jiàn)的依賴注入問(wèn)題
這篇文章主要介紹了spring boot中幾種常見(jiàn)的依賴注入問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了springboot2.x引入feign踩的坑及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
這篇文章主要介紹了java?引用傳遞的三種類型，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02
Lombok是一種Java實(shí)用工具，可用來(lái)幫助開(kāi)發(fā)人員消除Java的冗長(zhǎng)，尤其是對(duì)于簡(jiǎn)單的Java對(duì)象(POJO)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-10-10
本節(jié)詳細(xì)介紹 Kafka 運(yùn)行環(huán)境的搭建，為了節(jié)省篇幅，本節(jié)的內(nèi)容以 Linux CentOS 作為安裝演示的操作系統(tǒng)，其他 Linux 系列的操作系統(tǒng)也可以參考本節(jié)的內(nèi)容，對(duì)Kafka 安裝與配置相關(guān)知識(shí)感興趣的朋友一起看看吧2021-11-11
Java中的Map集合根據(jù)key值排序的實(shí)現(xiàn)
本文主要介紹了Java中的Map集合如何根據(jù)key值排序，包含使用TreeMap和使用lambda表達(dá)式和Stream流兩種方法，具有一定的參考價(jià)值，感興趣的可以了解一下2024-03-03
這篇文章主要介紹了如何利用Java實(shí)現(xiàn)圖片裁剪功能，可以將圖片按照自定義尺寸進(jìn)行裁剪，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2022-01-01
在Spring Boot 2.0中推出了Relaxed Binding 2.0，對(duì)原有的屬性綁定功能做了非常多的改進(jìn)以幫助我們更容易的在Spring應(yīng)用中加載和讀取配置信息，感興趣的小伙伴們可以參考一下2019-03-03
基于SpringBoot+Redis實(shí)現(xiàn)分布式鎖
本文主要介紹了基于SpringBoot+Redis實(shí)現(xiàn)分布式鎖，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
這篇文章主要介紹了Spring中的Actuator使用詳解,在生產(chǎn)環(huán)境中運(yùn)行的程序,并不總是穩(wěn)定、安靜、正確的,往往會(huì)遇到各式各樣的現(xiàn)場(chǎng)狀況,這個(gè)時(shí)候,就需要獲取該程序足夠多的運(yùn)行狀態(tài)信息,然后分析并對(duì)其進(jìn)行有效管理,需要的朋友可以參考下2023-09-09