Shulou(Shulou.com)06/03 Report--

This article mainly shows you "Java how to achieve the sorting algorithm", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "Java how to achieve sorting algorithm" this article.

Five sorting algorithms implemented by Java

Sorting algorithm will be used in many places, recently re-read the algorithm, and their own simple implementation, and hereby record it, leaving some materials for future review.

Let's look at the classic sorting algorithms one by one:

1. Selective sorting of Java sorting algorithm

The basic idea of selective sorting is that in the process of traversing the array, I represents the current sequence number that needs to be sorted, then the remaining [I … Find out the minimum value in nMur1], and then swap the minimum value found with the value I points to. Because there is a subprocess of selecting the maximum value in each process of determining the element, it is vividly called selection sorting.

Let me give you an example:

1. Initial: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]

2.3.I = 0: [2,17,16,16,7,31,39,32,38,11] (0th [38] 8th [2])

4.5.I = 1: [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (1st [38] 4th [17])

6.7.I = 2: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (2nd [11] 9th [16])

8.9.I = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (no exchange required)

10.11.I = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4th [17] 9th [16])

12.13.I = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5th [31] 9th [17])

14.15.I = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6th [39] 9th [31])

16.17.I = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no exchange required)

18.19.I = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no exchange is required)

20.21.I = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no exchange is required)

As can be seen from the example, as the sort goes on (I increases gradually), the number of comparisons will become less and less, but no matter whether the array is ordered at the beginning or not, the selection sort will make a selection comparison from I to the end of the array. So for an array of a given length, the number of comparisons of selection sort is fixed: 1 + 2 + 3 + … + n = n * (n + 1) / 2, and the number of exchanges is related to the order of the initial array. If the initial array order is random, in the worst case, the array elements will be exchanged n times. At best, it may be 0 times (the array itself is ordered).

It can be inferred that the time complexity and space complexity of selective sorting are O (N2) and O (1) respectively (selective sorting only needs an extra space for array element exchange).

Implementation code:

1.According to *

2. * Selection Sorting

3. * /

4.SELECTION (new Sortable () {

5. Public

6. Int len = array.length

7. For (int I = 0; I

< len; i++) { 　　8. int selected = i; 　　9. for (int j = i + 1; j < len; j++) { 　　10. int compare = array[j].compareTo(array[selected]); 　　11. if (compare != 0 && compare < 0 == ascend) { 　　12. selected = j; 　　13. } 　　14. } 　　15.16. exchange(array, i, selected); 　　17. } 　　18. } 　　19.}) 　　2、Java排序算法之插入排序 　　插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x "腾位置",最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的。 　　以下是一个实例，红色 标记的数字为插入的数字，被划掉的数字是未参与此次排序的元素，红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素，比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置，于是我们需要依次与前面的元素 31 、 11 做比较，一边比较一边移动比较过的元素，直到找到第一个比 12 小的元素 11 时停止比较，此时 31 对应的索引 1 则是 12 需要插入的位置。 　　1.初始： [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] 　　2.3.第一趟： [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] (无移动的元素) 　　4.5.第二趟： [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] ( 31 向后移动) 　　6.7.第三趟： [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] ( 11, 12, 31 皆向后移动) 　　8.9.第四趟： [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] (无移动的元素) 　　10.11.第五趟： [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] ( 31, 34 向后移动) 　　12.13.第六趟： [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] ( 30, 31, 34 向后移动) 　　14.15.第七趟： [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] (无移动的元素) 　　16.17.第八趟： [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] ( 38 向后移动) 　　18.19.第九趟： [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] ( 26, 30, 31, 34, 36, 38 向后移动) 　　插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,这种极端情况下，插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) . 　　实现代码： 　　1./** 　　2. * Insertion Sorting 　　3. */ 　　4.INSERTION(new Sortable() { 　　5. public 　　6. int len = array.length; 　　7. for (int i = 1; i < len; i++) { 　　8. T toInsert = array[i]; 　　9. int j = i; 　　10. for (; j >

0; jmurf -) {

11. Int compare = array [j-1] .compareto (toInsert)

12. If (compare = = 0 | | compare

< 0 == ascend) { 　　13. break; 　　14. } 　　15. array[j] = array[j - 1]; 　　16. } 　　17. 　　18. array[j] = toInsert; 　　19. } 　　20. } 　　21.}) 　　3、Java排序算法之冒泡排序 　　冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层 for 循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素"浮"到最前面，所以称之为冒泡排序。 　　照例举个简单的实例吧： 　　1. 　　2. 　　3.初始状态： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23] 　　4. 　　5.内层第一趟： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] ( 9th [23]8th [38 ) 　　6. 　　7.内层第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] ( 8th [23]7th [29] ) 　　8. 　　9.内层第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] ( 7th [23]6th [31] ) 　　10. 　　11.内层第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] ( 7 、 23 都位于正确的顺序，无需交换) 　　12. 　　13.内层第五趟： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] ( 5th [7]4th [36] ) 　　14. 　　15.内层第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] ( 4th [7]3rd [39] ) 　　16. 　　17.内层第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] ( 3rd [7]2nd [26] ) 　　18. 　　19.内层第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] ( 2nd [7]1st [19] ) 　　20. 　　21.内层第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] ( 1st [7]0th [24] ) 　　22. 　　23.…… 　　其实冒泡排序跟选择排序比较相像，比较次数一样，都为 n * (n + 1) / 2 ,但是冒泡排序在挑选最小值的过程中会进行额外的交换(冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换)，所以在我看来，选择排序属于冒泡排序的改进版。 　　实现代码： 　　1./** 　　2. * Bubble Sorting, it's very similar with Insertion Sorting 　　3. */ 　　4.BUBBLE(new Sortable() { 　　5. public 　　6. int length = array.length; 　　7. int lastExchangedIdx = 0; 　　8. for (int i = 0; i < length; i++) { 　　9. // mark the flag to identity whether exchange happened to false 　　10. boolean isExchanged = false; 　　11. // last compare and exchange happened before reaching index i 　　12. int currOrderedIdx = lastExchangedIdx >

I? LastExchangedIdx: i

13. For (int j = length-1; j > currOrderedIdx; Jmuri -) {

14. Int compare = array [j-1] .compareto (Array [j])

15. If (compare! = 0 & & compare > 0 = = ascend) {

16. Exchange (array, j-1, j)

17. IsExchanged = true

18. LastExchangedIdx = j

19.}

20.}

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

twenty-two。 If (isExchanged = = false) {

23. Break

24. }

25. }

twenty-six。 }

27.})

