算法系列之-选择排序(一)

所谓的选择排序，就是在一堆数中依次选出最小数，
选择排序的主要思想是从数组中取出一个数，和后面的每个数进行比较，
直到比较完所有数，最后得出一个最小数。这个最小数就放在数组的最前面，
那么接下来在剩余的数中重复此操作，知道选出所有的数。排序结束

int[] arr = {8,2,6,3,1,4};

如上所示：第一步以8位参考，后面的数依次和它比较，如果小于8就进行位置交换

1. 8和2比较 交换位置 2,8,6,3,1,4
2. 2和6比较位置不变
3. 2和3比较位置不变
4. 2和1比较 交换位置 1,8,6,3,2,4
5. 1和4比较 不变
6. 8和6比较 交换位置 1,6,8,3,2,4
   ......
   以此类推

给出步骤图

image.png

最后给出代码

 private void selectSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
           
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    swap(a,j,i);
                }
            }

        }
    }

 private void swap(int[] a, int min, int max) {
        int temp = a[max];
        a[max] = a[min];
        a[min] = temp;
    }

下面给出python实现的优化方案

class SelectSort():

    def selectorSort(self, list):
        count = len(list)
        for i in range(0, count):
            min = i
            for j in range(i + 1, count):
                if list[min] > list[j]:
                   min = j  #为什么不直接交换，要先记录脚标吗，因为赋值比交换位置效率高
            list[i], list[min] = list[min], list[i]
        return list

任何问题请留言