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

This article mainly explains "what is the principle of the Java sorting algorithm". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is the principle of the Java sorting algorithm".

1. Analysis of sorting algorithm

In addition to learning its algorithm principle and code implementation, the most important thing is to learn how to evaluate and analyze a sorting algorithm. The analysis of a sorting algorithm usually starts from the following points.

1.1. Execution efficiency

The analysis of executive efficiency is generally measured from these aspects:

Best-case, worst-case, average

In addition to the time complexity in these three cases, it is also necessary to give the corresponding raw data to be sorted.

Coefficient, constant, low order of time complexity

The large O time complexity reflects an increasing trend of algorithm time with n, for example, O (n ^ 2) indicates that the algorithm time increases with n, showing a square growth trend. In this case, coefficients, constants, low order and so on are often ignored. However, in the actual development process, the sorted data is often 10, 100, 1000 such small-scale data, so when comparing the same-order complexity of sorting algorithms, these coefficients, constants, low-order can not be omitted.

Number of comparisons and times of exchange (or movement)

In the algorithm based on comparison, operations such as element comparison and element exchange are involved. Therefore, when analyzing, we also need to analyze the number of comparisons and exchanges.

1.2. Memory consumption

Memory consumption is actually space complexity. For the sorting algorithm, if the space complexity of the sorting algorithm is O (1), then the sorting algorithm is also called in-situ sorting.

1.3. Stability.

What is it

Stability means that there are elements with equal values in the sequence to be sorted. After sorting, the order of equal elements is the same as before sorting.

Why

Most of the principles of sorting and the implementation of sorting are integers, but in the actual development process, it is often a group of objects to be sorted, and we just sort by a certain key in the object.

For example, an object has two properties, the order time and the order amount. By the time they are stored in the database, these objects have been stored in chronological order. But now we want to take the order amount as the main key, when the order amount is the same, the following time is key. Then, after using a stable algorithm, you only need to sort the order once according to the amount of the order. For example, there are three data, the first data is the order time, and the second data is the order amount: (20200515, 20), (20200516, 10), (20200517, 30), (20200518, 20). After using a stable algorithm, the sorting is as follows: (20200516, 10), (20200515, 20), (20200518, 20), (20200517, 30) can be found that the order is sorted by order time when the order amount is the same.

two。 The classical common sorting algorithm 2.1. Bubbling sort

Bubble sorting is to compare two adjacent elements in turn, and then exchange elements without meeting the size condition. A bubble sort will sort at least one element (the sorted area of the element is equivalent to the ordered area, so the bubble sort is equivalent to dividing the array to be sorted into two sorted and unsorted intervals). Therefore, in order to sort the n elements, you need to sort the bubbles for the first time (not on the nth trip).

The bubble sort is used to sort such a set of data 4, 5, 6, 3, 2, 1, from small to large. The first sort is as follows:

As you can see, after a bubble operation, the element 6 has been stored in the correct location, and to complete the sorting of all the data, we only need to sort the bubbles five times. The figure shows the sixth time, but the sixth time is not really necessary.

2.1.1. Optimize

In the process of using bubbling sorting, if there is no exchange between elements during a bubbling process, it means that it has been sorted and can simply exit and no longer perform subsequent bubbling operations.

2.1.2. Realize

The following bubble sorting implementation is optimized:

/ * * Bubble sort: * take ascending order as an example, that is, compare two adjacent numbers, and exchange them if they are in reverse order, which is similar to bubbling; * determine the position of one number at a time, because you need to determine the number of nMuq 1 * times bubbling. * Bubble sorting is actually equivalent to dividing the entire sorted sequence into unsorted and sorted regions * / public void bubbleSort (int [] arr, int len) {/ / len-1 for (int j = 0; j)

< len-1; j++) {int sortedFlag = 0;// 一趟冒泡for (int i = 0; i < len-1-j; i++) {if (arr[i] >

Arr [I]) {int temp = arr [I]; arr [I] = arr [I]; arr [I] = temp; sortedFlag = 1;}} / / this sequence does not occur, indicating that if (0 = = sortedFlag) {break;} 2.1.3 has been ordered. Algorithm analysis

Bubble sort is in-situ sort. Because the bubbling process only involves the exchange of adjacent data, it is equivalent to only opening up a memory space to complete the adjacent data exchange.

Bubble sorting is a stable sorting algorithm without swapping when the elements are of equal size.

The time complexity of bubbling sorting.

