面试之选择排序——你会怎么优化她【面试踩坑优化】
排序算法2-选择排序
课代表总结
—
基本思路
-
首先假设数组中的第一个元素为待排序数组中最小的元素，即temp=arr[0]，然后开始遍历数组中的其他元素，若发现第i个元素比temp小则重置temp值，即temp=arr[i] -
在第一趟排序时，找出数组中最小的元素，使其和arr[0]交换位置。 -
在第二趟排序时找出第二小的元素和arr[1]交换，依次类推。
public class Select {public static void main(String[] args) {int[] arr = new int[] { 10, 4, 2, 6, -2, 9, 0 };selectsort1(arr);}public static void selectsort1(int[] arr) {int temp, index;for (int i = 0; i < arr.length - 1; i++) {temp = arr[i];index = i;for (int j = i + 1; j < arr.length; j++) {if (temp > arr[j]) {temp = arr[j];index = j;}}if (index != i) {arr[index] = arr[i];arr[i] = temp;}System.out.println("第" + i + "趟排序后的结果是：" + Arrays.toString(arr));}}
优化
-
上面的选择排序基本思路是依次找到最小值，放到相应的位置，那么在遍历过程中既然能找到最小值，肯定也能找到最大值，并将其放在相应的位置上。 -
因此，通过遍历，将数组中的最大值和最小值都放在相应的位置上，这样整体数组排序的趟数为(arr.length/2),减少了运行时间。 -
下面代码每行都有思路注释，思路是最重要的！
public class Selsetsort {public static void main(String[] args) {int[] arr = new int[] { 10, 4, 2, 6, -2, 9, 0 };selectsort2(arr);System.out.println(Arrays.toString(arr));}public static void selectsort2(int[] arr) {int left = 0; //每次找到最小值应该放的位置int right = (arr.length - 1); //每次找到最大值应该放的位置int min = 0, max = 0; //记录遍历过程中找的的最小值和最大值int temp = 0; //用来交换两个数值时使用int mi = 0, mx = 0; //分别表示找到的最小值和最大值的下标for (int i = 0; i < (arr.length / 2); i++) {min = arr[left];max = arr[right];mi = left;mx = right;if (min > max) {temp = arr[left];arr[left] = arr[right];arr[right] = temp;min = arr[left];max = arr[right];}for (int j = left + 1; j < right; j++) {if (arr[j] < min) { //找到最小值min = arr[j];mi = j;}if (arr[j] > max) { //找到最大值max = arr[j];mx = j;}}if (mi != left) {arr[mi] = arr[left];arr[left] = min;}if (mx != right) {arr[mx] = arr[right];arr[right] = max;}left++;right--;System.out.println("第" + i + "趟排序结果为" + Arrays.toString(arr));}}}
性能比较
总结
-
上面算法的优化思路，绝对可以让你与众不同。 -
无论简单的算法还是更为复杂的，主要是解决问题的思路，举一反三，多思考，很多地方都可以应用的到！