Java实现的几个常用排序算法.docx

Java实现的几个常用排序算法.docx

《Java实现的几个常用排序算法.docx》由会员分享，可在线阅读，更多相关《Java实现的几个常用排序算法.docx（23页珍藏版）》请在冰点文库上搜索。

Java实现的几个常用排序算法

Java实现的几个常用排序算法详细解读

排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。

废话不多说，下面逐一看看经典的排序算法：

1.选择排序

选择排序的基本思想是遍历数组的过程中，以i代表当前需要排序的序号，则需要在剩余的[i…n-1]中找出其中的最大值，然后将找到的最大值与i指向的值进行交换。

因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。

举个实例来看看：

初始：

[38,17,16,16,7,31,39,32,2,11]

i=0:

 [2,17,16,16,7,31,39,32,38,11]（0th[38]<->8th[2]）

i=1:

 [2,7,16,16,17,31,39,32,38,11]（1st[38]<->4th[17]）

i=2:

 [2,7,11,16,17,31,39,32,38,16]（2nd[11]<->9th[16]）

i=3:

 [2,7,11,16,17,31,39,32,38,16]（无需交换）

i=4:

 [2,7,11,16,16,31,39,32,38,17]（4th[17]<->9th[16]）

i=5:

 [2,7,11,16,16,17,39,32,38,31]（5th[31]<->9th[17]）

i=6:

 [2,7,11,16,16,17,31,32,38,39]（6th[39]<->9th[31]）

i=7:

 [2,7,11,16,16,17,31,32,38,39]（无需交换）

i=8:

 [2,7,11,16,16,17,31,32,38,39]（无需交换）

i=9:

 [2,7,11,16,16,17,31,32,38,39]（无需交换）

由例子可以看出，选择排序随着排序的进行（i逐渐增大），比较的次数会越来越少，但是不论数组初始是否有序，选择排序都会从i至数组末尾进行一次选择比较，所以给定长度的数组，选择排序的比较次数是固定的：

1+2+3+….+n-1=n*（n-1）/2，而交换的次数则跟初始数组的顺序有关，如果初始数组顺序为随机，则在最坏情况下，数组元素将会交换n次，最好的情况下则可能0次（数组本身即为有序）。

由此可以推出，选择排序的时间复杂度和空间复杂度分别为O（n2）和O

（1）（选择排序只需要一个额外空间用于数组元素交换）。

实现代码：

1./**  * Selection Sorting  */  

2.SELECTION（new Sortable（） {  

3.    public > void sort（T[] array, boolean ascend） {  

4.        int len = array.length;  

5.        for （int i = 0; i < len; i++） {  

6.            int selected = i;  

7.            for （int j = i + 1; j < len; j++） {  

8.                int compare = array[j].compareTo（array[selected]）;  

9.                if （compare !

= 0 && compare < 0 == ascend） {  

10.                    selected = j;  

11.                }  

12.            }  

13.  

14.            exchange（array, i, selected）;  

15.        }  

16.    }  

17.}）  

/**

*SelectionSorting

*/

SELECTION（newSortable（）{

public>voidsort（T[]array,booleanascend）{

intlen=array.length;

for（inti=0;i

intselected=i;

for（intj=i+1;j

intcompare=array[j].compareTo（array[selected]）;

if（compare!

=0&&compare<0==ascend）{

selected=j;

}

}

exchange（array,i,selected）;

}

}

}）

 2.插入排序

插入排序的基本思想是在遍历数组的过程中，假设在序号i之前的元素即[0..i-1]都已经排好序，本趟需要找到i对应的元素x的正确位置k，并且在寻找这个位置k的过程中逐个将比较过的元素往后移一位，为元素x“腾位置”，最后将k对应的元素值赋为x，插入排序也是根据排序的特性来命名的。

