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

This article is to share with you about the common ordering of Java data structures. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

I. the concept and classification of sorting. The basic concept of sorting

Sorting is the process of rearranging a batch of unordered records (data) into a sequence of records ordered by keywords.

Sorting is divided into internal sorting and external sorting.

If the whole sorting process can be completed without accessing out-of-memory, this kind of sorting problem is called internal sorting.

On the other hand, if the number of records participating in sorting is so large that the sorting process of the whole sequence can not be completed in memory, this kind of sorting problem is called external sorting.

The process of internal sorting is a process of gradually expanding the length of the ordered sequence of records.

two。 Stability of sorting

It is assumed that in the sequence of records to be sorted, there are multiple records with the same keyword, and if the relative order of these records remains unchanged, that is, in the original sequence, r [I] = r [j], and r [I] is before r [j], while in the sorted sequence, r [I] is still before r [j], the sorting algorithm is said to be stable; otherwise, it is called unstable.

To sum up, if a data jumps during the sorting process, it is an unstable sort; otherwise, it is a stable sort.

Time complexity: the time it takes for an algorithm to execute

Space complexity: the amount of memory required to run a program.

Second, common sort 1. Directly insert sort

The basic operation of direct insertion sorting is to insert a record into a sorted table to get a new ordered table with an increase in the number of records by 1.

Code:

Public static void insertSort (int [] array) {for (int I = 1; I)

< array.length; i++) { int tmp = array[i]; int j = i-1; for (; j >

= 0; tmp -) {if (Array [j] > tmp) {array [jink 1] = array [j];} else {break;}} / / j fallback to a place less than 0 array [jink 1] = tmp;}

Process diagram:

Time and complexity analysis: when we implement this sorting algorithm, we only rely on an auxiliary record space.

So the best case is that the elements that we need to sort are in order, for example, {1grad, 2Magne3, 4jor5, 6}, then the number of times we need to compare is actually close to the comparison of the two elements, so there is no record of movement, and the time complexity is O (n).

The worst-case scenario is that the elements are all in reverse order, such as {6pyrrine 5rec 4jre 3jpgl 1}, so they all need to be compared, and the number of moves reaches O (n ^ 2).

Stability: stability

Insert sorting, the closer the initial data is to order, the higher the time efficiency

two。 Hill ranking

Hill sorting method is also known as shrinking incremental method. The basic idea of Hill sorting method is to select an integer first, divide all the records in the file to be sorted into a group, divide all the records with distance into the same group, and sort the records in each group. Then, repeat the above grouping and sorting work. When it reaches = 1, all records are sorted within the unified group.

Hill's grouping of records is not simply "segment-by-segment", but a group of records separated by "increments".

In Yan Weimin's "data structure", it says like this:

The above words may be a little difficult to understand, let's take a look at the nature of Hill ordering by drawing.

Hill sort is a bit similar to direct insertion sort, which can be said to be an upgraded version of direct insertion sort. The difference is that Hill's comparison has become leapfrog. For example, the first sort of the following set of data.

Finally, the sorting is complete.

Let's take a look at Hill's sorting code:

Public static void shell (int [] array,int gap) {for (int I = gap; I)

< array.length; i++ ) { int tmp = array[i]; int j = i-gap; for (; j >

= 0; j-= gap) {if (Array [j] > tmp) {array [j+gap] = array [j];} else {break;}} array [j+gap] = tmp }} / / grouping public static void shellSort1 (int [] array) {int [] drr = {5mine3) 1} by 5, 3, 1; for (int I = 0; I

< drr.length; i++) { shell(array,drr[i]); } } 是不是跟直接插入排序很像？所以我们才说，希尔排序是直接插入排序的升级版。它不是随便分组后各自排序，而是将相隔某个增量gap的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高了。 所以，选取"增量"是非常关键的一步，值得一提的是，选取什么样的"增量"，目前为止尚没有一个没完美的增量序列。 复杂度分析： 时间复杂度[和增量有关系的]：O(n^1.3 - n^1.5)。 空间复杂度：O(1) 稳定性：不稳定的。 3.简单选择排序 简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第 i(1 ≤ i ≤n) 个记录交换 public static void selectSort1(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = i+1; j < array.length; j++) { //1 2 3 4 5 6 if(array[j] < array[i]) { swap(array,i,j); } } } } public static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; 有时候，我们可能不需要循环那么多次，循环一两次就有序了，如果在有序的序列中继续循环，则会造成时间的浪费。为避免这种情况，所以我们可以对代码进行稍稍改进： public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i+1; j < array.length; j++) { //找到最小值下标 if(array[j] < array[minIndex]) { minIndex = j; } } swap(array,i,minIndex); } } 复杂度分析： 时间复杂度：O(n^2) 空间复杂度：同接下介绍的冒泡排序一样，只有在两个记录交换时需要一个辅助空间，所以空间复杂度为O(1). 稳定性：稳定 4.堆排序 堆排序的基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。 我上一篇文章有详细介绍，这里就不再说了，大家感兴趣可以去了解一下。 Java数据结构之优先级队列(堆)图文详解 这里也给一下代码： public static void heapSort(int[] array) { //1、建堆 O(N) createHeap(array); int end = array.length-1; //2、交换然后调整 O(N * log N) while (end >

0) {swap (array,0,end); shiftDown (array,0,end); end--;}} public static void createHeap (int [] array) {for (int parent = (array.length-1-1) / 2; parent > = 0; parent--) {shiftDown (array,parent,array.length) }} public static void shiftDown (int [] array,int parent,int len) {int child = 2 child subscript while (child)

< len) { if(child+1 < len && array[child] < array[child+1]) { child++; } //child下标 就是左右孩子最大值的下标 if(array[child] >

Array [parent]) {swap (array,child,parent); parent = child; child = 2roomparentquestions 1;} else {break;}}