When the elements are already sorted, the best-case time complexity is O (n). Because you only need to run once, and then you find that it is already in order, then you can quit.

When the elements happen to be arranged in reverse order, then one sort needs to be done, and the worst-case complexity is O (n ^ 2).

In general, the average time complexity is O (n ^ 2). The method of order degree and reverse degree is used to calculate the time complexity. there are mainly two operations in the process of bubble sorting: comparison and exchange. With each exchange, the degree of order increases by one, so the number of times the degree of order increases is the number of exchanges. And because the order degree needs to increase the number of times is equal to the reverse order degree, so the exchange number is actually equal to the reverse order degree.

So when you want to bubble sort an array containing n pieces of data. In the worst case, if the degree of order is 0, then n * (nmur1) / 2 exchanges are required; at best, no exchanges are needed. We take the intermediate value n * (nmur1) / 4 to represent the average case in which the initial ordering degree is neither very high nor very low. Since n * (nmur1) / 4 exchanges are required on average, there must be more comparison operations than swap operations. But the upper limit of time complexity is O (n ^ 2), so the average time complexity is O (n ^ 2).

★

Although this method is not strict, it is very practical. The main reason is that the quantitative analysis of probability is too complex and impractical. (PS: that's what I like.)

"2.2. Insert sort

* * insert sorting divides the elements in the array into two intervals: the sorted interval and the unsorted interval (at the beginning, the elements of the sorted interval are only the first element of the array). Insert sorting is to insert the elements of the unsorted interval into the sorted interval (you need to keep the sorted interval in order). In the end, the entire array is sorted, that is, sorted. * * if you want to sort n elements, then the number of elements in the unsorted interval is nMel 1, so you need to insert nMel once. The search for the insertion position can traverse the sorted interval from end to end or through the sorted interval from beginning to end.

As shown in the figure, suppose you want to sort 4, 5, 6, 1, 3, and 2. The orange-red on the left indicates the sorted interval, and the yellow on the right indicates the unsorted interval. The entire insertion sorting process is as follows

2.2.1. Optimize

In the way of Hill sorting.

* * use the Sentinel mechanism. * * for example, the array to be sorted is [2, 1, 3, 4]. In order to use the Sentinel mechanism, the first bit of the array needs to be empty, and then all the elements of the array need to be moved back one grid to [0, 2, 1, 3, 4]. Then the position of array 0 is used to store the data to be inserted, so there is one less judgment condition. Instead of judging j > = 0, you only need to use the condition of arr [j] > arr [0]. Because even if you traverse to the position where the subscript is 0, because the value at 0 is the same as the value to be inserted, the loop will exit and there will be no problem of crossing the line.

2.2.2. Realize

The way to find the insertion position here is to traverse the sorted interval from end to end, without the use of sentinels.

/ * insert sort: * insert sort is also equivalent to dividing the sorted sequence into sorted and unsorted regions; * each sort inserts an element selected from the unsorted area into the sorted appropriate location; * assuming that the first element belongs to the sorted area, then you also need to insert len-1 rows; * / public void insertSort (int [] arr, int len) {/ / len-1 for (int I = 1; I)

< len; i++) {// 一趟排序int temp = arr[i];int j;for (j = i-1; j >

= 0; temp -) {if (arr [j] > temp) {arr [jacks 1] = arr [j];} else {break;}} arr [jacks 1] = temp;}} 2.2.3. Algorithm analysis

Insertion sorting is an in-place algorithm. Because you only need to open up an additional storage space for temporary storage elements.

When you compare elements and find that they are equal, they are inserted after the equal elements, and this is the stable sort. That is to say, only when the element in the ordered interval is larger than the element to be inserted will it be moved to the later position, and if it is not greater than (less than or equal to), it will be inserted directly.

The time complexity of the insertion sort.

If the data to be sorted is ordered, there is no need to move any data. Then the best time complexity is O (n) to find the insertion position in the sorted interval from end to end.

The data to be sorted is in reverse order, and it needs to move 1, 2, 3,..., and nMel data in turn, so the worst time complexity is O (n ^ 2).

The average time complexity is O (n ^ 2). So the average time to insert a data into an ordered array is O (n), then you need to insert 1 data, so the average time complexity is O (n ^ 2).

★