以下是一个实例，红色标记的数字为插入的数字，被划掉的数字是未参与此次排序的元素，红色标记的数字与被划掉数字之间的元素为逐个向后移动的元素，比如第二趟参与排序的元素为[11,31,12]，需要插入的元素为12，但是12当前并没有处于正确的位置，于是我们需要依次与前面的元素31、11做比较，一边比较一边移动比较过的元素，直到找到第一个比12小的元素11时停止比较，此时31对应的索引1则是12需要插入的位置。

初始：

  [11,31,12,5,34,30,26,38,36,18]

第一趟：

[11,31,12,5,34,30,26,38,36,18]（无移动的元素）

第二趟：

[11,12,31,5,34,30,26,38,36,18]（31向后移动）

第三趟：

[5,11,12,31,34,30,26,38,36,18]（11,12,31皆向后移动）

第四趟：

[5,11,12,31,34,30,26,38,36,18]（无移动的元素）

第五趟：

[5,11,12,30,31,34,26,38,36,18]（31,34向后移动）

第六趟：

[5,11,12,26,30,31,34,38,36,18]（30,31,34向后移动）

第七趟：

[5,11,12,26,30,31,34,38,36,18]（无移动的元素）

第八趟：

[5,11,12,26,30,31,34,36,38,18]（38向后移动）

第九趟：

[5,11,12,18,26,30,31,34,36,38]（26,30,31,34,36,38向后移动）

插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于1+2+3…+n-1=n*（n-1）/2，这种极端情况下，插入排序的效率甚至比选择排序更差。

因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。

一般情况下，插入排序的时间复杂度和空间复杂度分别为O（n2）和O

（1）。

实现代码：

1./**  * Insertion Sorting */  

2.INSERTION（new Sortable（） {  

3.    public > void sort（T[] array, boolean ascend） {  

4.        int len = array.length;  

5.        for （int i = 1; i < len-1; i++） {  

6.            T toInsert = array[i];  

7.            int j = i;  

8.            for （; j > 0; j--） {  

9.                int compare = array[j - 1].compareTo（toInsert）;  

10.                if （compare == 0 || compare < 0 == ascend） {  

11.                    break;  

12.                }  

13.                array[j] = array[j - 1];  

14.            }  

15.  

16.            array[j] = toInsert;  

17.        }  

18.    }  

19.}）  /**

*InsertionSorting

*/

INSERTION（newSortable（）{

public>voidsort（T[]array,booleanascend）{

intlen=array.length;

for（inti=1;i

TtoInsert=array[i];

intj=i;

for（;j>0;j--）{

intcompare=array[j-1].compareTo（toInsert）;

if（compare==0||compare<0==ascend）{

break;

}

array[j]=array[j-1];

}

array[j]=toInsert;

}

}

}）

3.冒泡排序

冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层for循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素“浮”到最前面，所以称之为冒泡排序。

照例举个简单的实例吧：

初始状态：

 [24,19,26,39,36,7,31,29,38,23]

内层第一趟：

