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

This article mainly explains "what are the common primary sorting algorithms". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn what are the common primary sorting algorithms.

Preface

It is believed that the algorithm that all programmers come into contact with at the beginning will be the sorting algorithm, because sorting plays such an important role in data processing and calculation, and the sorting algorithm is often the basis of other algorithms; in this paper, we will start with the primary sorting algorithm.

Template for sorting algorithm

Before we start, let's define a general template for the sorting algorithm, which will be implemented by subsequent sorting algorithms.

Public interface SortTemplate {void sort (Comparable [] array); default void print (Comparable [] array) {for (Comparable a: array) {System.out.print (a + ");}} default boolean less (Comparable a, Comparable b) {return a.compareTo (b)

< 0; } default void exch(Comparable[] array, int i, int j) { Comparable tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } Comparable: 为了让我们实现的排序算法更加的通用，可以排序任意的对象，所以我们这里使用了Comparable数组 sort: 不同的排序算法实现的方式不一样，子类自己去实现 less: 定义的公用方法，如果a < b就返回true exch: 定义的公用方法，交换数组中的两个对象 print: 打印出数据中的每个元素 选择排序 算法实现的思路： 首先找到数组中的最小元素， 其实将它和数组中的第一个元素进行交换，这样就排定了一个元素; 再次找出剩余元素中最小的元素与数组中的第二个元素进行交换，如此反复直到所有元素都是有序的

Code implementation:

Public class SelectionSort implements SortTemplate {@ Override public void sort (Comparable [] array) {int length = array.length; for (int I = 0; I)

< length; i++) { int min = i; for (int j = i + 1; j < length; j++) { if (less(array[j], array[min])) { min = j; } } exch(array, i, min); } } } 假如输入的数组是有序的，我们会发现选择排序运行的时候和未排序的时间一样长! 对于N个元素的数组，使用「选择排序的时间复杂度是O(n2)」 选择排序的是「数据移动最少」的，交换的次数与数组的大小是线性关系，N个元素的数组需要N次交换 冒泡排序 算法实现的思路： 比较相邻的两个元素，如果前一个比后一个大，那么就交换两个元素的位置 对每一组相邻的元素执行同样的操作，直到最后一个元素，操作完成之后就可以排定一个最大的元素 如此往复，直到数组中所有的元素都有序 代码实现： public class BubbleSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length - 1; for (int i = 0; i < length; i++) { for (int j = 0; j < length - i; j++) { if (less(array[j + 1], array[j])) { exch(array, j, j + 1); } } } } } 对于N个元素的数组，使用「冒泡排序的时间复杂度是O(n2)」 插入排序 想象我们在玩扑克牌时，整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似 算法实现的思路： 初始默认第一个元素就是有序的，当前索引的位置从0开始 先后移动当前索引的位置，当前索引位置左边的元素是有序的，从后往前开始扫码与当前索引位置元素进行比较 当确定当前索引位置上的元素在左边有序适合的位置之后，插入到该位置上 如果当确定当前索引位置上的元素大于了已排序的最后一个元素，那么当前索引位置直接往后移动 如此反复，直到所有元素有序 代码实现： public class InsertionSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length; for (int i = 1; i < length; i++) { for (int j = i; j >

0 & & less (array [j], array [j-1]); jmurm -) {exch (array, j, j-1);}}

From the implementation of the code, we can see that when the element of the current index is larger than the last element of the ordered array on the left, the inner loop ends directly, so there is a partial ordering in the array we sort. then the insertion sorting algorithm will be fast.

Considering the worst-case scenario, if the input array is inverted, then the efficiency of the insert sort is the same as the selection sort, "the time complexity is O (N2)"

Hill ranking

Insertion sorting is slow for large-scale disordered arrays because it only exchanges adjacent elements, which can only be moved to the correct position from the array bit by bit; insert sorting is efficient for partially ordered array sorting

Hill sorting improves insertion sorting based on these two characteristics.

The idea of realizing the algorithm

First set a step size h to separate the subarray

Sort h subarrays independently by inserting sort

Decrease the h step and continue sorting the subarray until h step is 1

When the step size is 1, it becomes a normal insertion sort, so the array must be ordered.

The reason why Hill sorting is efficient is that at the beginning of sorting, each subarray is very short, and the subarray is partially ordered after sorting, both of which are suitable for insertion sorting.

Code implementation:

Public class ShellSort implements SortTemplate {@ Override public void sort (Comparable [] array) {int gap = 1; int length = array.length; while (gap)

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

= 1) {for (int I = gap; I

< length; i++) { for (int j = i; j >

= gap & & less (array [j], array [j-gap]); j-= gap) {exch (array, j, j-gap);}} gap = gap / 3;}} so far, I believe you have a deeper understanding of "common primary sorting algorithms". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.