希爾排序是插入排序的一種，又稱“縮小增量排序”，是插入排序演算法的一種更高效的改進版本，
思想：
將待排序陣列按照步長gap進行分組，然后將每組的元素利用直接插入排序的方法進行排序；每次將gap折半減小，回圈上述操作；當 gap=1時，利用直接插入，完成排序，同樣的：從上面的描述中我們可以發現：希爾排序的總體實作應該由三個回圈完成：第一層回圈：將gap依次折半，對序列進行分組，直到gap=1第二、三層回圈：也即直接插入排序所需要的兩次回圈，
代碼
移位法
public static void shell(int[] arr) {
int index = 0;//記錄當前分組的元素索引
int indexVal = 0;//元素值
for (int gap = arr.length / 2; gap > 0; gap /= 2) {//進行分組
for (int i = gap; i < arr.length; i++) {//對每個分組進行遍歷
index = i;
indexVal = arr[i];
while (index - gap >= 0 && arr[index - gap] > indexVal) {
arr[index] = arr[index - gap];//向后移動
index -= gap;//按步長向后移動
}
arr[index] = indexVal;//移動完成后，當前位置就是indexVal所需要存放的位置
}
}
}
/**
* 交換元素
*
* @param arr
* @param i
* @param j
*/
public static void exchage(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
交換法
/**
* 交換法
*
* @param arr
*/
public static void shellSoer(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {//進行分組
//遍歷每個分組
for (int i = gap; i < arr.length; i++) {
//對一個分組的元素進行排序
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) exchage(arr, j + gap, j);//滿足條件進行交換
}
}
}
}
交換法和位移法速度比較：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243664.html
標籤：其他
上一篇：高級篇之使用ENC編碼器實作USBCam攝像頭豎屏直播的方法
下一篇：公司使用Qt到底要不要付費？