排序算法-----选择排序

排序算法

就是使用一串记录，按照其中的某个或某个关键字的大小，递增或递减的排列起来的操作。

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。 （选择排序、冒泡排序、插入排序、希尔排序、归并排序、堆排序、快速排序）非比较类排序：不通过比较来决定元素之间的相对次序，他可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 （计数排序、桶排序、基数排序）

排序的相关概念

**稳定：**如果a原本在b前面，而ab，排序之后a仍然在b的前面。5,3,4,4,1,21,2,3,4,4,5

不稳定性：如果a原本在b前面，而a==b，排序之后a可能会出现在b的后面。

**时间复杂度：**对排序数据的总的操作次数，反映当n变化时，操作次数呈现什么规律

**空间复杂度：**是指算法在计算机内执行时所需存储空间的度量，他也是数据规模n的函数

- 选择排序

选择排序是一种简单直观的排序算法。他的工作原理：首先在位排序序列中找到最大（小），存放到排序系列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大），然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度：O（n^2）空间复杂度：S（1） package 排序算法; import java.lang.reflect.Array; import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int arr[]={4,9,2,3,1,5,8,7}; selectionSort(arr); System.out.println(Arrays.toString(arr)); } private static void selectionSort(int[] arr) { for (int i=0;i<arr.length-1;i++){ for (int j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ swap(arr,i,j); } } } } private static void swap(int[] arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }

执行结果

[1, 2, 3, 4, 5, 7, 8, 9]