排序算法小结

冒泡排序

package com.company; public class bubblingSort { public static void main(String[] args) { int[] nums={1,3,4,5,7,2,4,5,6}; sort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); //输出：7 6 5 5 4 3 2 1 } } public static void sort(int[] nums){ for (int i = nums.length-1; i >0; i--) { for (int j = 0; j < i; j++) { if (nums[j]<nums[j+1]){ int temp =nums[j]; nums[j]=nums[j+1]; nums[j+1]=temp; } } } } }

插入排序

package com.company; public class charuSort { public static void main(String[] args) { int[] num={2,1,4,5,3,6,4}; choose(num); for (int i = 0; i < num.length; i++) { System.out.print(num[i]+" "); //输出1 1 2 3 4 5 5 6 7 } } public static void choose(int[] nums){ for (int i = 0; i < nums.length; i++) { for (int j = i; j > 0; j--) { if (nums[j]<nums[j-1]){ swap(nums,j,j-1); } } } } public static void swap(int[] nums,int a,int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }

选择排序

package com.company; public class chosesort { public static void main(String[] args) { int[] num={2,1,4,5,3,6,4}; choose(num); for (int i = 0; i < num.length; i++) { System.out.print(num[i]+" "); //输出1 1 2 3 4 5 5 6 7 } } public static void choose(int[] nums){ for (int i = 0; i < nums.length; i++) { int temp=i; for (int j = i; j < nums.length; j++) { if (nums[j]<nums[temp]){ temp=j; } } swap(nums,i,temp); } } public static void swap(int[] nums,int a,int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }

堆排序

package com.company; public class heapSort { public static void main(String[] args){ int[] nums={3,1,5,7,2,4,6,9,10,11,21,14,13,12}; heapSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); //输出：7 6 5 5 4 3 2 1 } } public static void heapSort(int[] nums){ for (int i = nums.length/2-1; i >= 0 ; i--) { adjustHeap(nums,i,nums.length); } for (int i = nums.length-1; i >0 ; i--) { swap(nums,i,0); adjustHeap(nums,0,i); } } public static void adjustHeap(int[] nums,int i,int length){ int temp = nums[i]; for (int j = 2*i+1; j < length; j=j*2+1) { if (j+1<length && nums[j]<nums[j+1]){ j++; } if(nums[j]>temp){ nums[i]=nums[j]; i=j; }else { break; } } nums[i] = temp; } public static void swap(int[] nums,int a,int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }

归并排序

package com.company; public class mergeSort { public static void main(String[] args) { int[] nums={3,1,5,7,2,4,6}; // sort(nums,0,4,7); merge(nums,0,6); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); //输出：7 6 5 5 4 3 2 1 } } public static void merge(int[] nums,int left,int right){ if (right == left) return; int mid=left+(right-left)/2; merge(nums,left,mid); merge(nums,mid+1,right); sort(nums,left,mid+1,right); } public static void sort(int[] nums ,int left,int right,int end){ int[] temp = new int[end-left+1]; int i=0,r=right,l=left; while (l<=right-1&&r<=end){ if(nums[l] >= nums[r]){ temp[i++]=nums[r++]; }else { temp[i++]=nums[l++]; } } while (r<=end){ temp[i++]=nums[r++]; } while (l<=right-1){ temp[i++]=nums[l++]; } for (int j = 0; j < temp.length; j++) { nums[left+j]=temp[j]; } } }

快速排序

package com.company; public class quicklysort { public static void main(String[] args) { int[] cake = {2,4,5,2,4,3,2,5,8}; quicklysort(cake,0,cake.length-1); for (int i = 0; i < cake.length; i++) { System.out.print(cake[i]+","); //输出2,2,2,3,4,4,5,5,8, } } public static void quicklysort(int[] q ,int l,int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) { int temp=q[i]; q[i]=q[j]; q[j]=temp; } } quicklysort(q, l, j); quicklysort(q, j + 1, r); } }

希尔排序

package com.company; public class shellSort { public static void main(String[] atgs){ int[] nums={3,1,5,7,2,4,6,9,10,11,21,14,13,12}; shell(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); //输出：7 6 5 5 4 3 2 1 } } public static void shell(int[] num){ int h=1; while (h <= num.length/3){ h=h*3+1; } for (int gap = h; gap > 0 ; gap=(gap-1)/3) { for (int i = gap; i < num.length; i++) { for (int j = i; j > gap-1 ; j-=gap) { if(num[j]<num[j-gap]){ swap(num,j,j-gap); } } } } } public static void swap(int[] nums,int a,int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }