排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含14034字,纯文字阅读大概需要21分钟。
内容图文
![排序算法](/upload/InfoBanner/zyjiaocheng/1178/47b7131b70d84a068a585e2024692a4f.jpg)
冒泡排序 package basic_class_01; import java.util.Arrays; public class Code_00_BubbleSort { public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } } } publicstaticvoid swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for testpublicstaticvoid comparator(int[] arr) { Arrays.sort(arr); } // for testpublicstaticint[] generateRandomArray(int maxSize, int maxValue) { int[] arr = newint[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for testpublicstaticint[] copyArray(int[] arr) { if (arr == null) { returnnull; } int[] res = newint[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for testpublicstaticboolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { returnfalse; } if (arr1 == null && arr2 == null) { returntrue; } if (arr1.length != arr2.length) { returnfalse; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { returnfalse; } } returntrue; } // for testpublicstaticvoid printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for testpublicstaticvoid main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); bubbleSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); bubbleSort(arr); printArray(arr); } }
选择排序 package basic_class_01; import java.util.Arrays; public class Code_02_SelectionSort { public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } } publicstaticvoid swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for testpublicstaticvoid comparator(int[] arr) { Arrays.sort(arr); } // for testpublicstaticint[] generateRandomArray(int maxSize, int maxValue) { int[] arr = newint[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for testpublicstaticint[] copyArray(int[] arr) { if (arr == null) { returnnull; } int[] res = newint[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for testpublicstaticboolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { returnfalse; } if (arr1 == null && arr2 == null) { returntrue; } if (arr1.length != arr2.length) { returnfalse; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { returnfalse; } } returntrue; } // for testpublicstaticvoid printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for testpublicstaticvoid main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); selectionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); selectionSort(arr); printArray(arr); } }
堆排序 package basic_class_01; import java.util.Arrays; public class Code_03_HeapSort { /** * 堆排序 特别重要 * @param arr */ public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int size = arr.length; swap(arr, 0, --size); while (size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } publicstaticvoid heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } publicstaticvoid heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } publicstaticvoid swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for testpublicstaticvoid comparator(int[] arr) { Arrays.sort(arr); } // for testpublicstaticint[] generateRandomArray(int maxSize, int maxValue) { int[] arr = newint[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for testpublicstaticint[] copyArray(int[] arr) { if (arr == null) { returnnull; } int[] res = newint[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for testpublicstaticboolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { returnfalse; } if (arr1 == null && arr2 == null) { returntrue; } if (arr1.length != arr2.length) { returnfalse; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { returnfalse; } } returntrue; } // for testpublicstaticvoid printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for testpublicstaticvoid main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); heapSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); heapSort(arr); printArray(arr); } }
快排 package basic_class_01; import java.util.Arrays; public class Code_04_QuickSort { public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } /** * 快排问题 比较重要 * @param arr * @param l * @param r */publicstaticvoid quickSort(int[] arr, int l, int r) { if (l < r) { swap(arr, l + (int) (Math.random() * (r - l + 1)), r); //随机快排int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } publicstaticint[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; while (l < more) { if (arr[l] < arr[r]) { swap(arr, ++less, l++); } elseif (arr[l] > arr[r]) { swap(arr, --more, l); } else { l++; } } swap(arr, more, r); returnnewint[] { less + 1, more }; } publicstaticvoid swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for testpublicstaticvoid comparator(int[] arr) { Arrays.sort(arr); } // for testpublicstaticint[] generateRandomArray(int maxSize, int maxValue) { int[] arr = newint[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for testpublicstaticint[] copyArray(int[] arr) { if (arr == null) { returnnull; } int[] res = newint[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for testpublicstaticboolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { returnfalse; } if (arr1 == null && arr2 == null) { returntrue; } if (arr1.length != arr2.length) { returnfalse; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { returnfalse; } } returntrue; } // for testpublicstaticvoid printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for testpublicstaticvoid main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); quickSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); quickSort(arr); printArray(arr); } }
归并排序 package basic_class_01; import java.util.Arrays; public class Code_05_MergeSort { public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); } /** * 归并排序 * @param arr 一个数组 * @param l 左 * @param r 右 */publicstaticvoid mergeSort(int[] arr, int l, int r) { if (l == r) { return; } int mid = l + ((r - l) >> 1); //l r 中点位置 mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } publicstaticvoid merge(int[] arr, int l, int m, int r) { int[] help = newint[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while (p1 <= m && p2 <= r) { help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[l + i] = help[i]; } } // for testpublicstaticvoid comparator(int[] arr) { Arrays.sort(arr); } // for testpublicstaticint[] generateRandomArray(int maxSize, int maxValue) { int[] arr = newint[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for testpublicstaticint[] copyArray(int[] arr) { if (arr == null) { returnnull; } int[] res = newint[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for testpublicstaticboolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { returnfalse; } if (arr1 == null && arr2 == null) { returntrue; } if (arr1.length != arr2.length) { returnfalse; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { returnfalse; } } returntrue; } // for testpublicstaticvoid printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for testpublicstaticvoid main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); mergeSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); mergeSort(arr); printArray(arr); } }
插入排序 package basic_class_01; import java.util.Arrays; public class Code_01_InsertionSort { /** * 插入排序 * @param arr */ public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } publicstaticvoid swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for testpublicstaticvoid comparator(int[] arr) { Arrays.sort(arr); } // for testpublicstaticint[] generateRandomArray(int maxSize, int maxValue) { int[] arr = newint[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for testpublicstaticint[] copyArray(int[] arr) { if (arr == null) { returnnull; } int[] res = newint[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for testpublicstaticboolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { returnfalse; } if (arr1 == null && arr2 == null) { returntrue; } if (arr1.length != arr2.length) { returnfalse; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { returnfalse; } } returntrue; } // for testpublicstaticvoid printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for testpublicstaticvoid main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr); } }
原文:https://www.cnblogs.com/lijun199309/p/9449499.html
内容总结
以上是互联网集市为您收集整理的排序算法全部内容,希望文章能够帮你解决排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。