4. Hill sorting of Java sorting algorithm

Hill sorting was born because insert sorting encounters the problem of moving too many elements when dealing with large arrays. Hill's idea is to divide a large array into several small arrays, which are divided by gap, such as arrays [1, 2, 3, 4, 5, 6, 7, 8]. If they are divided by gap = 2, they can be divided into [1, 3, 5, 7] and [2, 4, 6, 8] arrays. For example, if gap = 3, the array is divided into: [1, 4, 7], [2, 5, 8], [3, 6]), and then insert and sort the divided array respectively. After each subarray is sorted, the gap value is reduced to repeat the steps before, until gap = 1, that is, the whole array is inserted and sorted. At this time, the array is basically sorted quickly. So the elements that need to be moved will be very small, which solves the problem of inserting sorting with a large number of moves when dealing with large arrays.

For specific examples, please refer to the insertion sort.

Hill sort is an improved version of insert sort, which is of great help to improve efficiency when the amount of data is large, and it is recommended to use insert sort directly when the amount of data is small. Implementation code:

1.According to *

2. * Shell Sorting

3. * /

4.SHELL (new Sortable () {

5. Public

6. Int length = array.length

7. Int gap = 1

8.

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

10. While (gap

< length / 3) { 　　11. gap = gap * 3 + 1; 　　12. } 　　13. 　　14. while (gap >

= 1) {

15. For (int I = gap; I

< length; i++) { 　　16. T next = array[i]; 　　17. int j = i; 　　18. while (j >

= gap) {

19. Int compare = array [j-gap] .compareto (next)

20. / / already find its position

21. If (compare = = 0 | | compare

< 0 == ascend) { 　　22. break; 　　23. } 　　24. 　　25. array[j] = array[j - gap]; 　　26. j -= gap; 　　27. } 　　28. if (j != i) { 　　29. array[j] = next; 　　30. } 　　31. } 　　32. gap /= 3; 　　33. } 　　34. 　　35. } 　　36.}) 　　5、Java排序算法之归并排序 　　归并排序采用的是递归来实现，属于"分而治之",将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组"归并"到一起，归并排序最重要的也就是这个"归并"的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] (虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ,我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分)那么需要的额外数组的长度为 4 + 4 = 8 .归并的过程可以简要地概括为如下： 　　1)将两个子数组中的元素复制到新数组 copiedArray 中，以前面提到的例子为例，则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ; 　　2)设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为 leftIdx 和 rightIdx ,则 leftIdx = 0 (对应 copiedArray 中的第一个元素 [3] )， rightIdx = 4 (对应 copiedArray 中的第五个元素 [1] ); 　　3)比较 leftIdx 和 rightIdx 指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置 i ,赋值完毕后分别对参与赋值的这两个索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。 　　下面给个归并的具体实例： 　　1.第一趟： 　　2.3.辅助数组 [21 , 28, 39 | 35, 38] (数组被拆分为左右两个子数组，以 | 分隔开) 　　4.5.[21 , , , , ] (第一次 21 与 35 比较 , 左边子数组胜出， leftIdx = 0 , i = 0 ) 　　6.7.第二趟： 　　8.9.辅助数组 [21, 28 , 39 | 35, 38] 　　10.11.[21 , 28, , , ] (第二次 28 与 35 比较，左边子数组胜出， leftIdx = 1 , i = 1 ) 　　12.13.第三趟： [21, 28, 39 | 35 , 38] 　　14.15.[21 , 28 , 35, , ] (第三次 39 与 35 比较，右边子数组胜出， rightIdx = 0 , i = 2 ) 　　16.17.第四趟： [21, 28, 39 | 35, 38 ] 　　18.19.[21 , 28 , 35 , 38, ] (第四次 39 与 38 比较，右边子数组胜出， rightIdx = 1 , i = 3 ) 　　20.21.第五趟： [21, 28, 39 | 35, 38] 　　22.23.[21 , 28 , 35 , 38 , 39] (第五次时右边子数组已复制完，无需比较 leftIdx = 2 , i = 4 ) 　　以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分(每次一分为二)直到分为长度为 1 的小数组为止，长度为 1 时数组已经不用排序了。在这之后再逆序(由于采用递归)依次对这些数组进行归并操作，直到最后一次归并长度为 n / 2 的子数组，归并完成之后数组排序也完成。 　　归并排序需要的额外空间是所有排序中最多的，每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判断)，时间复杂度比较难估，这里小弟也忘记是多少了(囧)。 　　实现代码： 　　1./** 　　2. * Merge sorting 　　3. */ 　　4.MERGE(new Sortable() { 　　5. public 　　6. this.sort(array, 0, array.length - 1, ascend); 　　7. } 　　8.9. private 　　10. // OPTIMIZE ONE 　　11. // if the substring's length is less than 20, 　　12. // use insertion sort to reduce recursive invocation 　　13. if (hi - lo < 20) { 　　14. for (int i = lo + 1; i lo; j--) { 　　18. int compare = array[j - 1].compareTo(toInsert); 　　19. if (compare == 0 || compare < 0 == ascend) { 　　20. break; 　　21. } 　　22. array[j] = array[j - 1]; 　　23. } 　　24.25. array[j] = toInsert; 　　26. } 　　27.28. return; 　　29. } 　　30.31. int mid = lo + (hi - lo) / 2; 　　32. sort(array, lo, mid, ascend); 　　33. sort(array, mid + 1, hi, ascend); 　　34. merge(array, lo, mid, hi, ascend); 　　35. } 　　36.37. private 　　38. // OPTIMIZE TWO 　　39. // if it is already in right order, skip this merge 　　40. // since there's no need to do so 　　41. int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]); 　　42. if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) { 　　43. return; 　　44. } 　　45.46. @SuppressWarnings("unchecked") 　　47. T[] arrayCopy = (T[]) new Comparable[hi - lo + 1]; 　　48. System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length); 　　49.50. int lowIdx = 0; 　　51. int highIdx = mid - lo + 1; 　　52.53. for (int i = lo; i mid - lo) { 　　55. // left sub array exhausted 　　56. array[i] = arrayCopy[highIdx++]; 　　57. } else if (highIdx >

Hi-lo) {

fifty-eight。 / / right sub array exhausted

fifty-nine。 Array [I] = arrayCopy [lowIdx++]

sixty。 } else if (arrayCopy [lowIdx] .compareto (arrayCopy [highIdx]) < 0 = = ascend) {

sixty-one。 Array [I] = arrayCopy [lowIdx++]

sixty-two。 } else {

sixty-three。 Array [I] = arrayCopy [highIdx++]

sixty-four。 }

sixty-five。 }

sixty-six。 }

67.})

These are all the contents of the article "how to implement the sorting algorithm in Java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.