Complexity analysis:

Time complexity: O (n * log2 (n))-2 means based on 2

Space complexity: O (1)

Stability: instability

[note]

Heap sorting can only be used for sequential structures, not chained structures.

Because there are more times of comparison when the initial reactor is built, it is not suitable to use it when the number of records is small.

5. Bubbling sort

Bubble sorting is a kind of exchange sort, its basic idea is: pairwise compare the keywords of adjacent records, if out of order, then exchange, until there are no records in reverse order.

Code:

Public static void bubbleSort (int [] array) {for (int I = 0; I)

< array.length-1; i++) { for (int j = 0; j < array.length-1; j++) { if(array[j] >

Array [juni1]) {swap (array,j+1,j);}} public static void swap (int [] array,int iMint j) {int tmp = array [I]; array [I] = array [j]; array [j] = tmp

Complexity analysis:

Time complexity: O (N ^ 2)

Space complexity: O (1)

Stability: stability.

6. Quick sort 6.1. Recursive quick sort

Quick sort is an upgraded version of bubble sorting, and they all belong to the exchange sort class, that is, it also achieves sorting through continuous comparison and mobile swapping. The difference is that the implementation of quick sort increases the distance between record comparison and movement.

Fast scheduling moves the data with larger keywords directly from the front to the back, and the records with smaller keywords directly from the back to the front, thus reducing the total number of comparisons and mobile exchanges.

The basic idea of fast platoon:

Through a sort, the data to be sorted is divided into two independent parts, one of which is smaller than the other, and then the two parts are recorded and sorted again to achieve the order of the whole sequence.

Let's translate the above paragraph:

First of all, you have to have a middle number. Put aside the smaller one and the larger one. This number is called the reference value.

Using the idea of divide and conquer, the left and right cells are treated in the same way, until the length between cells = = 1, which means that it has been ordered, or the length between cells = 0, which means there is no data.

Maybe you are still a little confused when you see here, let's go to the code directly.

Public static void quickSort (int [] array) {quick (array,0,array.length-1);} public static void quick (int [] array,int left,int right) {if (left > = right) {return;} int pivot = partition (array,left,right); / / benchmark quick (array,left,pivot-1); quick (array,pivot+1,right);}

Isn't the above code a bit like traversing a binary tree?

There are indeed similarities between the two, which we will talk about later.

There is also a partition function, which is the most critical part of our quick sorting.

/ * * find the benchmark * @ param array array objects to be sorted * @ param start left boundary * @ param end right boundary * @ return reference value subscript * / private static int partition (int [] array,int start,int end) {int tmp = array [start]; while (start

< end) { while (start < end && array[end] >

= tmp) {end--;} / / end subscript encountered

< tmp的值 array[start] = array[end]; while (start < end && array[start] tmp的值 array[end] = array[start]; } array[start] = tmp; return start; } 我们下面通过图解模拟一下函数的运行过程： 可以看到，当第一轮走完之后，数据由基准值分成了两部分。 之后，我们再次对左右两部分完成同样的操作，如下： 一直递归下来，跟二叉树的遍历类似。 复杂度分析： 时间复杂度： 最好情况下：O（nlogn） 最坏情况下：O（n^2）. 空间复杂度：O（logn） 稳定性：不稳定 快排优化 不知大家看上面的图解的时候有没有一点困惑，就是我们这基准选得不好，导致第一趟递归下来的效果不好，变成了如下图： 如果我们有一种办法，先找到相对居中的那个数字，那么整个排序的时间复杂度是不是大大减小了。 于是，有人提出了随机选取一个值来作为基准，称为随机选取法。 这种做法，得看运气，因为假如选的好，刚刚选取中间值，那么，性能大大提高；如果随机得不好，比如随机到最小值或者最大值，那么性能则变成最差了。 所以有人提出一个新的方法，三数取中： 取三个关键字先进行排序，将中间数作为基准，一般取左端，右端和中间三个数。 如果运用三数取中这种方法的话，第一次比较的结果如下： 可以看到，11基本上与中间的数字相差不远了，性能大大提高。 所以，这里我们再写一个找基准的代码： /** * 找基准 三数取中法 * @param array 待排序数组对象 * @param left 左边界 * @param right 右边界 * @return 基准值下标 */ private static int findMidValIndex(int[] array,int start,int end) { int mid = start + ((end-start) >

> > 1); if (Array [start]

< array[end]) { if(array[mid] < array[start]) { return start; }else if(array[mid] >

Array [end]) {return end;} else {return mid;}} else {if (Array [mid] > array [start]) {return start;} else if (Array [mid])

< array[end]) { return end; }else { return mid; } } } 前面quick函数改动一下，如下： public static void quick(int[] array,int left,int right) { if(left >

= right) {return;} / / use the triple middle method to find the reference value int midValIndex = findMidValIndex (array,left,right); swap (array,midValIndex,left); int pivot = partition (array,left,right); / / benchmark quick (array,left,pivot-1); quick (array,pivot+1,right);}

In fact, it's great to optimize it so far. However, we can still optimize.

Here is a point of knowledge:

Direct insertion is the best in simple sorting. So if the array we want to sort is very small, it would be better to insert the sort directly. The reason is that fast sorting uses recursive operations, and when sorting a large amount of data, this performance impact is negligible compared to its overall algorithm advantage. But if the array has only a small amount of data to sort, it's a bit overqualified.

Therefore, our optimization here is:

Add a judgment that when the right-left+1 is less than a constant, the direct insertion sort is used, which depends on the case. In this way, we can ensure that we can maximize the advantages of the two kinds of sorting to complete the sorting work.

/ * optimize, add insert sort * @ param array array objects to be sorted * @ left boundary of param left * @ right boundary of param right * @ return reference subscript * / public static void quick (int [] array,int left,int right) {if (left > = right) {return } / / add a judgment. If the data in the interval is less than a certain range in the process of sorting, you can use direct insertion sorting if (right-left+1 tmp) {array [juni1] = array [j];} else {break }} array [jacks 1] = tmp;}} 6.2. Non-recursive implementation

