简单选择排序算法分析,简单选择排序实例
墨初 知识笔记 48阅读
目录
1. 原理和执行流程
2. 代码实现
3. 性能分析
4. 双向选择排序了解
1. 原理和执行流程
选择排序包含了堆排序和简单选择排序。
每一次从无序区间选出最大或最小的一个元素存放在无序区间的最后或最前直到全部待排序的数据元素排完 。
选择类排序的主要动作是“选择”简单选择排序采用最简单的选择方式从头至尾顺序扫描序列。找出最小的一个关键字和第一个关键字交换接着从剩下的关键字中继续这种选择和交换最终使序列有序。
2. 代码实现
//选择排序 public static void selectSort(int[] array){ for(int i 0;i < array.length - 1;i){ //剩下最后一个元素不需要选择了因为已经在最合适的位置 boolean flag false;//用来比较是否更好minIndex的值 int j i 1;//往后一位进行比较 int minIndex i; for(;j < array.length;j){ if(array[minIndex] > array[j]){ minIndex j; flag true; } } if(flag){ int tmp array[minIndex]; array[minIndex] array[i]; array[i] tmp; } } } public static void main(String[] args) { int[] arr {3,1,2,4,5}; Sort.selectSort(arr); for (int x : arr) { System.out.print(x ); } }3. 性能分析 时间复杂度空间复杂度O(N^2)O(1)数据不敏感数据不敏感
4. 双向选择排序了解
每一次从无序区间选出最小 最大的元素存放在无序区间的最前和最后直到全部待排序的数据元素排完 。
public static void main(String[] args) { int[] arr {5,2,1,3,4}; Sort.selectSortOP(arr); for (int x : arr) { System.out.print(x ); } } //双向选择排序 //和单向的时间复杂度一致可能只是更帅一点吧 public static void selectSortOP(int[] array){ int low 0; int high array.length - 1; // [low, high] 表示整个无序区间 // 无序区间内只有一个数也可以停止排序了 while(low < high){ int min low; int max low; for(int i low 1;i < high;i){ if (array[i] < array[min]) { min i; } if(array[i] > array[max]){ max i; } } swap(array,low,min); //见下面解析最大值可能在low的位置上min和low一交换最大值就到了min的位置 if(max low){ max min; } swap(array,high,max); low; high--; } }array { 9, 5, 2, 7, 3, 6, 8 }; // 交换之前// low 0; high 6// max 0; min 2array { 2, 5, 9, 7, 3, 6, 8 }; // 将最小的交换到无序区间的最开始后// max 0但实际上最大的数已经不在 0 位置而是被交换到 min 即 2 位置了// 所以需要让 max min 即 max 2array { 2, 5, 8, 7, 3, 6, 9 }; // 将最大的交换到无序区间的最结尾后标签：