The best case is that if you insert an element at the end of the array, you don't need to move the array, and the time complexity is O (1). If you insert data at the beginning of the array, then all the data needs to be moved back one bit in turn, so the time complexity is O (n). If you insert it into the k position of the array, then the element in this part of the knewn needs to be moved back one bit. So the average time complexity of insertion at this time is O (n).

"2.2.4. VS bubble sort

The time complexity of bubble sort and insert sort is O (n ^ 2), which is stable in place. And no matter how much bubbling sorting is optimized, the number of element exchanges is a fixed value, which is the reverse order of the original data. The insertion sort is the same, and no matter how optimized, the number of element movements is equal to the reverse order of the original data. However, from the point of view of the implementation of the code, the data exchange of bubble sort is more complex than the data movement of insert sort, bubble sort needs three assignment operations, while insert sort needs only one assignment operation. So, although both bubble sort and insert sort are O (n ^ 2) in terms of time complexity, if you want to maximize performance, insert sort is the first choice. In fact, the main starting point of this point analysis is that under the same order complexity, we need to consider coefficients, constants, low order and so on.

2.3. Select sort

The selection sort is also divided into the sorted interval and the unsorted interval (there is no data in the sorted interval at the beginning). Each selection sort will find the lowest value in the unsorted interval (from small to large) to the end of the sorted interval.

2.3.1. Implement / * * Select sort: * Select sort divides the sequence to be sorted into unsorted and sorted areas; * the whole unsorted sequence is unsorted in the first sorting; * each sorting is actually a maximum value for the unsorted area and put it in the sorted area. * just take a trip to len-1 * / public void switchSort (int [] arr, int len) {/ / len-1, 0muri is the sorted area for (int I = 0; I)

< len-1; i++) {int minIndex = i;for (int j = i+1; j < len; j++) {if (arr[j] < arr[minIndex]) { minIndex = j; } }if (minIndex != i) {int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }}2.3.2. 算法分析 选择排序是原地排序，因为只需要用来存储最小值所处位置的额外空间和交换时所需的额外空间。 选择排序不是一个稳定的算法。因为选择排序是从未排序区间中找一个最小值，并且和前面的元素交换位置，这会破坏稳定性。比如 1、5、5、2 这样一组数据中，使用排序算法的话。当找到 2 为 5、5、2 当前未排序区间最小的元素时，2 会与第一个 5 交换位置，那么两个 5 的顺序就变了，就破坏了稳定性。 时间复杂度分析。最好、最坏、平均都是 O(n^2)，因为无论待排序数组情况怎么样，就算是已经有序了，都是需要依次遍历完未排序区间，需要比较的次数依次是 n-1、n-2，所以时间复杂度是 O(n^2)。 2.4. 归并排序（Merge Sort） **归并排序的核心思想就是我要对一个数组进行排序：首先将数组分成前后两部分，然后对两部分分别进行排序，排序好之后再将两部分合在一起，那整个数组就是有序的了。对于分出的两部分可以采用相同的方式进行排序。**这个思想就是分治的思想，就是先将大问题分解成小的子问题来解决，子问题解决之后，大问题也就解决了。而对于子问题的求解也是一样的套路。这个套路有点类似于递归的方式，所以分治算法一般使用递归来实现。分治是一种解决问题的处理思想，而递归是一种实现它的编程方法。 2.4.1. 实现 下面使用递归的方式来实现归并排序。递归的递推公式是：merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))，终止条件是 p>

= r, no more recursion. The whole implementation process is to first call the _ _ mergeSort () function to sort the two parts separately, and then merge the two sorted parts using the array merge method.

/ * * merge sort * / public void mergeSort (int [] arr, int len) {_ _ mergerSort (arr, 0, len-1);} private void _ mergerSort (int [] arr, int begin, int end) {if (begin = = end) {return;} _ mergerSort (arr, begin, (begin+end) / 2); _ mergerSort (arr, (begin+end) / 2 + 1, end); merge (arr, begin, end); return } private void merge (int [] arr, int begin, int end) {int [] copyArr = new int [end-begin+1]; System.arraycopy (arr, begin, copyArr, 0, end-begin+1); int mid = (end-begin+1) / 2 System.arraycopy int I = 0; / / begin-mid pointer int j = mid; / / mid-end pointer int count = begin; / / pointer while (I maxVal) {maxVal = arr [I] of the merged array }} / / confirm the range represented by each barrel bucketCount = (maxVal-minVal + 1)

