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

This article will explain in detail what are the common sorting algorithms in java. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

I. Bubble sorting

Train of thought:

Compare adjacent elements. If the first is larger than the second, exchange the two; do the same for each pair of adjacent elements, from the first pair to the last pair, so that the last element is the largest number; exclude the largest number, and then continue the same operation in the next round to determine the second largest number. Repeat steps 1-3 until the sorting is complete.

Animated demonstration:

Implementation code:

/ * *

* @ author Ye Hongzhi official account: java technology enthusiast

* @ name BubbleSort

* @ date 2020-09-05 21:38

* * /

Public class BubbleSort extends BaseSort {

Public static void main (String [] args) {

BubbleSort sort = new BubbleSort ()

Sort.printNums ()

}

@ Override

Protected void sort (int [] nums) {

If (nums = = null | | nums.length

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

Nums [j + 1]) {

Int temp = nums [j]

Nums [j] = nums [j + 1]

Nums [j + 1] = temp

}

}

}

}

}

/ / an array of 100000 entries, time consuming: 21554 milliseconds

Average time complexity: O (n ²)

Space complexity: O (1)

Algorithm stability: stability

Second, insert sort

Train of thought:

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

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

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

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

After the new element is inserted into that location

Repeat step 2-5.

Animated demonstration:

Implementation code:

/ * *

* @ author Ye Hongzhi official account: java technology enthusiast

* @ name InsertSort

* @ date 2020-09-05 22:34

* * /

Public class InsertSort extends BaseSort {

Public static void main (String [] args) {

BaseSort sort = new InsertSort ()

Sort.printNums ()

}

@ Override

Protected void sort (int [] nums) {

If (nums = = null | | nums.length

< 2) { return; } for (int i = 0; i < nums.length - 1; i++) { //当前值 int curr = nums[i + 1]; //上一个数的指针 int preIndex = i; //在数组中找到一个比当前遍历的数小的第一个数 while (preIndex >

= 0 & & curr

< nums[preIndex]) { //把比当前遍历的数大的数字往后移动 nums[preIndex + 1] = nums[preIndex]; //需要插入的数的下标往前移动 preIndex--; } //插入到这个数的后面 nums[preIndex + 1] = curr; } } } //10万个数的数组，耗时：2051毫秒 平均时间复杂度：O(n²) 空间复杂度：O(1) 算法稳定性：稳定 三、选择排序 思路： 第一轮，找到最小的元素，和数组第一个数交换位置。 第二轮，找到第二小的元素，和数组第二个数交换位置... 直到最后一个元素，排序完成。 动画演示： 实现代码： /** * @author Ye Hongzhi 公众号：java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/ public class SelectSort extends BaseSort { public static void main(String[] args) { SelectSort sort = new SelectSort(); sort.printNums(); } @Override protected void sort(int[] nums) { for (int i = 0; i < nums.length; i++) { int minIndex = i; for (int j = i + 1; j < nums.length; j++) { if (nums[j] < nums[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = nums[i]; nums[minIndex] = temp; nums[i] = nums[minIndex]; } } } } //10万个数的数组，耗时：8492毫秒 平均时间复杂度：O(n²) 算法空间复杂度：O(1) 算法稳定性：不稳定 四、希尔排序 思路： 把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->

Hmax 4-> hmax 8, and sort to ensure order. When hashes 1, the array sorting is complete.

Animated demonstration:

Implementation code:

/ * *

* @ author Ye Hongzhi official account: java technology enthusiast

* @ name SelectSort

* @ date 2020-09-06 22:27

* * /

Public class ShellSort extends BaseSort {

Public static void main (String [] args) {

ShellSort sort = new ShellSort ()

Sort.printNums ()

}

@ Override

Protected void sort (int [] nums) {

If (nums = = null | | nums.length

< 2) { return; } int length = nums.length; int temp; //步长 int gap = length / 2; while (gap >

0) {

For (int I = gap; I

< length; i++) { temp = nums[i]; int preIndex = i - gap; while (preIndex >

= 0 & & nums [preIndex] > temp) {

Nums [preIndex + gap] = nums [preIndex]

PreIndex-= gap

}

Nums [preIndex + gap] = temp

}

Gap / = 2

}

}

}

/ / an array of 100000 entries, time consuming: 261ms

Average time complexity: O (nlog2n)

Algorithm space complexity: O (1)

Algorithm stability: stability

5. Quick sorting

Quick platoon, the most popular sorting algorithm for interview. This is a sort algorithm using divide-and-conquer method.

Train of thought:

Choose a number from the array as the base value, usually the first number, or the last number. Double pointers (head and tail) are used to traverse, from left to right to find the first number larger than the base value, from right to left to find the first number smaller than the base value, and to exchange two positions until the head and tail pointers are equal or the head pointer is larger than the tail pointer. swap the base value with the number of the head pointer. After such a round, the number on the left is smaller than the benchmark, and the number on the right is larger than the benchmark. Repeat step 1 above for the sequence on the left. Repeat step 1 and step 2 on the right. After the recursive end of the series on the left and right sides, the sorting is complete.

Animated demonstration:

Implementation code:

/ * *

* @ author Ye Hongzhi official account: java technology enthusiast

* @ name SelectSort

* @ date 2020-09-06 22:27

* * /

Public class QuickSort extends BaseSort {

Public static void main (String [] args) {

QuickSort sort = new QuickSort ()

Sort.printNums ()

}

@ Override

Protected void sort (int [] nums) {

If (nums = = null | | nums.length

< 2) { return; } quickSort(nums, 0, nums.length - 1); } private void quickSort(int[] nums, int star, int end) { if (star >

End) {

Return

}

Int I = star

Int j = end

Int key = nums [star]

While (I)

< j) { while (i < j && nums[j] >

Key) {

Jmuri-

}

While (I)

< j && nums[i] = end) { return; } int mid = star + (end - star) / 2; //左边进行归并排序 mergeSort(star, mid, nums, temp); //右边进行归并排序 mergeSort(mid + 1, end, nums, temp); //合并左右 merge(star, end, mid, nums, temp); } private void merge(int star, int end, int mid, int[] nums, int[] temp) { int index = 0; int i = star; int j = mid + 1; while (i nums[parentIndex]) { //交换当前遍历的值与父节点的值 swap(nums, currIndex, parentIndex); //把父节点的索引指向当前遍历的索引 currIndex = parentIndex; //往上计算父节点索引 parentIndex = (currIndex - 1) / 2; } } } private void updateHeap(int[] nums, int size) { int index = 0; //左节点索引 int left = 2 * index + 1; //右节点索引 int right = 2 * index + 2; while (left < size) { //最大值的索引 int largestIndex; //如果右节点大于左节点，则最大值索引指向右子节点索引 if (right < size && nums[left] < nums[right]) { largestIndex = right; } else { largestIndex = left; } //如果父节点大于最大值，则把父节点索引指向最大值索引 if (nums[index] >

Nums [largestIndex]) {

LargestIndex = index

}

/ / if the parent node index points to the maximum index, it is proved to be a large root heap and exit the loop

If (largestIndex = = index) {

Break

}

/ / if it is not a large root heap, swap the value of the parent node

Swap (nums, largestIndex, index)

/ / change the index of the maximum value to the parent node index

Index = largestIndex

/ / recalculate the left node index

Left = 2 * index + 1

/ / recalculate the right node index

Right = 2 * index + 2

}

}

