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

This article is about how to gain an in-depth understanding of the common sorting algorithms in Java data structures. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article.

One, concept one, sort

Sorting is the operation of arranging a string of records in increments or decrements according to the size of one or some of the keywords. In the usual context, when it comes to sorting, it usually refers to sort ascending (not descending). Generally speaking, in place sort refers to the sort in place.

2, stability

For two equal data, if the sorting algorithm can ensure that the relative position of the sorting algorithm does not change after sorting, then we call it a stable sorting algorithm.

Or we say that a sort without a jump is also a stable sort.

Second, sort the detailed explanation.

1. Insert sort ① directly insert sort

The whole interval is divided into

1. Ordered interval

two。 Disordered interval

Select the first element of the unordered interval each time, and select the appropriate position to insert in the ordered interval.

Public static void main (String [] args) {int [] array = {12 array 5, 9, 34, 6, 8, 56, 8, 0, 7, 7, 4, 22, 55, 77); insertSort (array); System.out.println (Arrays.toString (array)) } / * time complexity: * Best: O (N)-> data is ordered * worst: O (N ^ 2)-> disordered data * Space complexity: O (1) * Stability: stable sorting * @ param array * / public static void insertSort (int [] array) {for (int I = 1 position I)

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

) {/ / array 1 if (Array [j] > tmp) {array [junk 1] = array [j];} else {/ / array [junk 1] = tmp; break;}} array [junk 1] = tmp;}

② Hill sorting

Hill sorting method is also known as shrinking incremental method. The basic idea of Hill sorting method is to select an integer first, divide all the records in the file to be sorted into a group, divide all the records with distance into the same group, and sort the records in each group. Then, fetch and repeat the above grouping and sorting work. When it reaches = 1, all records are sorted within the unified group.

1. Hill sorting is an optimization of direct insertion sorting.

two。 When gap > 1, it is pre-sorted in order to make the array more ordered. When gap = = 1, the array is close to ordered, so it will be very fast. In this way, on the whole, the optimization effect can be achieved. After we implement it, we can compare the performance test.

/ * time complexity: it is difficult to calculate the space complexity between n ^ 1.3 and n ^ 1.5 * Space complexity: O (1) * Stability: unstable sorting * technique: if there is no jump exchange during the comparison process, then it is a stable * @ param array * @ param array arrangement. Ordered array * @ param gap interval of each group-"number of groups * / public static void shell (int [] array) Int gap) {for (int I = gap I

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

= 0; j-= gap) {if (Array [j] > tmp) {array [j+gap] = array [j];} else {break;}} array [j+gap] = tmp } public static void main (String [] args) {int [] array = {12 array,5 5, 9, 34, 6, 8, 3, 56, 89, 0, 7, 5, 22, 5, 77, 77; shell (array,5); System.out.println (Arrays.toString (array));}

2. Select sort ① directly select sort

Each time, the largest (or smallest) element is selected from the unordered interval and stored at the end (or front) of the unordered interval until all the data elements to be sorted are finished.

Public static void main (String [] args) {int [] array = {12 array 5, 9, 34, 6, 8, 56, 8, 0, 7, 7, 4, 22, 55, 77); selectSort (array); System.out.println (Arrays.toString (array)) Time complexity: * Best: O (N ^ 2) * worst: O (N ^ 2) * Space complexity: O (1) * Stability: unstable * @ param array * / public static void selectSort (int [] array) {for (int I = 0; I)

< array.length; i++) { for (int j = i+1; j < array.length; j++) { if(array[j] < array[i]) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } } ②堆排序 基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。 注意： 排升序要建大堆；排降序要建小堆。 public static void main(String[] args) { int[] array = {12,5,9,34,6,8,33,56,89,0,7,4,22,55,77}; heapSort(array); System.out.println(Arrays.toString(array)); } public static void siftDown(int[] array,int root,int len) { int parent = root; int child = 2*parent+1; while (child < len) { if(child+1 < len && array[child] < array[child+1]) { child++; } //child的下标就是左右孩子的最大值下标 if(array[child] >

Array [parent]) {int tmp = array [child]; array [child] = array [parent]; array [parent] = tmp; parent = child; child = 2roomparentroom1;} else {break } public static void createHeap (int [] array) {/ / sort from small to large-"large root heap for (int I = (array.length-1-1) / 2; I > = 0; iMel -) {siftDown (array,i,array.length) }} / * time complexity: O (N*logN) is this time complexity * complexity: O (1) * Stability: unstable sorting * @ param array * / public static void heapSort (int [] array) {createHeap (array); / O (n) int end = array.length-1 While (end > 0) {/ / O (N*logN) int tmp = array [end]; array [end] = array [0]; array [0] = tmp; siftDown (array,0,end); end--;}}

3, exchange sort ① bubble sort

In the disordered interval, through the comparison of adjacent numbers, the largest number is bubbled to the end of the disordered interval, and the process continues until the array is ordered as a whole.

Public static void main (String [] args) {int [] array = {12 array 5, 9, 34, 6, 8, 56, 8, 0, 7, 7, 4, 22, 55, 77); bubbleSort (array); System.out.println (Arrays.toString (array)) } / * time complexity: * the best and worst is O (n ^ 2) * Space complexity: O (1) * Stability: stable sorting * Bubble Direct insertion * @ param array * / public static void bubbleSort (int [] array) {for (int I = 0; I)

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

Array [juni1]) {int tmp = array [j]; array [j] = array [juni1]; array [juni1] = tmp;}}

② quick sort

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 benchmark value (which can contain equal values) to the left of the benchmark value, and placing those larger than the benchmark value (which can include equal values) to the right side of the benchmark value

3. Using the idea of divide and conquer, the left and right cells are treated in the same way, until the length between cells = = 1, which means that it has been ordered, or the length between cells = 0, which means there is no data.

Public static void main (String [] args) {int [] array = {12 int [] array,int low,int high) {int tmp = array [low]; while (low)

< high) { while (low < high && array[high] >

= tmp) {high--;} array [low] = array [high]; while (low < high & & array [low] = end) {return;} int mid = (start+end) / 2; int pivot = partition (array,start,end); quick (array,start,pivot-1); quick (array,pivot+1,end) } / * time complexity: * best: O (n*logn) uniform segmentation * worst: O (n ^ 2) when the data is ordered * space complexity: * best: logn * worst: O (n) * stability: unstable Sort * * k*n*logn * 2 * 1.2 * @ param array * / public static void quickSort1 (int [] array) {quick (array) 0Perferent array.futhly1) }

4, merge and sort

Merge sorting (MERGE-SORT) is an effective sorting algorithm based on merge operation, which is 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 subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called two-way merging.

Public static void main (String [] args) {int [] array = {12 array,int low,int mid,int high 5, 9, 3, 6, 8, 5, 6, 8, 5, 6, 8, 6, 8, 5, 6, 8, 6, 8, 6, 8, 6, 8, 6, 8, 0, 7, 7, 7, 22, 55, 77, 77); mergeSort1 (array); System.out.println (Arrays.toString (array));} public static void merge (int [] array,int low,int mid,int high) {int S1 = low; int E1 = mid; int S2 = mid+1; int e2 = high Int [] tmp = new int [high-low+1]; int k = 0 / subscript while (S1) representing the array of tmp

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.