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

This article mainly introduces "what sort algorithms programmers must know". In daily operations, I believe many people have doubts about the sorting algorithms that programmers must know. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "what sort algorithms programmers must know". Next, please follow the editor to study!

Introduction

As programmers, the top ten sorting is necessary and mastered by all qualified programmers, and popular algorithms such as fast sorting and merge sorting may also be asked in detail, requiring the mastery of algorithm performance and complexity. Bigsai, as a responsible Java and a small blogger in the direction of data structures and algorithms, must not let readers have loopholes in this respect. Follow this article, take you to sort out the top ten common sorting algorithms, easy to master!

First of all, for sorting, most people's concept of sorting stays in bubble sorting or Arrays.sort () in JDK. Handwritten sorting is an extravagant hope for many people, not to mention the top ten sorting algorithms, but fortunately you have encountered this article!

For sorting classification, the main different dimensions such as complexity, internal and external, comparative non-comparative and other dimensions to classify. The top ten sorting algorithms we normally talk about are internal sorting, and we divide them into two categories: sorting categories based on the dimension of "comparison and non-comparison".

Non-comparative categories include bucket sorting, cardinality sorting, and counting sorting. There are also many people who classify sorting into 8 major sorting, that is, because cardinality sorting and counting sorting are based on bucket sorting or a special bucket sorting, but cardinality sorting and counting sorting have their own unique characteristics, so here they are summarized into 10 classical sorting algorithms. The sort of comparison can also be divided into

There are also more detailed methods for comparing category sorting, including exchange-based, insertion-based, selection-based, merge-based, and a more detailed view of the brain map below.

Bubbling sort

Bubble sorting, also known as bubble sorting, is a typical exchange-based sorting, and it is also the basis of fast sorting. Bubble sorting is a stable sorting algorithm with a time complexity of O (n ^ 2). The basic idea is: "the loop traverses many times and adjusts the large elements back from the back, determining the largest (minimum) element at a time, and then reaching the sorting sequence several times." "(or adjust the small elements forward from back to front).

The specific idea is (to adjust the big elements back):

Traversing back from the first element, each position is determined whether it is larger than the later element, if it is larger than the later element, then swap the size of the two, and then continue backward. In this way, after a round, it is guaranteed that "the largest number is swapped to the last position can be determined."

The second time also determines the progress from the beginning, and if the current position is larger than the latter position, then swap with the number behind him. But one thing to note is that you don't need to judge at the end this time, you just need to judge the penultimate position (because for the first time we have determined that the largest one is in the penultimate position, this time the aim is to determine the penultimate position)

Similarly, the traversal length decreases by one at a time until the first element keeps the entire element in order.

For example, the sorting process of 2 5 3 1 4 is as follows:

The implementation code is:

Public void maopaosort (int [] a) {/ / TODO Auto-generated method stub for (int ionoma. For [1]) {int team=a [j]; a [j] = a [j + 1]; a [j] = team;} quick sort

Quick sorting is an improvement of bubble sorting, which is solved by the method of recursive divide and conquer. Compared to bubbling, fast platoon is an unstable sort, the worst time complexity is O (n ^ 2), the average time complexity is O (nlogn), and the best time complexity is O (nlogn).

For fast platoon, the "basic idea" is like this.

Fast arrangement needs to divide the sequence into two parts, that is, "the left side of the sequence is all less than one number" and "the right side of the sequence is all greater than one number", and then use the idea of recursion to sort the left sequence as a complete sequence. similarly, the right side of the sequence is sorted as a complete sequence.

Among them, this number can be taken randomly in this sequence, you can take the leftmost, you can take the rightmost, of course, you can also take a random number. But "usually" we don't optimize. We take the leftmost number.

The implementation code is:

Public void quicksort (int [] an int low=left; int high=right; int left,int right) {the order of the following two sentences must not be mixed, otherwise the array will cross the line! Very important!!! If (low > high) / / as to determine whether the cut-off condition return; int Kempa [low]; / / extra space k, take the leftmost space as a measure, and finally require that the left side is smaller than it, and the right side is larger than it. While (lowteam) {a [j] = a [j]; a [j] = team;} else {break;}} selection class sort simple selection sort

Simple selection sorting (Selection sort) is a simple and intuitive sorting algorithm. How it works: first find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence, then continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all the elements are sorted.

The implementation code is:

Public void selectSort (int [] arr) {for (int I = 0; I)

< arr.length - 1; i++) { int min = i; // 最小位置 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { min = j; // 更换最小位置 } } if (min != i) { swap(arr, i, min); // 与第i个位置进行交换 } } } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } 对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况 如果所有节点 「大于」 孩子节点值，那么这个堆叫做 「大根堆」 ，堆的最大值在根节点。 如果所有节点 「小于」 孩子节点值，那么这个堆叫做 「小根堆」 ，堆的最小值在根节点。 堆排序首先就是 「建堆」 ，然后再是调整。对于二叉树(数组表示)，我们从下往上进行调整，从 「第一个非叶子节点」 开始向前调整，对于调整的规则如下： 建堆是一个O(n)的时间复杂度过程，建堆完成后就需要进行删除头排序。给定数组建堆(creatHeap) ①从第一个非叶子节点开始判断交换下移(shiftDown)，使得当前节点和子孩子能够保持堆的性质 ②但是普通节点替换可能没问题，对如果交换打破子孩子堆结构性质，那么就要重新下移(shiftDown)被交换的节点一直到停止。 堆构造完成，取第一个堆顶元素为最小(最大)，剩下左右孩子依然满足堆的性值，但是缺个堆顶元素，如果给孩子调上来，可能会调动太多并且可能破坏堆结构。 ①所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown）,不过需要注意此时整个堆的大小已经发生了变化，我们在逻辑上不会使用被抛弃的位置，所以在设计函数的时候需要附带一个堆大小的参数。 ②重复以上操作，一直堆中所有元素都被取得停止。 而堆算法复杂度的分析上，之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换，每个个数最坏为logn个。这样复杂度就为O(nlogn).总的时间复杂度为O(n)+O(nlogn)=O(nlogn). 实现代码为： static void swap(int arr[],int m,int n) { int team=arr[m]; arr[m]=arr[n]; arr[n]=team; } //下移交换 把当前节点有效变换成一个堆(小根) static void shiftDown(int arr[],int index,int len)//0 号位置不用 { int leftchild=index*2+1;//左孩子 int rightchild=index*2+2;//右孩子 if(leftchild>

= len) return; else if (rightchild

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.