As we all know, recursion has a certain impact on performance. So we can also use a non-recursive way to achieve quick sorting.

/ * * non-recursive implementation of quick sorting * @ param array array to be sorted * / public static void quickSort (int [] array) {Stack stack = new Stack (); int left = 0; int right = array.length-1; int pivot = partition (array,left,right); if (pivot > left+1) {stack.push (left) Stack.push (pivot-1);} if (pivot

< right-1) { stack.push(pivot+1); stack.push(right); } while (!stack.isEmpty()) { right = stack.pop(); left = stack.pop(); pivot = partition(array,left,right); if(pivot >

Left+1) {/ / there are 2 elements on the left: stack.push (left); stack.push (pivot-1);} if (pivot)

< right-1) { //右边有2个元素 stack.push(pivot+1); stack.push(right); } } } 非递归复杂度分析： 时间复杂度： 最坏情况下： O(n^2) 平均情况下：O（nlogn） 空间复杂度： 最坏情况下：O（n） 平均情况下：O（logn） 稳定性：不稳定 7.归并排序 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide an Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并 7.1.递归归并排序 直接上代码： //调用了mergeSortInternal函数 public static void mergeSort1(int[] array) { mergeSortInternal(array,0,array.length-1); } private static void mergeSortInternal(int[] array,int low,int high) { if(low>

= high) {return;} int mid = low + ((high-low) > 1); / / > unsigned move 1 bit to the right. That is, divide by 2 to find the intermediate value / / left recursive mergeSortInternal (array,low,mid); / right recursive mergeSortInternal (array,mid+1,high); / / merge two-sided array merge (array,low,mid,high);}

Illustration of the mergeSortInternal function:

In fact, it is a half-separated array.

Here the merge function is the key to merge sorting, and both recursive and non-recursive functions must be used.

Its essence is to merge two arrays and make them orderly.

Code for the merge function:

Private static void merge (int [] array,int low,int mid,int high) {int [] tmp = new int [high-low+1]; int k = 0 low; int bank / int S1 = low; int E1 = mid; int S2 = mid+1; int e2 = high; while (S1)

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.