< bucketCount ? (maxVal - minVal + 1) : bucketCount;int bucketSize = (maxVal - minVal + 1) / bucketCount; bucketCount = (maxVal - minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1;int[][] buckets = new int[bucketCount][bucketSize];int[] indexArr = new int[bucketCount]; // 数组位置记录// 将数据依次放入桶中for (int i = 0; i < len; i++) {int bucketIndex = (arr[i] - minVal) / bucketSize;if (indexArr[bucketIndex] == buckets[bucketIndex].length) { expandCapacity(buckets, bucketIndex); } buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i]; }// 桶内排序for (int i = 0; i < bucketCount; ++i) {if (indexArr[i] != 0) { quickSort(buckets[i], 0, indexArr[i] - 1); } }// 桶内数据依次取出int index = 0;for (int i = 0; i < bucketCount; ++i) {for (int j = 0; j < indexArr[i]; ++j) { arr[index++] = buckets[i][j]; } }// 打印for (int i = 0; i < len; ++i) { System.out.print(arr[i] + ">

);} System.out.println ();} / expand the array public void expandCapacity (int [] [] buckets, int bucketIndex) {int [] newArr = new int [bucketIndex] .length * 2]; System.arraycopy (buckets [bucketIndex], 0, newArr, 0, buckets.length); buckets [bucketIndex] = newArr;} 2.7.2. Algorithm analysis

The best time complexity is O (n), the worst time complexity is O (nlogn), and the average time complexity is O (n).

If the data to be sorted is n, divide the data evenly into m buckets, each bucket will have k=n/m elements. Each bucket uses a quick sort with a time complexity of O (k.logk). The time complexity of m barrels is O (m*k*logk), and the time complexity of conversion is O (n*log (n n*log)). When the number of buckets m is close to the number of data n, log is a very small constant, and the time complexity of bucket sorting is close to O (n).

If the data is divided into buckets, the data in each bucket is very uneven, for example, a bucket contains all the data, then the bucket sorting will be reduced to the O (nlogn) sorting algorithm.

The average time complexity here is O (n) without strict calculation, but only in a rough way. Because bucket sorting in most cases, the data can be roughly evenly divided, and it is rare that all the data is in one bucket.

Non-local algorithm

Because in the process of bucket sorting, the space complexity of creating m buckets is definitely not O (1). In the case of quick sort in bucket, the space complexity of bucket sort should be O (n).

The stability of bucket sorting mainly depends on two pieces: 1. Whether to put the data in the order when putting the data into the bucket; 2. The sorting algorithm used in the bucket. So if the data is put into the bucket in order, and a stable sorting algorithm is used in the bucket, then the whole bucket sorting is stable. Since it can be stable, it is generally stable.

2.7.3. Summary

Bucket sorting is very demanding on the data to be sorted.

First, the data to be sorted needs to be easily divided into m buckets. Moreover, there is a natural size order between buckets, so that after the data in each bucket is sorted, the data between buckets no longer need to be sorted.

Secondly, the distribution of data in each barrel is relatively uniform. If the data is divided into buckets, the data in each bucket is very uneven, for example, a bucket contains all the data, then the bucket sorting will be reduced to the O (nlogn) sorting algorithm.

* * Bucket sorting is suitable for external sorting. * * for example, the data to be sorted has 10GB order data, but there are only a few hundred MB in memory, so it is impossible to load all 10GB data into memory at once. At this time, you can first scan the order data of 10GB, and then determine the scope of the order data. For example, if the range of the order is between 10 and 100,000 yuan, then all the data can be divided into 100 barrels. Then scan the order data of 10GB in turn, store the order within 1000 yuan to the first barrel, and the order data within 1001to 2000 yuan to the second barrel, each barrel corresponds to a file, and the name of the file is numbered in order such as 00,01 according to the size of the amount range, that is, the data of the first barrel is output to file 00.

Ideally, if the order data is evenly distributed, the data of each file is about 100MB. The data of these files are read into memory in turn, sorted by quick sorting, and then stored back to the file. Finally, as long as the data in the file is read in the file order and written to a file, the data in the file is sorted.

However, the order data is not necessarily evenly distributed. After the partition, there may still be larger files, so continue to divide. For example, if the order amount is more than 1 to 1000 yuan, then this range will continue to be divided into 10 small sections, 1: 100, 101: 200 and so on. If the partition is still large, continue the partition until all the files can be read into memory.

★

External sorting means that the data is stored on disk, the amount of data is relatively large, and the memory is limited, so it is impossible to load all the data into memory.

