排序使我們實(shí)際開發(fā)中最常使用到的幾個(gè)算法之一，按照如果按照排序過程中依據(jù)的原則對內(nèi)部排序進(jìn)行分類，則大致上可以分為插入排序、交換排序、選擇排序、歸并排序等排序方法，
數(shù)據(jù)結(jié)構(gòu)與算法之排序(歸納總結(jié)一)
。讓我們首先看看插入排序的算法有哪些，以及他們的具體實(shí)現(xiàn)。插入排序的基本排序思想是：逐個(gè)考察每個(gè)待排序元素，將每一個(gè)新元素插入到前面已經(jīng)排好序的序列中適當(dāng)?shù)奈恢蒙希沟眯滦蛄腥匀皇且粋�(gè)有序序列。在這一類排序中主要介紹三種排序方法：直接插入排序、折半插入排序和希爾排序。1.直接插入排序
a.算法描述
直接插入排序是一種最簡單的插入排序方法，它的基本思想是：僅有一個(gè)元素的序列總是有序的，因此，對n個(gè)記錄的序列，可從第二個(gè)元素開始直到第n個(gè)元素，逐個(gè)向有序序列中執(zhí)行插入操作，從而得到n個(gè)元素按關(guān)鍵字有序的序列。一般來說，在含有j-1 個(gè)元素的有序序列中插入一個(gè)元素的方法是：從第j-1 個(gè)元素開始依次向前搜索應(yīng)當(dāng)插入的位置，并且在搜索插入位置的同時(shí)可以后移元素，這樣當(dāng)找到適當(dāng)?shù)牟迦胛恢脮r(shí)即可直接插入元素。以關(guān)鍵字序列{ 26 , 53 , 48 , 11 , 13 , 48, 32 , 15}為例，直接插入排序的過程如下所示。
b:算法實(shí)現(xiàn)
public void insertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++)
if (compare(r[i], r[i - 1])) { // 小于時(shí)，需將r[i]插入有序表
int temp = r[i];
r[i] = r[i - 1];
int j = i - 2;
for (; j >= low && compare(temp, r[j]); j--)
r[j + 1] = r[j]; // 記錄后移
r[j + 1] = temp; // 插入到正確位置
}
}
【效率分析】
空間效率：僅使用一個(gè)輔存單元。
時(shí)間效率：假設(shè)待排序的元素個(gè)數(shù)為n，則向有序表中逐個(gè)插入記錄的操作進(jìn)行了n-1趟，每趟操作分為比較關(guān)鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。直接插入排序的時(shí)間復(fù)雜度為O(n²)
c:實(shí)現(xiàn)舉例
StraightInsertionSort.java
package com.test.sort.insertion;
public class StraightInsertionSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("直接插入排序排序功能實(shí)現(xiàn)》》》》");
int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };
StraightInsertionSort sort = new StraightInsertionSort();
System.out.println("排序之前序列：");
sort.printArr(arr);
sort.insertSort(arr, 0, arr.length - 1);
System.out.println("排序之后序列：");
sort.printArr(arr);
}
public void insertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++)
if (compare(r[i], r[i - 1])) { // 小于時(shí)，需將r[i]插入有序表
int temp = r[i];
r[i] = r[i - 1];
int j = i - 2;
for (; j >= low && compare(temp, r[j]); j--)
r[j + 1] = r[j]; // 記錄后移
r[j + 1] = temp; // 插入到正確位置
}
}
public boolean compare(int paramA, int paramB) {
if (paramA < paramB) {
return true;
} else {
return false;
}
}
/**
* 依次打印出數(shù)組元素
*/
public void printArr(int[] arr) {
if (arr != null) {
for (int temp : arr) {
System.out.print(temp + " ");
}
System.out.println();
}
}
}
d：結(jié)果輸出
2.希爾排序
a.算法描述
希爾排序又稱為“縮小增量排序”，它也是一種屬于插入排序類的排序方法，是一種對直接插入排序的改進(jìn)，但在時(shí)間效率上卻有較大的改進(jìn)。從對直接插入排序的分析中知道，雖然直接插入排序的時(shí)間復(fù)雜度為O(n²)，但是在待排序元素序列有序時(shí)，其時(shí)間復(fù)雜度可提高至O(n)。由此可知在待排序元素基本有序時(shí)，直接插入排序的效率可以大大提高。從另一方面看，由于直接插入排序方法簡單，則在n值較小時(shí)效率也較高。希爾排序正是從這兩點(diǎn)出發(fā)，對直接插入排序進(jìn)行改進(jìn)而得到的一種排序方法。
希爾排序的基本思想是：首先將待排序的元素分為多個(gè)子序列，使得每個(gè)子序列的元素個(gè)數(shù)相對較少，對各個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)待排序序列“基本有序”后，再對所有元素進(jìn)行一次直接插入排序。根據(jù)上述排序思想，下面我們給出希爾排序的排序過程：
⑴選擇一個(gè)步長序列t1，t2，…，tk，其中ti>tj（i ⑵按步長序列個(gè)數(shù)k，對待排序元素序列進(jìn)行k趟排序； ⑶每趟排序，根據(jù)對應(yīng)的步長ti，將待排序列分割成ti個(gè)子序列，分別對各子序列進(jìn)行直接插入排序。當(dāng)步長因子為1時(shí)，所有元素作為一個(gè)序列來處理，其長度為n。以關(guān)鍵字序列{ 26 , 53 , 67 , 48 , 57 , 13 , 48, 32 , 60 , 50}為例，假設(shè)選擇的步長序列為{5 , 3 , 1}，則希爾排序的過程如圖9-2所示。因?yàn)椴介L序列長度為3，因此對待排序序列一共需要進(jìn)行3趟排序。首先，第一趟排序中將關(guān)鍵字序列分成5個(gè)子序列{26 , 13}，{53 , 48}，{67 , 32}，{48 , 60}，{57 , 50}，對它們分別進(jìn)行直接插入排序，結(jié)果如圖所示。然后，進(jìn)行第二趟希爾排序，此時(shí)步長為3，則將關(guān)鍵字序列分成3個(gè)子序列{13 , 48 , 53 , 57}，{48, 50 , 67}，{32 , 26 , 60}，對它們進(jìn)行直接插入排序后的結(jié)果如圖所示。最后，對整個(gè)序列進(jìn)行一趟直接插入排序，此時(shí)得到一個(gè)關(guān)鍵字有序的序列，希爾排序結(jié)束。 b.算法實(shí)現(xiàn) public void shellSort(int[] r, int low, int high, int[] delta) { for (int k = 0; k < delta.length; k++) shellInsert(r, low, high, delta[k]); // 一趟步長為delta[k]的直接插入排序 } private void shellInsert(int[] r, int low, int high, int deltaK) { for (int i = low + deltaK; i <= high; i++) if (compare(r[i], r[i - deltaK])) { // 小于時(shí)，需將r[i] 插入有序表 int temp = r[i]; int j = i - deltaK; for (; j >= low && compare(temp, r[j]); j = j - deltaK) r[j + deltaK] = r[j]; // 記錄后移 [j]; r[j + deltaK] = temp; // 插入到正確位置 } } 【效率分析】 空間效率：僅使用一個(gè)輔存單元。 時(shí)間效率：假設(shè)待排序的元素個(gè)數(shù)為n，則向有序表中逐個(gè)插入記錄的操作進(jìn)行了n-1趟，每趟操作分為比較關(guān)鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。直接插入排序的時(shí)間復(fù)雜度為O(n²) c.使用示例 HashInsertSort.java package com.test.sort.insertion; public class HashInsertSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("希爾排序功能實(shí)現(xiàn)》》》》"); int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 }; int[] delta = {5,3,1}; HashInsertSort sort = new HashInsertSort(); System.out.println("排序之前序列："); sort.printArr(arr); sort.shellSort(arr, 0, arr.length - 1,delta); System.out.println("排序之后序列："); sort.printArr(arr); } public void shellSort(int[] r, int low, int high, int[] delta) { for (int k = 0; k < delta.length; k++) shellInsert(r, low, high, delta[k]); // 一趟步長為delta[k]的直接插入排序 } private void shellInsert(int[] r, int low, int high, int deltaK) { for (int i = low + deltaK; i <= high; i++) if (compare(r[i], r[i - deltaK])) { // 小于時(shí)，需將r[i] 插入有序表 int temp = r[i]; int j = i - deltaK; for (; j >= low && compare(temp, r[j]); j = j - deltaK) r[j + deltaK] = r[j]; // 記錄后移 [j]; r[j + deltaK] = temp; // 插入到正確位置 } } public boolean compare(int paramA, int paramB) { if (paramA < paramB) { return true; } else { return false; } } /** * 依次打印出數(shù)組元素 */ public void printArr(int[] arr) { if (arr != null) { for (int temp : arr) { System.out.print(temp + " "); } System.out.println(); } } } d.結(jié)果輸出 3.折半插入排序 a.算法描述 直接插入排序算法簡便、容易實(shí)現(xiàn)，電腦資料
《數(shù)據(jù)結(jié)構(gòu)與算法之排序(歸納總結(jié)一)》(http://m.clearvueentertainment.com)。當(dāng)待排序元素的數(shù)量n很小時(shí)，這是一種較好的排序方法，但是通常待排序元素?cái)?shù)量n很大，則不宜采用直接插入排序方法，此時(shí)需要對直接插入排序進(jìn)行改進(jìn)。直接插入排序的基本操作是向有序序列中插入一個(gè)元素，插入位置的確定是通過對有序序列中元素按關(guān)鍵字逐個(gè)比較得到的。既然是在有序序列中確定插入位置，則可以不斷二分有序序列來確定插入位置，即搜索插入位置的方法可以使用折半查找實(shí)現(xiàn)。
b.算法實(shí)現(xiàn)
public void binInsertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int temp = r[i]; // 保存待插入元素
int hi = i - 1;
int lo = low; // 設(shè)置初始區(qū)間
while (lo <= hi) { // 折半確定插入位置
int mid = (lo + hi) / 2;
if (compare(temp, r[mid]))
hi = mid - 1;
else
lo = mid + 1;
}
for (int j = i - 1; j > hi; j--)
r[j + 1] = r[j]; // 移動元素
r[hi + 1] = temp; // 插入元素
}// for
}
【效率分析】
空間效率：僅使用一個(gè)輔存單元。
時(shí)間效率：折半插入排序僅減少了元素的比較次數(shù)，但是并沒有減少元素的移動次數(shù),折半插入排序的時(shí)間復(fù)雜度為O(n²)。
c.應(yīng)用舉例
BinaryInsertSort.java
package com.test.sort.insertion;
public class BinaryInsertSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("折半插入排序排序功能實(shí)現(xiàn)》》》》");
int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };
BinaryInsertSort sort = new BinaryInsertSort();
System.out.println("排序之前序列：");
sort.printArr(arr);
sort.binInsertSort(arr, 0, arr.length - 1);
System.out.println("排序之后序列：");;
sort.printArr(arr);
}
public void binInsertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int temp = r[i]; // 保存待插入元素
int hi = i - 1;
int lo = low; // 設(shè)置初始區(qū)間
while (lo <= hi) { // 折半確定插入位置
int mid = (lo + hi) / 2;
if (compare(temp, r[mid]))
hi = mid - 1;
else
lo = mid + 1;
}
for (int j = i - 1; j > hi; j--)
r[j + 1] = r[j]; // 移動元素
r[hi + 1] = temp; // 插入元素
}// for
}
public boolean compare(int paramA, int paramB) {
if (paramA < paramB) {
return true;
} else {
return false;
}
}
/**
* 依次打印出數(shù)組元素
*/
public void printArr(int[] arr) {
if (arr != null) {
for (int temp : arr) {
System.out.print(temp + " ");
}
System.out.println();
}
}
}