首页 > 代码库 > O(n^2) Sortings
O(n^2) Sortings
Insertion Sort:
Time Complexity: Best O(n) (when already sorted); Average O(n^2); Worst O(n^2).
Space Complexity: O(1)
public static void main(String[] args) { int[] a = new int[]{3,2,9,0,1,7,5,4,8,6}; insertionSort(a); System.out.println(Arrays.toString(a)); } public static void insertionSort(int[] a) { for(int i = 1;i<a.length;++i) { int j = i; while(j>=1 && a[j]<a[j-1]) { int temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; --j; } } }
Bubble Sort:
Time Complexity: Best O(n) (when already sorted); Average O(n^2); Worst O(n^2).
Space Complexity: O(1)
public static void main(String[] args) { Random r = new Random(); int[] a = new int[]{r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100)}; int[] aCopy1 = Arrays.copyOf(a, a.length); int[] aCopy2 = Arrays.copyOf(a, a.length); bubbleSort(aCopy1); optimizedBubbleSort(aCopy2); System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(aCopy1)); System.out.println(Arrays.toString(aCopy2)); } public static void bubbleSort(int[] a) { int end = a.length; boolean swapped = true; while(swapped) { swapped = false; for(int i = 1;i<end;++i) { if(a[i]<a[i-1]) { int temp = a[i]; a[i]=a[i-1]; a[i-1]=temp; swapped = true; } } --end; } } public static void optimizedBubbleSort(int[] a) { int end = a.length; while(end>0) { int newEnd = 0; for(int i = 1;i<end;++i) { if(a[i]<a[i-1]) { int temp = a[i]; a[i]=a[i-1]; a[i-1]=temp; newEnd = i; } } end = newEnd; } }
Selection Sort:
Time Complexity: Best O(n^2); Average O(n^2); Worst O(n^2).
Space Complexity: O(1)
public static void main(String[] args) { Random r = new Random(); int[] a = new int[]{r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100)}; int[] aCopy1 = Arrays.copyOf(a, a.length); int[] aCopy2 = Arrays.copyOf(a, a.length); selectionSort(aCopy1); System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(aCopy1)); } private static void selectionSort(int[] a) { for(int i = 0;i<a.length-1;++i) { int minIndex = i; for(int j = i+1;j<a.length;++j) { if(a[j]<a[minIndex]) minIndex = j; } if(minIndex != i) { int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } }
O(n^2) Sortings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。