选择排序

目录

选择排序（第一种）（不稳定）：

          代码实现：

        思路分析：

        选择排序（第二种）（不稳定）：

        代码实现： 

        思路分析：

---

选择排序（第一种）（不稳定）：

          代码实现：

 public static void selectSort(int[] arr) {for (int i = 0; i < arr.length; i++) {int mindex = i;for (int j = i + 1; j < arr.length; j++) {if(arr[mindex] > arr[j]) {mindex = j;}}//交换swap(arr,mindex,i);}}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

        思路分析：

        首先，每一次在 i 循环开始后，使用 mindex 记录 其 i 下标值的大小，之后，j 每次在 i 后一个元素开始循环，如果过程遇到 下标值 比 mindex下标值更小的，mindex 下标更新成小的下标，直到一轮 j 的循环结束，就能找到此过程与 i 下标相比最小的元素下标，再进行交换。 使得最小的元素放到了前面。

        

        选择排序（第二种）（不稳定）：

        代码实现： 

 public static void selectSort2(int[] arr) {int left = 0;int right = arr.length - 1;while(left < right) {int mindex = left;int maxdex = left;for (int i = left + 1; i <= right ; i++) {if(arr[mindex] > arr[i]) {mindex = i;}if(arr[maxdex] < arr[i]) {maxdex = i;}}swap(arr,mindex,left);假设第一个值 是最大值if(maxdex == left) {maxdex = mindex;}swap(arr,maxdex,right);left++;right--;}}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

        思路分析：

                

         使用两个变量 mindex 和 maxdex 记录遍历过程中最小值的下标和最大值的下标。

        先给定 mindex 和 maxdex 的下标为 left ，定义一个变量 i ，从 left + 1 的位置开始，不断往后走更新mindex 和 maxdex ，找到包含 left 和 right 之间 的最大值 和最小值的下标，再将其left 与最小值下标mindex交换，right 与 最大值 maxdex 交换，然后left 加加，right减减，缩小范围，不断重复此过程，直至left 与 right相遇停止。

        值得注意的是，如果最大值下标 maxdex 是 left 的位置，那么在 left 和 mindex 的下标值交换后，left 下标的最大值跑到了 mindex 的位置去了，所有要把 maxdex 赋值成 mindex。

        

        选择排序效率不是很好。实际中很少使用。