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

What are several common sorting algorithms in java? I believe many inexperienced people don't know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

1 sort

Sorting is the operation of increasing or decreasing a string of records according to the size of one or some of its keywords.

In the usual context, the reference to sorting usually refers to ascending order.

2 stability

For two identical data, if the sorting algorithm can ensure that its relative position does not change after sorting, it is said that the algorithm has stable distribution.

[insert sort]

[optimized version]

Analysis step

The first step: set the subscript of the first element to I, and let index and I point to the same element.

The second part sets the loop to use the j loop to find out the smallest element except the first element and hand it over to the index

The third step is to exchange index with the first element

Public static void insertSort (int [] array) {for (int I = 1; I)

< array.length; i++) { int tmp = array[i]; int j = i-1; for (; j >

= 0; array -) {if (Array [j] > tmp) {array [jung1] = array [j];} else {/ / array [jmur1] = tmp; as long as j rollback and encounters an element smaller than tmp, it ends this comparison break. }} / / j falls back to a place less than 0 array [jacks 1] = tmp;}} [Hill sort]

(those who seldom take part in interviews based on understanding)

[analysis steps]

[select sort]

Analysis step

The first step: set the subscript of the first element to I, and let index and I point to the same element.

The second part sets the loop to use the j loop to find out the smallest element except the first element and hand it over to the index

The third step is to exchange index with the first element

[heap sort]

Notes! The basic principle is still sorting. It only uses the heap for unordered sorting without traversing.

Public static void createHeap (int [] array) {for (int parent = (array.length-1-1) / 2; parent > 0; parent--) {/ / set the parent node shiftDown (array, parent, array.length); / /}} public static void shiftDown (int [] array, int parent, int len) {int child = 2 * parent + 1 / set child node while (child

< len) { if (child + 1 < len && array[child] < array[child + 1]) { child++;//以防有两个子节点 找出两个子节点最大一位 } if (array[child] >

Array [parent]) {swap (array, parent, child); / / Exchange parent node and child node parent = child;// re-set parent node child = 2 parents parentnodes 1;} else {break;} public static void heapSort (int [] array) {/ / createHeap (array); int end = array.length-1 / / after each exchange of the last element minus one bit while (end > 0) {swap (array,0,end); shiftDown (array,0, array.length-1); / / the downward transition in this cycle end--;}} [bubble sort]

Comments; it may be one of several relatively simple sorting.

This paper introduces an optimization method of bubble sorting.

[quick sort]

Introduction to principles-Overview

1 Select a number from the interval to be sorted as the base value (pivot)

2 partition: traverses the entire range to be sorted, placing those smaller than the datum (which can be the same as the datum) on the left side of the base, and placing the larger ones (which can be the same as the datum) on the right side of the datum.

(3) using the idea of divide and conquer, the left and right cells are processed according to the same method until the length of the cells is = = 1; then it represents order, and if the length = = 0, there are no elements.

Public static void quick (int [] array,int left,int right) {if (left > = right) {/ / determine that the recursive condition does not meet the exit return;} int pivot = partition (array,left,right); / / find the benchmark value quick (array,left, pivot-1); / / Recursive quick (array, pivot+1, right) on the left / / Recursive} private static int partition (int [] array,int start,int end) {int tmp = array [start]; while (start) on the right

< end){// while(start< end &&array[end] >

Tmp) {/ / the tail subtracts end--;} array [start] = array [end] when the tail value is larger than tmp; / / encounter an element smaller than tmp on the right to swap while (start < end & & array [start] < tmp) {/ / compare the header to swap start++ more hours than tmp } array [end] = array [start];} array [end] = tmp; return end;} public static void quickSort (int [] array) {quick (array,0, array.length-1);}} [merge sort]

Principle-Overview

Merge sorting (MERGE-SORT) is an effective sorting algorithm based on merge operation, which adopts a very typical application of divide-and-conquer (Divide and Conquer). The ordered subsequences are merged to get a completely ordered sequence, that is, each subsequence is ordered first, and then the segments of the subsequence are ordered. If two ordered tables are merged into one ordered table, it is called two-way merging.

Before that, review (chain list) [merge two ordered linked lists] (the basis of merge sorting)

Public static int [] mergeArray (int [] array1,int [] array2) {/ / pay attention to the judgment parameter int [] tmp = new int [array1.length + array2.length]; int I = 0; int S1 = 0; int E1 = array1.length-1; int S2 = 0; int e2 = array2.length-1; while (S1)

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.