"2.8. Count sort

Counting sorting is similar to bucket sorting, it can be said that counting sorting is actually a special case of bucket sorting. * * when the range of n pieces of data to be sorted is not large, for example, the maximum value is K, the data can be divided into K buckets, and the data values in each bucket are the same. * * this saves the time of sorting in the bucket. It can be said that the difference between counting sort and bucket sort lies in the size and granularity of the bucket.

Let's take a look at the process of counting and sorting by giving an example. Suppose there are eight data in array A with values between 0 and 5: 2, 5, 3, 0, 2, 3, 0, 3.

First, use the array C [6] of size 6 to store the number of each value, with the subscript corresponding to the specific value. Thus, it is obtained that the case of C [6] is 2, 0, 2, 3, 0, 1.

So, the number of data with a value of 3 points is 3, and the number of data less than 3 points is 4, so the data with a value of 3 should be located at 4, 5, 6 in the ordered array R. In order to quickly calculate the position, the array C [6] is changed and the number of data less than or equal to the value k is stored in C [k]. The changed array is 2, 2, 4, 7, 7, 8.

Then we scan data A from back to front (from back to front for stability). For example, when we scan to 3, we take the value of subscript 3 from data C, which is 7 (that is, so far, there are 7 data with values less than or equal to 3), so 3 is the seventh element in the array R, that is, the subscript is 6. Of course, after 3 is put into the array R, C [3] will be subtracted by 1 and become 6, indicating that there are 6 data less than or equal to 3 in the unsorted data.

And so on, when the second data with a value of 3 is scanned, the data is placed in R with the subscript 5. When the entire array An is scanned, the data in array R is arranged in order from small to large.

2.8.1. Implement / * * count sorting, temporarily can only handle integers (including integers and negative numbers) * @ param arr * @ param len * / public void countingSort (int [] arr, int len) {/ / determine the range int minVal = arr [0]; int maxVal = arr [0]; for (int I = 1; I)

< len; ++i) {if (maxVal < arr[i]) { maxVal = arr[i]; } else if (arr[i] < minVal) { minVal = arr[i]; } }// 对数据进行处理for (int i = 0; i < len; ++i) { arr[i] = arr[i] - minVal; } maxVal = maxVal - minVal;// 遍历数据数组，求得计数数组的个数int[] count = new int[maxVal + 1];for (int i = 0; i < len; ++i) { count[arr[i]] ++; } printAll(count, maxVal + 1);// 对计数数组进行优化for (int i = 1; i < maxVal + 1; ++i) { count[i] = count[i - 1] + count[i]; } printAll(count, maxVal + 1);// 进行排序，从后往前遍历（为了稳定）int[] sort = new int[len];for (int i = len - 1; i >

= 0;-- I) {sort [count [arr]-1] = arr [I] + minVal; count [arr [I]] -;} printAll (sort, len);} 2.8.2. Algorithm analysis

Non-local algorithm

Counting sorting is the same as a special case of bucket sorting. Counting sorting requires an additional k pieces of memory space and n new memory spaces to store the sorted array.

Stable algorithm

As mentioned earlier, if you traverse from back to front, it is a stable algorithm.

Time complexity

The best, worst, and average time complexity are all the same, which is O (nymk) and k is the data range. As you can see from the implementation of the code, you have to loop the same number of times regardless of the situation of the array to be arranged.

2.8.3. Summary

Counting sorting can only be used in scenarios where the data range is small, and if the data range k is much larger than the data n to be sorted, it is not suitable for counting sorting.

Counting sorting can only sort non-negative integers directly, and if the data to be sorted is of other types, it needs to be converted to non-negative integers without changing the relative size. For example, when the number to be sorted is accurate to one decimal place, you need to multiply the values of all the data by 10 and convert them to integers. For example, if there is a negative number in the sorted data, the range of the data is [- 1000], then you need to add 1000 to each data and convert it to a non-negative integer.

2.9. Cardinality sort

Both bucket sort and count sort are suitable for situations where the range is not particularly large (note that it is a range), but the range of bucket sort can be slightly larger than the range of count sort. If the range of data is very large, such as for mobile phone numbers, bucket sorting and technical sorting are obviously not suitable, because the number of buckets required is also very large. At this point, you can use cardinality sorting. * * the idea of cardinality sorting is to split the sorted data into bits and compare them bit by bit. * * for example, the mobile phone number can be sorted from back to front, sorted first according to the last digit of the mobile number, then sorted according to the second-to-last digit, and so on. When you reorder according to the first place, the whole sort is complete.

