??? 在學習算法的過程中，我們難免會接觸很多和排序相關的算法?？偠灾?#xff0c;對于任何編程人員來說，基本的排序算法是必須要掌握的。

從今天開始，我們將要進行基本的排序算法的講解。Are you ready？Let‘s go~~~

1、排序算法的基本概念的講解

???? 時間復雜度:需要排序的的關鍵字的比較次數和相應的移動的次數。

???? 空間復雜度:分析需要多少輔助的內存。

???? 穩定性:如果記錄兩個關鍵字的A和B它們的值相等，經過排序后它們相對的位置沒有發生交換，那么我們稱這個排序算法是穩定的。

????????????? 否則我們稱這個排序算法是不穩定的。

???

??? 排序算法的常見分類:

??? 1、內部排序（最常見的一種排序方式，不需要借助第三方輔助存儲工具）

??? 2、外部排序（需要借助外部存儲來輔助完成相關的排序操作）

??????? 如果參與排序的數據元素非常的多，數據量非常的大，計算機無法把整個排序過程放到內存中進行的話，

??????? 我們必須借助外部存儲器如磁盤來完成，這種排序方式，我們稱之為外部排序。

??????? 其中外部排序最常見的就是多路歸并排序，即將原始文件分解成多個能夠一次性裝入內存的部分，分別把每一部分調入

??????? 內存完成相應的排序，接下來在對多個有序的外部文件進行多路歸并排序。

??

?? 對于我們絕大多數的程序員而言，我們經常遇到的為內部排序。接下來我們將要對常見的內部排序進行相應的講解。

??? 今天要講解的內部排序為:

?? Shell排序

? 1.Shell排序的基本概念的講解

?? 希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排 ?? 序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。 ?? 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞 ?? 越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。 先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插 入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量 =1( < …<d2<d1)，即所有記錄放在同一組中進行 直接插入排序為止。 ? 該方法實質上是一種分組插入方法 ? 比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比^[2] 較就可能消除多個元素交換。 ? D.L.shell于1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組， ? 每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行，在每組中再進行排序。當增量 ? 減到1時，整個要排序的數被分成一組，排序完成。 ? 一般的初次取序列的一半為增量，以后每次減半，直到增量為1。 ? 給定實例的shell排序的排序過程 ? 假設待排序文件有10個記錄，其關鍵字分別是： ? 49，38，65，97，76，13，27，49，55，04。 ? 增量序列的取值依次為： ? 5，2，1

?

? 2.Shell排序的Java代碼實現

????

package com.yonyou.test;/*** 內部排序算法之Shell排序* 默認按照從小到大進行排序操作* @author 小浩* @創建日期 2015-3-27*/ public class Test{public static void main(String[] args) {//需要進行排序的數組int[] array=new int[]{8,3,2,1,7,4,6,5};//輸出原數組的內容printResult(array);//shell排序操作shellSort(array);//輸出排序后的相關結果printResult(array);}/*** shell排序算法* 增量h=(h*3)+1; 這個增量公式是由Knuth給出的* 如果不是很了解的話請百度一下吧* @param array*/private static void shellSort(int[] array) {//首先根據數組的長度確定增量的最大值int h=1;// 按h * 3 + 1得到增量序列的最大值while(h <= array.length / 3){h = h * 3 + 1;}//進行增量查找和排序while(h>0){ for(int i=h;i<array.length;i++){for(int k=i;k<array.length;k+=h){//判斷是否需要重新排序,如果小于k-h處的值，需要重新排序if(array[k]<array[k-h]){int tempValue=array[k];int j=k;for(;j>=i&&tempValue<array[j-h];j-=h){array[j]=array[j-h];}array[j]=tempValue;}}printResult(array);}h=(h-1)/3;} }/*** * 輸出相應數組的結果* @param array*/private static void printResult(int[] array) {for(int value:array) System.out.print(" "+value+" ");System.out.println();}/*** 交換數組中兩個變量的值* @param array* @param i* @param j*/private static void swap(int[] array,int i,int j){int temp=array[i];array[i]=array[j];array[j]=temp;} }

?

　　

?

?? ??

?

?

?

總結

以上是生活随笔為你收集整理的Java常见排序算法之Shell排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。