<> Insert sort
<>1. Direct insert sort
* Time complexity ： best O(n) , worst O(n2) , average O(n2)
* stable
public class Main{ public static void main(String[] args) { int[] nums={4,5,8,7
,9,6,3,2,1}; int len=nums.length; int num=-1; for (int i = 1; i <len; i++) {
// Give the current element to the sentry first num=nums[i]; int j; for (j = i-1;j>=0&&num<nums[j]; j--) { nums[j+1]
=nums[j]; } nums[j+1]=num; } System.out.println(nums); } }
<>2. Shell Sort
<> Exchange sort
<>1. Bubble sorting
* Time complexity ： best O(n2), worst O(n2), average O(n2)
* stable
public class Main{ public static void main(String[] args) { int[] nums={4,5,8,7
,9,6,3,2,1}; int len=nums.length; for (int i = 0; i < len - 1; i++) { boolean
flag=false; // Indicates whether there has been an exchange in this traversal for (int j = len-1; j >i; j--) { if(nums[j-1]>nums[j
]){ int temp=nums[j]; nums[j]=nums[j-1]; nums[j-1]=temp; flag=true; } } if(!flag
)break; } System.out.println(nums); // There is no exchange in this traversal , Description order } }
<>2. Quick sort
* Time complexity ： best O(n l o g 2 n {log_2{n}} log2n), worst O(n2), average O(n l o g 2 n {log_2{n}}
log2n)
* Spatial complexity ：O(n l o g 2 n {log_2{n}} log2n) Recursive use stack
* instable
* Java code public class Main{ public static void main(String[] args) { int[]
nums= {4, 6, 8, 5, 9, 7, 2, 1, 3}; int low=0,high=nums.length-1; QuickSort(nums,
low,high); System.out.println(nums); } // recursion private static void QuickSort(int[]
nums, int low, int high) { if(low>=high)return; // End condition if(low<high){ int
pivotpos=Partition(nums,low,high); QuickSort(nums,low,pivotpos-1); QuickSort(
nums,pivotpos+1,high); } } // Determine the position of one element at a time private static int Partition(int[]
nums, int low, int high) { int pivot=nums[low]; while (low<high){ while (low<
high&&nums[high]>=pivot)--high; nums[low]=nums[high]; while (low<high&&nums[low]
<=pivot)++low; nums[high]=nums[low]; } nums[low]=pivot; return low; } }
Technology
Daily Recommendation