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

This article focuses on "commonly used sorting algorithms and how to use Java to achieve", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "commonly used sorting algorithms and how to implement them with Java".

one。 Overview of directly inserting sort

Insert sort is to quickly insert a new element into an ordered array. The array to be sorted is divided into two parts, one is all the elements of the array (excluding the elements to be inserted), the other is the elements to be inserted; sort the first part first, and then insert the element. The sorting of the first part is also carried out by splitting it into two parts again. (note: due to different operations, insert sort can be divided into direct insert sort, half insert sort (also known as binary insert sort), linked list insert sort. )

Mode of realization

1. Starting with the first element, the element can be considered to have been sorted

two。 Take out the next element and scan from back to front in the sorted sequence of elements

3. If the element (sorted) is larger than the new element, move the element to the next location

4. Repeat step 3 until you find the location where the sorted element is less than or equal to the new element

5. After the new element is inserted into that location

6. Repeat the steps ② ~ ⑤

As shown in figure (1-1):

(figure: 1-1)

Java code implementation / * insert sort * * 1. Starting from the first element, the element can be considered to have been sorted * 2. Take out the next element and scan * 3 from back to front in the sorted sequence of elements. If the element (sorted) is larger than the new element, move the element to the next location * 4. Repeat step 3 until the sorted element is found to be less than or equal to the position of the new element * 5. After inserting the new element into this location, * 6. Repeat step 2: 5 * @ param arr: array to be sorted * / public static void insertionSort (int [] arr) {for (int item0; i0; Jmurb -) {if (arr [j-1] tj, tk = 1th 2. The sequence is sorted k times according to the number of incremental sequences k; 3. In each sorting, according to the corresponding incremental ti, the sequence to be arranged is divided into several subsequences of length m, and each subtable is sorted directly. Only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence.

As shown in figure (2-1):

Figure (2-1)

Java code to achieve / * Hill sorting (Wiki official version) * * 1. Select an incremental sequence T1 ~ T2, … , tk, where ti > tj,tk=1; (note the gap value of this algorithm) * 2. The sequence is sorted k times according to the number of incremental sequences k; * 3. In each sorting, according to the corresponding incremental ti, the sequence to be arranged is divided into several subsequences of length m, and each subtable is sorted directly. * only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence. * @ param arr array to be sorted * / public static void shell_sort (int [] arr) {int gap = 1, I, j, len = arr.length; int temp; while (gap)

< len / 3) gap = gap * 3 + 1; // : 1, 4, 13, 40, 121, ... for (; gap >

0; gap / = 3) {for (I = gap; I

< len; i++) { temp = arr[i]; for (j = i - gap; j >

= 0 & & arr [j] > temp; j-= gap) arr [j + gap] = arr [j]; arr [j + gap] = temp;}

The complex analysis is as follows:

Average time complexity Best case worst case Space complexity O (nlog2 n) O (1)

Summary:

It is important to choose a reasonable step size. For a better step size sequence, please refer to Wikipedia.

The reason why sorting is more efficient is that it weighs the size and ordering of subarrays. At the beginning of sorting, each subarray is very short, and after sorting, the subarray is partially ordered, both of which are suitable for insertion sorting.

Hill sort and insert sort are as follows:

Insert sorting is efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting, but insert sorting is generally inefficient because it can only move the data at a time.

Hill sorting is to first divide the whole sequence of records to be sorted into several sub-sequences for direct insertion and sorting, and then directly insert and sort all the records when the records in the whole sequence are "basically ordered".

three。 Overview of selection sorting

Selective sorting (Selection sort) is a simple and intuitive sorting algorithm. How it works is as follows. First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence, then continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all the elements are sorted.

The main advantages of selective sorting are related to data movement. If an element is in the correct final position, it will not be moved. The selection sort exchanges one pair of elements at a time, and at least one of them will be moved to its final position, so the sorting of the tables of n elements is carried out for a total of one exchange. Of all the sorting methods that rely entirely on swapping to move elements, selective sorting is a very good one.

Implementation method 1. In the unsorted sequence, find the element with the smallest keyword 2. If the smallest element is not the first element of the unsorted sequence, swap it with the first element of the unsorted sequence by 3. Repeat steps 1 or 2 until the sort is over.

As shown in figure (3-1):

Figure (3-1)

Java code implementation / * select sort * * 1. From the sequence to be sorted, find the element with the lowest keyword; * 2. If the smallest element is not the first element of the sequence to be sorted, swap it with the first element; * 3. From the remaining N-1 elements, find the element with the lowest keyword, and repeat the ① and ② steps until the sorting is over. * only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence. * @ param arr array to be sorted * / public static void selectionSort (int [] arr) {for (int I = 0; I)

< arr.length-1; i++){ int min = i; for(int j = i+1; j < arr.length; j++){ //选出之后待排序中值最小的位置 if(arr[j] < arr[min]){ min = j; } } if(min != i){ int temp = arr[min]; //交换操作 arr[min] = arr[i]; arr[i] = temp; System.out.println("Sorting: " + Arrays.toString(arr)); } }} 复杂分析如下： 平均时间复杂度最好情况最坏情况空间复杂度O(n²)O(n²)O(n²)O(1) 总结： 选择排序的简单和直观名副其实，这也造就了它"出了名的慢性子"，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。 四. 堆排序概述 堆：n个元素的序列{k1,k2,···,kn}，当且仅当满足下关系时，称之为堆。ki = k(2i+1) 把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。 实现方式 先将初始序列K[1…n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1…n-1]和有序区K[n], 且满足K[1…n-1].keys 0; i--){ max_heapify(arr, i); int temp = arr[0]; //堆顶元素(第一个元素)与Kn交换 arr[0] = arr[i-1]; arr[i-1] = temp; }}private static void max_heapify(int[] arr, int limit){ if(arr.length = 0; parentIdx--){ if(parentIdx * 2 >

= limit) {continue;} int left = parentIdx * 2; / / left child node location int right = (left + 1) > = limit? Left: (left + 1); / / right child node location. If there is no right node, the default is the left node location int maxChildId = arr [left] > = arr [right]? Left: right; if (arr [maxChildId] > arr [parentIdx]) {/ / Exchange the maximum value between the parent node and the left and right child nodes int temp = arr [parentIdx]; arr [parentIdx] = arr [maxChildId]; arr [maxChildId] = temp;}} System.out.println ("Max_Heapify:" + Arrays.toString (arr));}

The complex analysis is as follows:

Average time complexity Best case worst case Space complexity O (nlog2n) O (1)

Summary:

1. The process of setting up the heap, from length/2 to 0, the time complexity is O (n); 2. The process of adjusting the heap is to adjust along the parent and child nodes of the heap, the number of execution is the depth of the heap, and the time complexity is O (lgn); 3. The process of heap sorting is completed by step 2 of n times, and the time complexity is O (nlgn).

Summary: because of the large number of comparisons in initializing the heap in heap sorting, it is not suitable for small sequences. At the same time, because many times any subscript exchanges positions with each other, the original relative order of the same elements is destroyed, so it is an unstable sort.

five。 Overview of Bubble sorting

Bubble sorting (Bubble Sort) is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need for swapping, that is, the sequence has been sorted. The algorithm gets its name because smaller elements slowly "float" to the top of the sequence by swapping.

Implementation method 1. Compare adjacent elements. If the first is bigger than the second, exchange the two of them. two。 Do the same for each pair of adjacent elements, from the first pair to the last pair. After this step is done, the last element will be the maximum number. 3. Repeat the above steps for all elements except the last one. 4. Continue to repeat the above 1-3 steps for fewer and fewer elements at a time until there are no pairs of numbers to compare.

As shown in figure (5-1):

Figure (5-1)

Java implementation / * * Bubble sort * * 1. Compare adjacent elements. If the first is bigger than the second, exchange the two of them. * 2. Do the same for each pair of adjacent elements, from the first pair to the last pair. After this step is done, the last element will be the maximum number. * 3. Repeat the above steps for all elements except the last one. * 4. Continue to repeat the above 1-3 steps for fewer and fewer elements at a time until there are no pairs of numbers to compare. * @ param arr array to be sorted * / public static void bubbleSort (int [] arr) {for (int I = arr.length-1; I > 0; iMurt -) {/ outer loop mobile cursor for (int j = 0; j

< i; j++){ //内层循环遍历游标及之后(或之前)的元素 if(arr[j] >

Arr [juni1]) {int temp = arr [j]; arr [j] = arr [juni1]; arr [juni1] = temp; System.out.println ("Sorting:" + Arrays.toString (arr));}

The complex analysis is as follows:

Average time complexity Best case worst case Space complexity O (n ²) O (n ²) O (1)

Summary:

Bubble sort is the easiest to achieve the sort, the worst case is each need to swap, a total of need to traverse and exchange nearly n ²/ 2 times, time complexity of O (n ²), the best case is the inner loop after a traversal found that the sort is right, so out of the loop, the time complexity is O (n). On average, the time complexity is O (n ²) because only the cached temp variables in the bubble sort require memory space, so the space complexity is constant O (1).

Bubble sorting is a stable sorting algorithm because it changes the position of adjacent elements only when their size does not meet the requirements, and it does not change the relative order of the same elements.

six。 Overview of Quick sort

Quick sort is to sort n items for nlogn comparisons on average. In the worst case, you need to compare (N2) times, but this is not common. In fact, quick sorting is usually significantly faster than other nlogn algorithms because its internal loop (inner loop) can be implemented efficiently on most architectures.

Mode of realization

Quick sorting uses divide-and-conquer strategies to divide a sequence (list) into two subsequences (sub-lists). The steps are:

Pick an element from the sequence and call it a "pivot".

Reorder the series so that all elements that are smaller than the base value are placed in front of the benchmark, and all elements that are larger than the base value are placed behind the benchmark (the same number can go to either side). At the end of the partition, the datum is in the middle of the series. This is called a partition operation.

Recursively sorts the subseries of elements less than the reference value and the subseries of elements greater than the reference value. When recursive to the bottom, the size of the sequence is zero or one, that is, it has been sorted. This algorithm is bound to end, because in each iteration, it places at least one element in its last position.

As shown in figure (6-1):

Figure (6-1)

Java code to implement / * Quick sort (recursive) * * ①. Pick an element from the sequence and call it a "pivot". * ②. Reorder the series so that all elements that are smaller than the base value are placed in front of the benchmark, and all elements that are larger than the base value are placed behind the benchmark (the same number can go to either side). At the end of the partition, the datum is in the middle of the series. This is called a partition operation. * ③. Recursively sorts the subseries of elements less than the reference value and the subseries of elements greater than the reference value. * @ param arr array to be sorted * @ param low left boundary * @ param high right boundary * / public static void quickSort (int [] arr, int low, int high) {if (arr.length = high) return; int left = low; int right = high; int temp = arr [left]; / / dig pit 1: save the datum value while (left)

< right){ while(left < right && arr[right] >

= temp) {/ / pit 2: find the element smaller than the datum from back to front and insert it into the datum location pit 1 right--;} arr [left] = arr [right]; while (left

< right && arr[left] = 0){ stack.push(pivotIdx + 1); stack.push(high); } }}private static int partition(int[] arr, int low, int high){ if(arr.length = high) return -1; int l = low; int r = high; int pivot = arr[l]; //挖坑1：保存基准的值 while(l < r){ while(l < r && arr[r] >

= pivot) {/ / Hole 2: find the element smaller than the datum from back to front and insert it into the datum location pit 1; arr [l] = arr [r]; while (l < r & & arr [l] 1; int [] leftArr = Arrays.copyOfRange (arr, 0, num); int [] rightArr = Arrays.copyOfRange (arr, num, arr.length) System.out.println ("split two array:" + Arrays.toString (leftArr) + "And" + Arrays.toString (rightArr)); return mergeTwoArray (mergingSort (leftArr), mergingSort (rightArr)); / / continuously split into minimum units, and then sort and merge} private static int [] mergeTwoArray (int [] arr1, int [] arr2) {int I = 0, j = 0, k = 0; int [] result = new int [arr1.length + arr2.length] / / apply for additional space to store the merged array while (I < arr1.length & & j < arr2.length) {/ / select the smaller of the two sequences and put them in the new array if (ARR1 [I]

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.