算法(一)直接选择排序

直接选择排序，整体思想是将数据分成两个区域，有序区与无序区。排序的时候是每次从无序区中选择出最小的数，然后插入到有序区中的最末尾，从而形成更大的有序区。直到无序区中的数为零，结束排序。

详细步骤

假设排序数组为a[0…n-1];

1. 首先有序区中的个数为0，令i = 0。从无序区中选择最小的数，加入到有序区a[i]中。使得有序区为a[0..i],无序区为a[i...n-1]
2. 完成后 i++ ,然后继续前面的步骤，直到 i = n-1 为止。使得全部数都在有序区中。

所以根据上面的思想步骤就能很容易的写出实现代码了

实现

public static void selectSort(int[] arr) {
        int temp;
        int mid;
        for (int i = 0; i < arr.length - 1; i++) {
            mid = i;//关键数
            for (int j = mid + 1; j < arr.length; j++) {
                if (arr[mid] > arr[j])//找到最小值
                    mid = j;
            }
            if (mid != i) {//不等于关键数则交换
                temp = arr[mid];
                arr[mid] = arr[i];
                arr[i] = temp;
            }
        }
    }

总结

该排序为不稳定排序，首先说明何为稳定排序：在排序结束后如果排序中相同大小的数与排序前的相对位置相同(即前后位置不变)，则称为稳定排序 直接选择排序我们很容易发现，如果排序数组为a[11,11,2]在进行第一趟排序之后第一个11与2交换位置使得原来前面的11排序到后面的11之后，所以直接选择排序为不稳定排序。同时它的时间复杂度为O(n^2)

转载请指明出处 idisfkj博客：https://idisfkj.github.io