It should be noted that * *, according to each sort process needs to be stable, because if the latter sort is unstable, the previous sort result will fall short of success. For example, the first ranking of bits is 21, 11, 42, 22, 62, with 21 in front of 22; if the second ranking of ten digits is unstable, 22 may be ahead of 21. Then the whole sort is wrong, and the ranking of individual bits is in vain.

Here is an example of a string. The whole process of cardinality sorting is shown in the following figure:

2.9.1. Implement / * * cardinality sorting * @ param arr * @ param len * / public void radixSort (int [] arr, int len, int bitCount) {int exp = 1 for (int I = 0; I)

< bitCount; ++i) { countingSort(arr, len, exp); exp = exp * 10; }}public int getBit(int value, int exp) {return (value / exp) % 10;}/** * 计数排序，暂时只能处理整数（包括整数和负数） * @param arr * @param len */public void countingSort(int[] arr, int len, int exp) {// 确定范围int maxVal = getBit(arr[0], exp);for (int i = 1; i < len; ++i) {if (maxVal < getBit(arr[i], exp)) { maxVal = getBit(arr[i], exp); } }// 遍历数据数组，求得计数数组的个数int[] count = new int[maxVal + 1];for (int i = 0; i < len; ++i) { count[getBit(arr[i], exp)] ++; }// 对计数数组进行优化for (int i = 1; i < maxVal + 1; ++i) { count[i] = count[i - 1] + count[i]; }// 进行排序，从后往前遍历（为了稳定）int[] sort = new int[len];for (int i = len - 1; i >

= 0;-- I) {sort [arr [I], exp)]-1] = arr [I]; count [getBit (arr [I], exp)] -;} System.arraycopy (sort, 0, arr, 0, len); printAll (sort, len);} 2.9.2. Algorithm analysis

Non-local algorithm

Whether or not the in-place algorithm actually depends on the algorithm used to sort for each bit. In order to ensure the time complexity of cardinality sorting and the stability of each bit, counting sorting is generally used, and counting sorting is a non-local algorithm, so cardinality sorting can be regarded as non-local sorting.

Stable algorithm

Because cardinality sorting needs to ensure that each bit is stable when sorting, the whole cardinality sorting is stable.

The time complexity is O (kn), where k is the number of bits in the array.

The best, worst and average time complexity is all O (n). Because no matter what happens to the array to be sorted, the cardinality sort is actually traversing every bit, sorting each bit. If count sort is used in each bit sort process, the time complexity is O (n). If there are k bits, then k bucket sort or count sort is required. Therefore, the total time complexity is O (kn). When k is small, for example, the mobile phone number is 11 digits, then the time complexity of cardinality sorting is similar to O (n). You can also see it in the code.

2.9.3. Summary

One of the requirements of cardinality sorting is that the sorted data should be of equal length. When unequal length of time can be added before or after 0, such as string sorting, you can add 0 after, because all the letters in the ASCII code are greater than "0", so the complement "0" will not affect the original size sorting.

Another requirement of cardinality sorting is that the data can be divided into independent "bits" to compare, and there is a progressive relationship between bits: if the high bits of a data are larger than b data, then the remaining low bits do not have to be compared.

In addition, the data range of each bit should not be too large, and the linear sorting algorithm should be used to sort, otherwise, the cardinality sorting time complexity can not reach O (n).

3. Sorting function

Almost all programming languages provide sorting functions, such as qsort () in C, sort () / stable_sort () in C++ STL, and Collections.sort () in Java. These sorting functions do not use only one sorting algorithm, but a combination of multiple sorting algorithms. Of course, the main sorting algorithms used are O (nlogn).

The qsort () sort function of glibc. Qsort () gives priority to the merge sorting algorithm. Quick sort is used when the amount of sorted data is large. When using the sorting algorithm, it will also be optimized, such as using the "three-number middle method" and manually implementing a stack on the heap to simulate recursion. In the process of fast sorting, insert sorting is used if the number of elements in the sorted interval is less than or equal to 4. In addition, the Sentinel mechanism is also used in the insertion sorting, which reduces one judgment.

★

Algorithms with O (n ^ 2) time complexity in front of small-scale data do not necessarily take longer than O (nlogn) algorithms. Mainly because the time complexity will remove the coefficient and the low order.