Private void swap (int [] nums, int I, int j) {

Int temp = nums [I]

Nums [I] = nums [j]

Nums [j] = temp

}

}

/ / an array of 100000 entries, which takes 38 milliseconds

Average time complexity: O (nlogn)

Algorithm space complexity: O (1)

Algorithm stability: unstable

8. Bucket sorting

Train of thought:

Find the maximum and minimum values. Several buckets are created based on the length of the array. Traverses the elements of the array and puts them into the corresponding bucket according to the value of the element. Sort the elements of each bucket (quick sort, insert sort, etc.). Merge the elements of each bucket in order, and the sorting is complete.

When the elements in the array are evenly distributed, the sorting efficiency is higher. On the contrary, if the distribution is uneven, it will cause most of the numbers to fall into the same bucket, which will reduce the efficiency.

Animation demonstration (from five-minute learning algorithm, intrusion and deletion):

Implementation code:

/ * *

* @ author Ye Hongzhi official account: java technology enthusiast

* @ name BucketSort

* @ date 2020-09-08 23:37

* * /

Public class BucketSort extends BaseSort {

Public static void main (String [] args) {

BucketSort sort = new BucketSort ()

Sort.printNums ()

}

@ Override

Protected void sort (int [] nums) {

If (nums = = null | | nums.length

< 2) { return; } bucketSort(nums); } public void bucketSort(int[] nums) { if (nums == null || nums.length < 2) { return; } //找出最大值，最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int num : nums) { min = Math.min(min, num); max = Math.max(max, num); } int length = nums.length; //桶的数量 int bucketCount = (max - min) / length + 1; int[][] bucketArrays = new int[bucketCount][]; //遍历数组，放入桶内 for (int i = 0; i < length; i++) { //找到桶的下标 int index = (nums[i] - min) / length; //添加到指定下标的桶里，并且使用插入排序排序 bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]); } int k = 0; //合并全部桶的 for (int[] bucketArray : bucketArrays) { if (bucketArray == null || bucketArray.length == 0) { continue; } for (int i : bucketArray) { //把值放回到nums数组中 nums[k++] = i; } } } //每个桶使用插入排序进行排序 private int[] insertSortArrays(int[] arr, int num) { if (arr == null || arr.length == 0) { return new int[]{num}; } //创建一个temp数组，长度是arr数组的长度+1 int[] temp = new int[arr.length + 1]; //把传进来的arr数组，复制到temp数组 for (int i = 0; i < arr.length; i++) { temp[i] = arr[i]; } //找到一个位置，插入，形成新的有序的数组 int i; for (i = temp.length - 2; i >

= 0 & & temp [I] > num; imuri -) {

Temp [I + 1] = temp [I]

}

/ / insert the value to be added

Temp [I + 1] = num

/ / return

Return temp

}

}

/ / an array of 100000 entries, time consuming: 8750 milliseconds

Average time complexity: O (masking N)

Algorithm space complexity: O (masking N)

Algorithm stability: stable (depending on the sorting algorithm in the bucket, the insertion sort is used here, so it is stable).

Summary

The animation demonstration comes from the algorithm learning website: https://visualgo.net

After talking about these sorting algorithms, someone may ask what is the use of learning these sorting algorithms, just to cope with the written interview? These are not usually used by developers.

I think we should look at it from a different point of view. For example, in high school, we studied physics, chemistry, mathematics, and so many formulas and theorems, which are not very useful now, but why do high school textbooks teach them?

My understanding is: first, popularize some common sense problems. Second, exercise your thinking and improve your ability to solve problems. Third, in order to distinguish between talents.

Back to the question of what is the use of sorting algorithms, in fact, it is the same. These most basic sorting algorithms are common sense problems that developers should understand and master. At the same time, it also exercises the programming thinking, including the ideas of double pointers, divide and conquer, recursion and so on. Finally, what is reflected in the interview is the division of talents, and knowing these basic sorting algorithms is certainly more competitive than those who do not.

This is the end of this article on "what are the common sorting algorithms in java?" I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it out for more people to see.

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.