选择排序算法
O(n^2) 的排序算法
时间复杂度的概念
选择排序 Selection Sort
8 7 5 4 9 1 2 3
1 7 5 4 9 8 2 3
1 2 5 4 9 8 7 3
1 2 3 4 9 8 7 5
1 2 3 4 5 8 7 9
1 2 3 4 5 7 8 9
从小到大，首先找到里面最小的1放在第一个位置，然后把那个数字放在1的位置上，然后再去找倒数2小的，放在第二个位置。依次类推排序。最多需要 n-1次排序
从i=0位置开始，外套循环，从j=i+1开始，内套循环，将每一个位置的值都和自己后面值一一的进行比较，寻找对应的值，进行交换。
代码
Java
package imooc_algo;
public class SelectionSort {
//构造方法
private SelectionSort(){}
public static void sort(int[] arr){
int n = arr.length;
//外部循环，从第一个开始
for(int i=0;i<n;i++){
//寻找[i,n]之间最小值的索引
int minIndex = i;
for(int j=i+1;j<n;j++)
if(arr[j]<arr[minIndex])
minIndex = j;
//swap 函数自定义
swap(arr,i,minIndex);
}
}
//交换函数
private static void swap(int[] arr, int i,int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args){
int[] arr = {10,9,6,7,1,2,3,5,4,8};
SelectionSort.sort(arr);
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]);
System.out.print(' ');
}
System.out.println();
}
}
结果
1 2 3 4 5 6 7 8 9 10
主要是循环的过程，MinIndex寻找最小值的索引。
Python
def selectionSort(alist):
for i in range(len(alist)):
// 最小值的索引
minIndex=i
for j in range(i+1,len(alist)):
if alist[minIndex] > alist[j]:
minIndex=j
//将最小值和第一个位置的数字替换
alist[i],alist[minIndex] = alist[minIndex],alist[i]
return alist
if __name__ == '__main__':
alist = [10,8,9,1,2,3,5,4,7,6]
print (selectionSort(alist))
结果
C:\Users\Administrator\Desktop\Algo>python3 Seclectsort.py
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]