上節(jié)我們學習了插入排序,其實插入排序存在一些小的缺陷,還是不夠完美,所以有人在它的基礎上進行了完善,.由于完善的人叫希爾,故此算法的思想叫希爾排序算法思想,為啥說插入排序有缺陷了,我們來簡單的看一個例子:
- 假如我有這樣一個待排序的數(shù)組如: int [] arr = {2,3,4,5,6,1},通過之前的分步推導我們來看排序的過程:
- 第一輪排序的代碼如下:
//逐步推導過程
//{2,3,4,5,6,1} -> 首先以{2}為有序列表,以{3,4,5,6,1}為無序列表
//將無序列表中的數(shù)往有序列表中添加
//定義待插入的數(shù)和索引下標
int insertVal = arr[1]; //這里也就是3
int insertIndex = 1 - 1; //arr[1]前面數(shù)的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數(shù)還沒有找到插入的位置
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第一輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
由于上述給的排序的數(shù)組的特殊性,其實我們的while循環(huán)是不進去的,只需要因為將無序列表的3插入有序列表的{2}中時,3>2,所以插入到有序列表{2}的后面即{2,3}來看測試結果:
第一輪排序結果.png
跟我們預想的結果一樣,接著看:
- 第二輪排序過程:
//定義待插入的數(shù)和索引下標
insertVal = arr[2];
insertIndex = 2-1;
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數(shù)還沒有找到插入的位置如:
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex];
insertIndex --;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1
arr[insertIndex + 1] = insertVal;
System.out.println("第二輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
分析過程跟第一輪的一樣,我們來看結果:
第二輪排序結果.png
- 第三輪排序過程
//定義待插入的數(shù)和索引下標
insertVal = arr[3]; //這里也就是119
insertIndex = 3-1; //arr[2]前面數(shù)的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數(shù)還沒有找到插入的位置如: 34 < arr[] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex]; //此時的數(shù)組為{101,101,119,1}
insertIndex --;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第三輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
直接看結果:
第三輪排序結果.png
- 第四輪排序過程
//定義待插入的數(shù)和索引下標
insertVal = arr[4]; //這里也就是119
insertIndex = 4-1; //arr[2]前面數(shù)的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數(shù)還沒有找到插入的位置如: 34 < arr[] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex]; //此時的數(shù)組為{101,101,119,1}
insertIndex --;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第四輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
來看測試結果:
第四輪測試結果.png
- 第五輪排序過程:
//定義待插入的數(shù)和索引下標
insertVal = arr[5]; //這里也就是119
insertIndex = 5-1; //arr[2]前面數(shù)的下標
//簡單說明:
//1. insertIndex>=0 其主要的目的是為了防止在插入時候為了約束越界
//2. insertVal < arr[insertIndex]表示待插入的數(shù)還沒有找到插入的位置如: 34 < arr[] =101
//3. 需要將 arr[insertIndex]往后移動
while (insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex +1] = arr[insertIndex]; //此時的數(shù)組為{101,101,119,1}
insertIndex --;
}
//當退出while循環(huán)時,說明插入的位置找到,需要 insertIndex +1 如: 34改為 134
arr[insertIndex + 1] = insertVal;
System.out.println("第五輪插入后的結果為:");
System.out.println(Arrays.toString(arr));
通過五步我們完成了對它的排序過程,期待吧,心累:
第五輪排序結果.png
其實我們也能發(fā)現(xiàn)問題,我們要對1進行排序時需要移動的次數(shù)太頻繁,這樣是很耗時的一個操作,當然會影響我們的效率,所以著名的希爾提出了新的算法思想對它進行了優(yōu)化操作---------->希爾排序思想,首先我們來對它進行一個簡單的介紹
希爾排序的介紹
我們都說了,希爾排序排序的本質(zhì)是插入排序,由希爾本人在1959年提出的算法思想,是對插入排序的完善后的一個高效版本的插入排序,同時也稱作為縮小增量排序.
我們通過一張示意圖來了解下希爾[排序的過程和思想
希爾排序示意圖.png
簡單的來說一下上述圖解的過程
- 首先我們將上述數(shù)組分成步長為5,也就是5組數(shù)組,就像圖中的一樣,同一種顏色為一組如[8,3]為一組.
- 接著對每一組的數(shù)據(jù)進行插入排序,將小的數(shù)字排到了前面,然后在縮小步長也就是5/2 = 2,將數(shù)組分成了2組也就是圖中所示
- 對步長為2的數(shù)組進行插入排序排序之后,繼續(xù)分組為 2/2 =1 ,也就是圖中最后一個我們將數(shù)組分為了一組最后進行排序即可.
上述的過程每一次都再縮小步長,我們可以發(fā)現(xiàn)從5---->2------>1,最后完成排序,簡單的對希爾排序算法的思想進行總結
希爾排序算法的思想
希爾排序就是將一組待排序的數(shù)字按下標進行一定增量的分組,對每組直接使用插入排序的算法,隨著增量的減少,每組包含的數(shù)字也越來越多,當增量減至1時,整個列表被分為一組,也就是我們算法的停止.
假設我有一組待排序的數(shù)字如: int [] arr = {8,9,1,7,2,3,5,4,6,0},我們通過代碼的方式來完成對它的排序:
代碼實現(xiàn)希爾排序算法
- 第一輪的排序?qū)崿F(xiàn)過程
//第一輪排序
//首先將10個數(shù)據(jù)分成5組了
int temp = 0;
for (int i = 5; i<arr.length; i++){
//內(nèi)循環(huán)的說明:
//遍歷各組中所有的元素(總共5組,每組有2個元素),步長為5如 8 和3為一組,9和5為一組等等
for (int j = i -5; j >=0; j-=5){
//如果當前元素大于+步長后的那個元素,則進行位置的交換
if (arr[j] > arr[j+5]){
temp =arr[j];
arr[j] = arr[j+5];
arr[j+5] = temp;
}
}
}
System.out.println("第一輪的排序結果為:");
System.out.println(Arrays.toString(arr));
- 來看測試結果:
希爾排序第一輪測試結果.png
- 第二輪的代碼實現(xiàn)過程
//第二輪排序
//在前面5組的基礎上進行分5/2 = 2組
for (int i = 2; i<arr.length; i++){
//內(nèi)循環(huán)的說明:
//遍歷各組中所有的元素(總共5組,每組有2個元素),步長為5如 8 和3為一組,9和5為一組等等
for (int j = i -2; j >=0; j-=2){
//如果當前元素大于+步長后的那個元素,則進行位置的交換
if (arr[j] > arr[j+2]){
temp =arr[j];
arr[j] = arr[j+2];
arr[j+2] = temp;
}
}
}
System.out.println("第二輪的排序結果為:");
System.out.println(Arrays.toString(arr));
-
來看測試結果:
希爾排序第二輪測試結果.png - 第三輪的代碼實現(xiàn)過程
//第三輪排序
//因為是第三輪排序,我們將10個數(shù)字分為2/2 = 1組
for (int i = 1; i<arr.length; i++){
//內(nèi)循環(huán)的說明:
//遍歷各組中所有的元素(總共5組,每組有2個元素),步長為5如 8 和3為一組,9和5為一組等等
for (int j = i -1; j >=0; j-=1){
//如果當前元素大于+步長后的那個元素,則進行位置的交換
if (arr[j] > arr[j+1]){
temp =arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println("第三輪的排序結果為:");
System.out.println(Arrays.toString(arr));
-
來看測試結果
希爾排序第三輪測試結果.png
之前我們也通過圖來了解了該過程,通過三輪的排序我們完成了對該數(shù)組的數(shù)字從小到大的排序過程,我們對代碼來優(yōu)化下.
代碼優(yōu)化
//希爾排序方法
public static void shellSort(int[] arr){
//定義一個臨時的變量來儲存交換的元素
int temp = 0;
int count = 0;
for (int gap = arr.length /2;gap>0; gap /= 2){
for (int i = gap; i<arr.length; i++){
//內(nèi)循環(huán)的說明:
//遍歷各組中所有的元素(總共5組,每組有2個元素),步長為gap如 8 和3為一組,9和5為一組等等
for (int j = i -gap; j >=0; j-=gap){
//如果當前元素大于+步長后的那個元素,則進行位置的交換
if (arr[j] > arr[j+gap]){
temp =arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
count ++;
System.out.println("第"+count+"輪的排序結果為:");
System.out.println(Arrays.toString(arr));
}
上述代碼是采用交換的一種方式來完成排序,也就是說我們每發(fā)現(xiàn)一個就立馬進行交換,這種寫法其實也沒毛病,我們來看下另外一種(移位法)來實現(xiàn),代碼如下,大家可以比較兩個算法的好與不好:
- 移位法
//方法優(yōu)化(移位法)
public static void shellSort2(int [] arr){
//gap為步長
for (int gap = arr.length /2; gap >0 ; gap /=2) {
//從gap個元素開始,對其所在組進行插入排序
for (int i = gap; i < arr.length ; i++) {
int j = i; //交換變量
int temp = arr[j];
//表示需要進行位置的交換
if (arr[j] < arr[j - gap] ){
while (j -gap >=0 && temp < arr[j-gap]){
//移動
arr[j] = arr[j-gap];
j -= gap;
}
//當退出循環(huán)時,表示給temp找到了插入的位置
arr[j] = temp;
}
}
}
}
這里就不測試了,我們最后來看下希爾排序的執(zhí)行時間如何,同樣是10W數(shù)據(jù)的排序,代碼如下:
//插入的時間復雜度測試
int [] arr = new int[100000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 100000); //隨機生成[0,100000)的數(shù)
}
Date date1 = new Date();
SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format = dateFormat.format(date1);
System.out.println("排序前的時間為:"+format);
//進行排序
shellSort(arr);
Date date2 = new Date();
SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format2 = dateFormat.format(date2);
System.out.println("排序后的時間為:"+format2);
}
- 測試結果如下:
交換法的執(zhí)行時間.png
來看下移位法的執(zhí)行時間
移位法的執(zhí)行時間結果.png
從上圖我們可以看出兩個方式算法的執(zhí)行效率,那么關于希爾算法的學習就到這里了....
