Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

How to implement Bubble, selection, insert, Hill and merge sorting algorithms in Java

2025-01-19 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

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

This article is about how Java implements bubbling, selection, insertion, Hill, and merge sorting algorithms. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Simple sorting

Common time complexity

? Constant order (1)

? Logarithmic order (log2n)

? Linear order (n)

? Linear logarithmic order (nlog2n)

? Square order square (n ²)

? Cubic order (n ³)

? KTH (n ^ k)

? Exponential order (2 ^ n)

Common time complexity map

Please (1) < log2n (n) < nlog2n (n) < broadcast (n ²) < broadcast (n ³) <... < broadcast (2 ^ n) < broadcast (n!) Arr [j + 1]) {swap (arr, j, j + 1);} public static void swap (int [] arr, int I, int j) {int temp = arr [I]; arr [I] = arr [j]; arr [j] = temp;} selection sort (Quicksort)

Algorithm description:

Selective sorting is a simple and intuitive sorting algorithm. It works as follows: select the smallest (or largest) element from the data elements to be sorted for the first time, store it at the beginning of the sequence, and then find the smallest (largest) element from the remaining unsorted elements. continue to put it in the starting position until the number of unsorted elements is 0.

Code implementation:

Public static void selectionSort (int [] a) {/ / each time you complete a round, you will find a minimum, where an I represents a round of for (int I = 0; I

< a.length; i++) { int index = i; //每一轮从i+1开始找,查找是否有比当前值更小的值 for (int j = i + 1; j < a.length; j++) { if (a[index] >

A [j]) {index = j;}} / / if index and I are not equal, the subscript has been exchanged, that is to say, a smaller number has been found, if (index! = I) {swap (a, index, I);}} public static void swap (int [] a, int I, int j) {int temp = a [I] A [I] = a [j]; a [j] = temp;} insert sort (insertSort)

Algorithm description:

Insertion sorting is also a common sorting algorithm. the idea of insertion sorting is to divide the initial data into ordered and unordered parts, and each step inserts the data of an unordered part into the ordered part that has been sorted before. until all the elements have been inserted. The steps to insert the sort are as follows: take one element from the unordered part at a time, compare it with the elements in the ordered part from back to front, and find the appropriate position to insert the element into the ordered group. Divide the array into two ends, an ordered array and an unordered array, and insert the values from the unordered array into the unordered array in turn.

As shown in the figure, the process of inserting 4 is to divide the array into two ends, an ordered array and an unordered array, and then insert the values from the unordered array into the unordered array.

Figure 367 below is an ordered array and 42 is an unordered array. Insert 4Bing 2 into the unordered array in turn.

As shown in the figure, the process of inserting 4 is as follows

Code implementation:

Public static void insertionSort (int [] a) {for (int I = 1; I)

< a.length; i++) { int temp = a[i]; int j; // 查到合适的插入位置,插入即可 for (j = i - 1; j >

= 0 & & a [j] > temp; Jmuri -) {a [j + 1] = a [j];} a [j + 1] = temp;}} Hill sort (ShellSort)

Algorithm description:

Hill sorting is an improved algorithm based on insertion sorting. Because it can lead to inefficiency when the data is moved too many times. So we can first make the array as a whole in order (a little more at the beginning, then a little smaller later), so that the number of moves will be reduced, and then the efficiency will be improved.

Code implementation:

Public static void shellSort (int [] a) {for (int step = a.length / 2; step > 0; step / = 2) {/ / the following process is similar to the insertion sort for (int I = step; I)

< a.length; i++) { int temp = a[i]; int j; for (j = i - step; j >

= 0 & a [j] > temp; j-= step) {a [j + step] = a [j];} a [j + step] = temp;}} merge sort (MergetSort)

Algorithm description:

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

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

3. 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

4. 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.

Easy to understand, looking for pictures directly on the Internet.

Code implementation:

Public static void mergeSort (int [] a, int left, int right) {/ / segments the array into only one element if (left = = right) {return;} int mid = (left + right) / 2; mergeSort (a, left, mid); / / Recursive mergeSort (a, mid + 1, right); merge (a, left, mid, right) } public static void merge (int [] a, int left, int mid, int right) {int [] temp = new int [right-left + 1]; int I = left; int j = mid + 1; int k = 0; while (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.

Views: 0

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report