[24,19,26,39,36,7,31,29,23,38]（9th[23]<->8th[38）

内层第二趟：

[24,19,26,39,36,7,31,23,29,38]（8th[23]<->7th[29]）

内层第三趟：

[24,19,26,39,36,7,23,31,29,38]（7th[23]<->6th[31]）

内层第四趟：

[24,19,26,39,36,7,23,31,29,38]（7、23都位于正确的顺序，无需交换）

内层第五趟：

[24,19,26,39,7,36,23,31,29,38]（5th[7]<->4th[36]）

内层第六趟：

[24,19,26,7,39,36,23,31,29,38]（4th[7]<->3rd[39]）

内层第七趟：

[24,19,7,26,39,36,23,31,29,38]（3rd[7]<->2nd[26]）

内层第八趟：

[24,7,19,26,39,36,23,31,29,38]（2nd[7]<->1st[19]）

内层第九趟：

[7,24,19,26,39,36,23,31,29,38]（1st[7]<->0th[24]）

…...

其实冒泡排序跟选择排序比较相像，比较次数一样，都为n*（n+1）/2，但是冒泡排序在挑选最小值的过程中会进行额外的交换（冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换），所以在我看来，选择排序属于冒泡排序的改进版。

实现代码：

1./**  * Bubble Sorting, it's very similar with Insertion Sorting  */  

2.BUBBLE（new Sortable（） {  

3.    public > void sort（T[] array, boolean ascend） {  

4.        int length = array.length;  

5.        int lastExchangedIdx = 0;  

6.        for （int i = 0; i < length; i++） {  

7.            // mark the flag to identity whether exchange happened to false  

8.            boolean isExchanged = false;  

9.            // last compare and exchange happened before reaching index i  

10.            int currOrderedIdx = lastExchangedIdx > i ?

 lastExchangedIdx :

 i;  

11.            for （int j = length - 1; j > currOrderedIdx; j--） {  

12.                int compare = array[j - 1].compareTo（array[j]）;  

13.                if （compare !

= 0 && compare > 0 == ascend） {  

14.                    exchange（array, j - 1, j）;  

15.                    isExchanged = true;  

16.                    lastExchangedIdx = j;  

17.                }  

18.            }  

19.            // if no exchange happen means array is already in order  

20.            if （isExchanged == false） {  

21.                break;  

22.            }  

23.        }  

24.    }  

25.}）  /**

*BubbleSorting,it'sverysimilarwithInsertionSorting

*/

BUBBLE（newSortable（）{

public>voidsort（T[]array,booleanascend）{

intlength=array.length;

intlastExchangedIdx=0;

for（inti=0;i

//marktheflagtoidentitywhetherexchangehappenedtofalse

booleanisExchanged=false;

//lastcompareandexchangehappenedbeforereachingindexi

intcurrOrderedIdx=lastExchangedIdx>i?

lastExchangedIdx:

i;

for（intj=length-1;j>currOrderedIdx;j--）{

intcompare=array[j-1].compareTo（array[j]）;

if（compare!

=0&&compare>0==ascend）{

exchange（array,j-1,j）;

isExchanged=true;

lastExchangedIdx=j;

}

}

//ifnoexchangehappenmeansarrayisalreadyinorder

if（isExchanged==false）{

break;

}

}

}

}）

4.希尔排序

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。

希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以gap来划分，比如数组[1,2,3,4,5,6,7,8]，如果以gap=2来划分，可以分为[1,3,5,7]和[2,4,6,8]两个数组（对应的，如gap=3，则划分的数组为：

[1,4,7]、[2,5,8]、[3,6]）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小gap值重复进行之前的步骤，直至gap=1，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题。

具体实例请参照插入排序。

希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

实现代码：

1./**  * Shell Sorting  */  

2.SHELL（new Sortable（） {  

3.    public > void sort（T[] array, boolean ascend） {  

4.        int length = array.length;  

5.        int gap = 1;  

6.  

7.        // use the most next to length / 3 as the first gap  

8.        while （gap < length / 3） {  

9.            gap = gap * 3 + 1;  

10.        }  

11.  

12.        while （gap >= 1） {  

13.            for （int i = gap; i < length; i++） {  

14.                T next = array[i];  

15.                int j = i;  

16.                while （j >= gap） {  

17.                    int compare = array[j - gap].compareTo（next）;  

18.                    // already find its position  

19.                    if （compare == 0 || compare < 0 == ascend） {  

20.                        break;  

21.                    }  

22.  

23.                    array[j] = array[j - gap];  

24.                    j -= gap;  

25.                }  

26.                if （j !

= i） {  

27.                    array[j] = next;  

28.                }  

29.            }  

30.            gap /= 3;  

31.        }  

32.  

33.    }  

34.}）  

/**

*ShellSorting

*/

SHELL（newSortable（）{

public>voidsort（T[]array,booleanascend）{

intlength=array.length;

intgap=1;

//usethemostnexttolength/3asthefirstgap

while（gap