算法：选择排序

原理：

就是在待排序的数组数据值中查找到最小那个值，然后交换位置，直到排到只剩最后一个数。

图片展示

图片中的情况没有标指向，就是每一mix的下标指向未排序的第一数上面，让他跟剩下的数比较。小的话就交换位置，这样这个数就一定比排好的数大，剩下的也依次比这个数值大。

代码实现

public class SelectSort { public void sort(int arr[] ,int n){ int mix,i,j; for(i=0;i<n;i++){ //指向当前排序好的末尾，未排序的第一值得位置，同时为交换提供位置指向 mix = i; for(j=i+1;j<n;j++){ if(arr[j]<arr[mix]){ int tmp = arr[j]; arr[j] = arr[mix]; arr[mix] = tmp; } } } } public static void main(String[] args) { int[] a = {20,40,30,10,60,50}; new SelectSort().sort(a,6); System.out.println(Arrays.toString(a)); } }

代码改进

public class SelectSort { public void sort(int arr[] ,int n){ int mix,i,j; for(i=0;i<n;i++){ //指向当前排序好的末尾，未排序的第一值的位置，同时为交换提供位置指向 mix = i; for(j=i+1;j<n;j++){ if(arr[j]<arr[mix]){ //可能后面还有更小的数，所以只是先标识，不交换 mix = j; } } //判断是否找到更小的元素 if(mix!=i){ int temp = arr[mix]; arr[mix] = arr[i]; arr[i] = temp; } } } public static void main(String[] args) { int[] a = {20,40,30,10,60,50}; new SelectSort().sort(a,6); System.out.println(Arrays.toString(a)); } }

时间复杂度:

冒泡排序的时间复杂度是O(N²)。有n个数遍历一次的时间复杂度为O(N)，而需要进行n-1轮循环排序，所以是n²。

学习链接