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

This article mainly explains "how to use the classical sorting algorithm of java code". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to use the classical sorting algorithm of java code".

Sorting algorithm is one of the most basic algorithms in data structure and algorithm.

The sorting algorithm can be divided into internal sorting and external sorting. The internal sorting is that the data records are sorted in memory, while the external sorting is because the sorted data is so large that it can not accommodate all the sorted records at one time. Access to external memory is needed in the sorting process. Common internal sorting algorithms are: insert sort, Hill sort, select sort, bubble sort, merge sort, quick sort, heap sort, cardinality sort and so on. Summarize it with a picture:

About time complexity:

Square order (O (N2)) sort all kinds of simple sort: direct insertion, direct selection and bubbling sort.

Linear logarithmic order (O (nlog2n)) sort Quick sort, heap sort, and merge sort.

O (N1 + §), which is a constant between 0 and 1. Hill sort.

Linear order (O (n)) sort cardinal sort, in addition, there are bucket and box sorting.

About stability:

Stable sorting algorithms: bubble sort, insert sort, merge sort and cardinality sort.

Is not a stable sorting algorithm: select sort, quick sort, Hill sort, heap sort.

The noun explains:

N: data scale

K: number of buckets

In-place: occupies constant memory, not extra memory

Out-place: takes up extra memory

Stability: the order of the two equal keys after sorting is the same as that before sorting.

I. Bubble sorting

Bubble sorting (Bubble Sort) is also a simple and intuitive 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.

As one of the simplest sorting algorithms, Bubble sorting gives me the same feeling as Abandon in a word book, in the * * page * * bit every time, so I am most familiar with it. Another optimization algorithm for bubble sorting is to set up a flag. When elements are not exchanged in a sequence traversal, it is proved that the sequence has been ordered. But this improvement does not do much to improve performance.

1. Algorithm step

Compare adjacent elements. If one is bigger than the second, exchange the two of them.

Do the same for each pair of adjacent elements, from the beginning pair to the end pair. After this step is done, the element of * will be the number of *.

Repeat the above steps for all elements, except for one.

Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

two。 Moving picture demonstration

3. When is the fastest time?

When the input data is already in positive order (it's already in positive order, what's the use of bubbling sorting?).

4. When is the slowest?

When the input data is in reverse order (just write a for loop to output the data in reverse order, why use you to bubble sort it, am I free).

5. Java code implementation

Public class BubbleSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / copy a pair of arr without changing the parameter content int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); for (int I = 1; I

< arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。 boolean flag = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] >

Arr [j + 1]) {int tmp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = tmp; flag = false;}} if (flag) {break }} return arr;}}

2. Selection and sorting

Selective sorting is a simple and intuitive sorting algorithm, no matter what data is entered, it is O (n ²) time complexity. So when using it, the smaller the data, the better. The only benefit may be that it doesn't take up extra memory space.

1. Algorithm step

First, find the smallest (largest) element in the unsorted sequence and store it at the beginning of the sorted sequence.

Continue to look for the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.

Repeat the second step until all the elements are sorted.

two。 Moving picture demonstration

3. Java code implementation

Public class SelectionSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); / / A total of 1 round of comparison for (int I = 0; I)

< arr.length - 1; i++) { int min = i; // 每轮需要比较的次数 N-i for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } return arr; } } 三、插入排序 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。 1. 算法步骤 将***待排序序列***个元素看做一个有序序列，把第二个元素到***一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。) 2. 动图演示 3. Java 代码实现 public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i; while (j >

0 & & tmp

< arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp; } } return arr; } } 四、希尔排序 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。 1. 算法步骤 选择一个增量序列 t1，t2，……，tk，其中 ti >

Tj, tk = 1

Sort the sequence k times according to the number of incremental sequences k

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.

2. Java code implementation

Public class ShellSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / A copy of arr without changing the parameter content int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); int gap = 1; while (gap)

< arr.length) { gap = gap * 3 + 1; } while (gap >

0) {for (int I = gap; I

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

= 0 & & arr [j] > tmp) {arr [j + gap] = arr [j]; j-= gap;} arr [j + gap] = tmp;} gap = (int) Math.floor (gap / 3);} return arr;}}

V. merging and sorting

Merge sorting (Merge sort) is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of divide-and-conquer (Divide and Conquer).

As a typical algorithm application of divide-and-conquer idea, merge sorting is realized by two methods:

Top-down recursion (all recursive methods can be iteratively rewritten, so there is a second method)

Bottom-up iteration

In "JavaScript description of data structures and algorithms", the author gives a bottom-up iterative method. However, for the recursive method, the author thinks that:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

However, this approach is not feasible in JavaScript because the recursion depth of the algorithm is too deep for it.

To tell you the truth, I don't quite understand this sentence. Does it mean that the memory of the JavaScript compiler is too small and the recursion is too deep to cause memory overflow? I also hope that there are great gods who can give us some advice.

Like selective sorting, the performance of merge sorting is not affected by the input data, but it performs much better than selective sorting, because it is always O (nlogn) time complexity. The cost is that extra memory space is required.

1. Algorithm step

Apply for space so that it is the sum of two sorted sequences, which is used to store the merged sequence

Set two pointers, initially at the start of the two sorted sequences

Compare the elements pointed to by the two pointers, select the relatively small elements to put into the merge space, and move the pointer to the next location

Repeat step 3 until a pointer reaches the end of the sequence

Copy all the remaining elements of another sequence directly to the end of the merge sequence.

