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