"

The Array.sort () sort function, using the TimSort algorithm. TimSort algorithm is a hybrid sorting algorithm of merging algorithm and insertion sorting algorithm. The basic working process is:

During the whole sorting process, the segmented selection strategy can guarantee the time complexity of O (nlogn). TimSort mainly makes use of the characteristics that some fragments in the sequence to be arranged may have been basically ordered. After that, the insertion algorithm is used to merge the small fragments into large fragments. Finally, the sorting work is completed by merging and sorting.

Scan the array to determine the monotonous ascending segment and the monotonous descending segment, and the strictly descending segment will be reversed.

The minimum basic fragment length is defined, and the monotonous fragments that are not satisfied with the length are formed by insertion sorting (that is, the length is greater than or equal to the required minimum basic fragment length).

Merge some adjacent fragments repeatedly, and avoid merging segments with large differences in length until the whole sequence is completed.

4. Additional knowledge 4.1. Order degree, reverse order degree

In the case of order from small to large, the degree of order is the number of element pairs of ordered relations in the array, as shown in the following mathematical formula.

If I

< j，那么 a[i] < a[j] 比如 2、4、3、1、5、6 这组数据的有序度是 11；倒序排列的数组，有序度是 0；一个完全有序的数组，有序度为满有序度，为 n*(n-1)/2，比如1、2、3、4、5、6，有序度就是 15。 逆序度的定义正好跟有序度的定义相反 如果 i < j，那么 a[i] >

A [j]

The reverse order degree, order degree and full order degree satisfy the following formula

Reverse degree = full ordered degree-ordered degree

The process of sorting is actually the process of reducing the degree of reverse order and increasing the degree of order. if the sorting sequence reaches the full degree of order, then the sequence is ordered.

5. Summary

Bubble sorting and selection sorting may stay at the theoretical level, but there are not many practical applications, but insert sorting is still very useful. Insert sorting is used when some sorting algorithms are optimized. For example, insert sort will be selected first when the amount of sorting data is small.

The time complexity of bubbling, selection and insertion is generally calculated according to n ^ 2. * * and all three have a common feature, that is, they all divide the sorted series into sorted and unsorted parts. * * the outer loop is actually adding one to the ordered part, so the outer loop is equivalent to dividing the ordered part from the unordered part. The number of outer loops is the number of data to be sorted, while the inner loop is mainly responsible for dealing with the unsorted elements.

The partition process of quick arrangement and the idea of partition are actually very useful, and they will be encountered in solving many non-sorting problems. For example, how to find the maximum value of k within the time complexity of O (n) (divide and conquer, more often partition); for example, dividing a string into alphabetic and numeric parts (actually partitioning, so you need to pay attention to the application of the partitioning process). When you see something like partitions in the future, you can think about the operation of the fast-arranging partitioning process.

Quick arrangement and merge use are the idea of divide and conquer, which can be realized by recursion. It's just that merging is a bottom-up process, a process of dealing with advanced line sub-problems, and then merging, while fast scheduling is a top-down process, in which sub-problems are partitioned first, and then sub-problems are dealt with.

The time complexity of bucket sorting, counting sorting and cardinality sorting is linear, so this kind of sorting algorithm is called linear sorting. The reason why this can achieve linear sorting, mainly because these three algorithms are not based on the comparison of sorting algorithms, do not involve the comparison between elements. But these three algorithms are very demanding on the sorted data. If the data characteristics meet the requirements of these sorting algorithms, the complexity of these algorithms can reach O (n).

Bucket sorting and counting sorting are feasible for a small range of data, and their basic idea is to divide the data into different buckets to sort.

Comparison of various algorithms

Sorting algorithm average time complexity best time complexity worst time complexity is whether in-situ sorting is stable bubbling O (n ^ 2) O (n) O (n ^ 2) √√ insert O (n ^ 2) O (n) O (n ^ 2) √√ Select O (n ^ 2) √ × merge O (nlogn) × O (n) √ Fast arrangement O (nlogn) O (nlogn) O (n ^ 2) √ × Heap sort O (nlogn) √ × bucket sort O (n) O (n) O (nlogn) × √ Counting sort O (kn) O (kn) × √ cardinality sort O (kn) O (kn) × √ Thank you for your reading The above is the content of "what is the principle of Java sorting algorithm". After the study of this article, I believe we have a deeper understanding of what the principle of Java sorting algorithm is, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.