two。 Moving picture demonstration

3. Java code implementation

Public class MergeSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / copy a pair of arr without changing the parameter content int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); if (arr.length)

< 2) { return arr; } int middle = (int) Math.floor(arr.length / 2); int[] left = Arrays.copyOfRange(arr, 0, middle); int[] right = Arrays.copyOfRange(arr, middle, arr.length); return merge(sort(left), sort(right)); } protected int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; int i = 0; while (left.length >

0 & & right.length > 0) {if (left [0] 0) {result [ionization +] = left [0]; left = Arrays.copyOfRange (left, 1, left.length);} while (right.length > 0) {result [ionization +] = right [0]; right = Arrays.copyOfRange (right, 1, right.length) } return result;}}

VI. Quick sorting

Quick sorting is a sort algorithm developed by Tony Hall. On average, sorting n items requires nlogn comparisons. 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.

Quick sort uses the divide-and-conquer (Divide and conquer) strategy to divide a serial (list) into two subserial (sub-lists).

Quick sorting is also a typical application of divide-and-conquer idea in sorting algorithm. In essence, quick sorting should be regarded as a recursive divide-and-conquer method based on bubble sorting.

The name of quick sort is simple and rude, because as soon as you hear the name, you know the meaning of its existence, that is, fast and efficient! It is one of the fastest sorting algorithms to deal with big data. Although Worst Case has a time complexity of O (n ²), others are excellent and perform better than sorting algorithms with an average time complexity of O (n logn) in most cases, but I don't know why.

The worst-case scenario for quick sorting is O (n ²), such as the quick sort of a sequential sequence. But its expected equalization time is O (nlogn), and the constant factor implied in the O (nlogn) notation is very small, which is much smaller than the merge ordering whose complexity is stably equal to O (nlogn). Therefore, for the vast majority of random sequences with weak ordering, quick sorting is always better than merge sorting.

1. Algorithm step

Pick an element from a series, called a "pivot"

Reorder the series so that all elements smaller than the benchmark are placed in front of the benchmark, and all elements larger than the benchmark are placed behind the benchmark (the same number can be on either side). After the partition exits, the datum is in the middle of the series. This is called a partition operation

Recursive sorts the subseries of elements less than the reference value and the subseries of elements greater than the reference value

In the recursive case, the size of the sequence is zero or one, that is, it has always been sorted. Although recursive all the time, the algorithm always exits, because in each iteration, it puts at least one element in its position.

two。 Moving picture demonstration

3. Java code implementation

Public class QuickSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / A copy of arr without changing the parameter content int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); return quickSort (arr, 0, arr.length-1);} private int [] quickSort (int [] arr, int left, int right) {if (left)

< right) { int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; } private int partition(int[] arr, int left, int right) { // 设定基准值（pivot） int pivot = left; int index = pivot + 1; for (int i = index; i 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0, len); } return arr; } private void buildMaxHeap(int[] arr, int len) { for (int i = (int) Math.floor(len / 2); i >

= 0; iMel -) {heapify (arr, I, len);}} private void heapify (int [] arr, int I, int len) {int left = 2 * I + 1; int right = 2 * I + 2; int largest = I; if (left

< len && arr[left] >

Arr [largest]) {largest = left;} if (right

< len && arr[right] >

Arr [largest]) {largest = right;} if (largest! = I) {swap (arr, I, largest); heapify (arr, largest, len);}} private void swap (int [] arr, int I, int j) {int temp = arr [I]; arr [I] = arr [j] Arr [j] = temp;}}

VIII. Counting and sorting

The core of counting sorting is to convert the input data values into keys and store them in the extra array space. As a sort of linear time complexity, counting sorting requires that the input data must be integers with a definite range.

1. Moving picture demonstration

2. Java code implementation

Public class CountingSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / A copy of arr without changing the parameter content int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); int maxValue = getMaxValue (arr); return countingSort (arr, maxValue);} private int [] countingSort (int [] arr, int maxValue) {int bucketLen = maxValue + 1 Int [] bucket = new int [bucketLen]; for (int value: arr) {bucket[ value] +;} int sortedIndex = 0; for (int j = 0; j)

< bucketLen; j++) { while (bucket[j] >

0) {arr [sortedIndex++] = j; bucket [j] -;}} return arr;} private int getMaxValue (int [] arr) {int maxValue = arr [0]; for (int value: arr) {if (maxValue)

< value) { maxValue = value; } } return maxValue; } } 九、桶排序 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点： 在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 2. 什么时候最慢 当输入的数据被分配到了同一个桶中。 3. Java 代码实现 public class BucketSort implements IArraySort { private static final InsertSort insertSort = new InsertSort(); @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); return bucketSort(arr, 5); } private int[] bucketSort(int[] arr, int bucketSize) throws Exception { if (arr.length == 0) { return arr; } int minValue = arr[0]; int maxValue = arr[0]; for (int value : arr) { if (value < minValue) { minValue = value; } else if (value >

MaxValue) {maxValue = value;}} int bucketCount = (int) Math.floor ((maxValue-minValue) / bucketSize) + 1; int [] [] buckets = new int [bucketCount] [0]; / / use the mapping function to allocate data to each bucket for (int I = 0; I < arr.length) Int index = (int) Math.floor ((arr [I]-minValue) / bucketSize); buckets [index] = arrAppend (buckets [index], arr [I]);} int arrIndex = 0; for (int [] bucket: buckets) {if (bucket.length)

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.