How to use the seven sorting methods of Java data structures
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;--j){ if(array[j]>tmp){ array[j+1]=array[j]; }else{ break; } } array[j+1]=tmp; } }
- Hill sort is an optimization of direct insertion sort.
- The purpose is to make the array closer to order, so pre-sorting is performed when gap > 1. Insertion sort can quickly sort a nearly ordered array when the gap is 1.
- The time complexity of Hill sorting is difficult to calculate, because there are many ways to obtain gap values, making it difficult to calculate.
public static void shellSort(int[] array){ int size=array.length; //这里定义gap的初始值为数组长度的一半 int gap=size/2; while(gap>0){ //间隔为gap的直接插入排序 for (int i = gap; i < size; 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; } gap/=2; } }
- Select the smallest data element in the element set array[i]--array[n-1]
- If it is not the first element in this set of elements one, then exchange it with the first element in this set of elements
- In the remaining set, repeat the above steps until there is 1 element left in the set
//交换 private static void swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; } //选择排序 public static void chooseSort(int[] array){ for (int i = 0; i < array.length; i++) { int minIndex=i;//记录最小值的下标 for (int j = i+1; j < array.length; j++) { if (array[j]<array[minIndex]) { minIndex=j; } } swap(array,i,minIndex); } }
- Create a small root heap, in order Take out the top element of the heap and put it into the array until the heap is empty
- Create a large root heap, define the tail element position key of the heap, and exchange the top element of the heap and the element at the key position each time (key --), until the key reaches the top of the heap. At this time, the sequential traversal of the elements in the heap is in ascending order (as follows)
Space complexity: O(N), unstableHeap sort:
//向下调整 public static void shiftDown(int[] array,int parent,int len){ int child=parent*2+1; while(child<len){ if(child+1<len){ if(array[child+1]>array[child]){ child++; } } if(array[child]>array[parent]){ swap(array,child,parent); parent=child; child=parent*2+1; }else{ break; } } } //创建大根堆 private static void createHeap(int[] array){ for (int parent = (array.length-1-1)/2; parent >=0; parent--) { shiftDown(array,parent,array.length); } } //堆排序 public static void heapSort(int[] array){ //创建大根堆 createHeap(array); //排序 for (int i = array.length-1; i >0; i--) { swap(array,0,i); shiftDown(array,0,i); } }
public static void bubbleSort(int[] array){ for(int i=0;i<array.length-1;++i){ int count=0; for (int j = 0; j < array.length-1-i; j++) { if(array[j]>array[j+1]){ swap(array,j,j+1); count++; } } if(count==0){ break; } } }
public static void quickSort(int[] array,int left,int right){ if(left>=right){ return; } int l=left; int r=right; int tmp=array[l]; while(l<r){ while(array[r]>=tmp&&l<r){ //等号不能省略,如果省略,当序列中存在相同的值时,程序会死循环 r--; } array[l]=array[r]; while(array[l]<=tmp&&l<r){ l++; } array[r]=array[l]; } array[l]=tmp; quickSort(array,0,l-1); quickSort(array,l+1,right); }
//key值的优化,只在快速排序中使用,则可以为private private int threeMid(int[] array,int left,int right){ int mid=(left+right)/2; if(array[left]>array[right]){ if(array[mid]>array[left]){ return left; } return array[mid]<array[right]?right:mid; }else{ if(array[mid]<array[left]){ return left; } return array[mid]>array[right]?right:mid; } }
随着我们递归的进行,区间会变的越来越小,我们可以在区间小到一个值的时候,对其进行插入排序,这样代码的效率会提高很多。
(3)快速排序的非递归实现
//找到一次划分的下标 public static int patition(int[] array,int left,int right){ int tmp=array[left]; while(left<right){ while(left<right&&array[right]>=tmp){ right--; } array[left]=array[right]; while(left<right&&array[left]<=tmp){ left++; } array[right]=array[left]; } array[left]=tmp; return left; } //快速排序的非递归 public static void quickSort2(int[] array){ Stack<Integer> stack=new Stack<>(); int left=0; int right=array.length-1; stack.push(left); stack.push(right); while(!stack.isEmpty()){ int r=stack.pop(); int l=stack.pop(); int p=patition(array,l,r); if(p-1>l){ stack.push(l); stack.push(p-1); } if(p+1<r){ stack.push(p+1); stack.push(r); } } }
四、归并排序
归并排序(MERGE-SORT):该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。实现序列的完全有序,需要将已经有序的子序列合并,即先让每个子序列有序,然后再将相邻的子序列段有序。若将两个有序表合并成一个有序表,称为二路归并。
时间复杂度:O(n*logN)(无论有序还是无序)
空间复杂度:O(N)。是稳定的排序。
//归并排序:递归 public static void mergeSort(int[] array,int left,int right){ if(left>=right){ return; } int mid=(left+right)/2; //递归分割 mergeSort(array,left,mid); mergeSort(array,mid+1,right); //合并 merge(array,left,right,mid); } //非递归 public static void mergeSort1(int[] array){ int gap=1; while(gap<array.length){ for (int i = 0; i < array.length; i+=2*gap) { int left=i; int mid=left+gap-1; if(mid>=array.length){ mid=array.length-1; } int right=left+2*gap-1; if(right>=array.length){ right=array.length-1; } merge(array,left,right,mid); } gap=gap*2; } } //合并:合并两个有序数组 public static void merge(int[] array,int left,int right,int mid){ int[] tmp=new int[right-left+1]; int k=0; int s1=left; int e1=mid; int s2=mid+1; int e2=right; while(s1<=e1&&s2<=e2){ if(array[s1]<=array[s2]){ tmp[k++]=array[s1++]; }else{ tmp[k++]=array[s2++]; } } while(s1<=e1){ tmp[k++]=array[s1++]; } while(s2<=e2){ tmp[k++]=array[s2++]; } for (int i = left; i <= right; i++) { array[i]=tmp[i-left]; } }
五、排序算法的分析
排序方法 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
直接插入排序 | O(n) | O(n^2) | O(1) | 稳定 |
希尔排序 | O(n) | O(n^2) | O(1) | 不稳定 |
直接排序 | O(n^2) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlog(2)n) | O(nlog(2)n) | O(1) | 不稳定 |
冒泡排序 | O(n) | O(n^2) | O(1) | 稳定 |
快速排序 | O(nlog(2)n) | O(n^2) | O(nlog(2)n) | 不稳定 |
归并排序 | O(nlog(2)n) | O(nlog(2)n) | O(n) | 稳定 |
The above is the detailed content of How to use the seven sorting methods of Java data structures. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

In this article, we have kept the most asked Java Spring Interview Questions with their detailed answers. So that you can crack the interview.

Java 8 introduces the Stream API, providing a powerful and expressive way to process data collections. However, a common question when using Stream is: How to break or return from a forEach operation? Traditional loops allow for early interruption or return, but Stream's forEach method does not directly support this method. This article will explain the reasons and explore alternative methods for implementing premature termination in Stream processing systems. Further reading: Java Stream API improvements Understand Stream forEach The forEach method is a terminal operation that performs one operation on each element in the Stream. Its design intention is

Guide to TimeStamp to Date in Java. Here we also discuss the introduction and how to convert timestamp to date in java along with examples.

PHP is a scripting language widely used on the server side, especially suitable for web development. 1.PHP can embed HTML, process HTTP requests and responses, and supports a variety of databases. 2.PHP is used to generate dynamic web content, process form data, access databases, etc., with strong community support and open source resources. 3. PHP is an interpreted language, and the execution process includes lexical analysis, grammatical analysis, compilation and execution. 4.PHP can be combined with MySQL for advanced applications such as user registration systems. 5. When debugging PHP, you can use functions such as error_reporting() and var_dump(). 6. Optimize PHP code to use caching mechanisms, optimize database queries and use built-in functions. 7

Capsules are three-dimensional geometric figures, composed of a cylinder and a hemisphere at both ends. The volume of the capsule can be calculated by adding the volume of the cylinder and the volume of the hemisphere at both ends. This tutorial will discuss how to calculate the volume of a given capsule in Java using different methods. Capsule volume formula The formula for capsule volume is as follows: Capsule volume = Cylindrical volume Volume Two hemisphere volume in, r: The radius of the hemisphere. h: The height of the cylinder (excluding the hemisphere). Example 1 enter Radius = 5 units Height = 10 units Output Volume = 1570.8 cubic units explain Calculate volume using formula: Volume = π × r2 × h (4

PHP and Python each have their own advantages, and the choice should be based on project requirements. 1.PHP is suitable for web development, with simple syntax and high execution efficiency. 2. Python is suitable for data science and machine learning, with concise syntax and rich libraries.

Java is a popular programming language that can be learned by both beginners and experienced developers. This tutorial starts with basic concepts and progresses through advanced topics. After installing the Java Development Kit, you can practice programming by creating a simple "Hello, World!" program. After you understand the code, use the command prompt to compile and run the program, and "Hello, World!" will be output on the console. Learning Java starts your programming journey, and as your mastery deepens, you can create more complex applications.

Spring Boot simplifies the creation of robust, scalable, and production-ready Java applications, revolutionizing Java development. Its "convention over configuration" approach, inherent to the Spring ecosystem, minimizes manual setup, allo
