陕西宝陵建设集团网站,兰州搜狗推广,怎么注册公司需要多少钱,通州区网站建设1. 基本原理 将待排序的元素分为已排序(初始为空)和未排序两组#xff0c;依次将未排序的元素中值最小的元素放入已排序的组中。 直接选择排序简单直观#xff0c;但性能略差#xff1b;堆排序是一种较高效的选择排序方法#xff0c;但实现起来略微复杂。 2. 直接选择排序 …1. 基本原理 将待排序的元素分为已排序(初始为空)和未排序两组依次将未排序的元素中值最小的元素放入已排序的组中。 直接选择排序简单直观但性能略差堆排序是一种较高效的选择排序方法但实现起来略微复杂。 2. 直接选择排序 基本过程为 在一组元素R[i]到R[n]中选择具有最小关键码的元素若它不是这组元素中的第一个元素则将它与这组元素中的第一个元素对调。除去具有最小关键字的元素在剩下的元素中重复第(1)、(2)步直到剩余元素只有一个为止。 3. 代码实现 1 package com.windy.sort;2 3 import java.util.Arrays;4 5 import org.junit.Test;6 7 public class SelectSort {8 9 class DataWrap implements ComparableDataWrap {10 int data;11 String flag;12 13 public DataWrap(int data, String flag) {14 this.data data;15 this.flag flag;16 }17 18 Override19 public String toString() {20 return data flag;21 }22 23 Override24 public int compareTo(DataWrap dw) {25 26 return this.data dw.data ? 1 : (this.data dw.data ? 0 : -1);27 28 }29 }30 31 Test32 public void test1() {33 34 DataWrap[] dw new DataWrap[] { 35 new DataWrap(-9, ), 36 new DataWrap(1, ),37 new DataWrap(-47, *),38 new DataWrap(1246, ), 39 new DataWrap(758, ), 40 new DataWrap(-123, ), 41 new DataWrap(5, ),42 new DataWrap(638, ), 43 new DataWrap(-47, ), 44 new DataWrap(5, *)45 };46 47 System.out.println(排序前\n Arrays.toString(dw));48 selectSort(dw);49 System.out.println(排序后\n Arrays.toString(dw));50 }51 52 Test53 public void test2() {54 DataWrap[] dw new DataWrap[] { 55 new DataWrap(-9, ), 56 new DataWrap(1, ),57 new DataWrap(-47, *),58 new DataWrap(1246, ), 59 new DataWrap(758, ), 60 new DataWrap(-123, ), 61 new DataWrap(5, ),62 new DataWrap(638, ), 63 new DataWrap(-47, ), 64 new DataWrap(5, *)65 };66 67 System.out.println(排序前\n Arrays.toString(dw));68 selectSort2(dw);69 System.out.println(排序后\n Arrays.toString(dw));70 }71 72 // 直接选择排序73 private static void selectSort(DataWrap[] dw) {74 75 int length dw.length;76 77 System.out.println(排序中...);78 79 for (int i 0; i length - 1; i) {80 81 for (int j i 1; j length; j) {82 if (dw[i].compareTo(dw[j]) 0) {83 DataWrap temp;84 temp dw[i];85 dw[i] dw[j];86 dw[j] temp;87 }88 }89 90 System.out.println(Arrays.toString(dw));91 }92 93 }94 95 /*96 * 直接选择排序改进版 用临时变量记录最小值的下标而不是选择马上交换 在对比一轮结束之后才选择交换97 */98 private static void selectSort2(DataWrap[] dw) {99 int length dw.length;
100
101 System.out.println(排序中...);
102 for (int i 0; i length - 1; i) {
103 int min i;
104
105 for (int j i 1; j length; j) {
106 // 用最小值去对比而不是dw[i]
107 if (dw[min].compareTo(dw[j]) 0) {
108 min j;
109 }
110 }
111
112 DataWrap temp;
113 temp dw[i];
114 dw[i] dw[min];
115 dw[min] temp;
116
117 System.out.println(Arrays.toString(dw));
118 }
119
120 }
121
122 } View Code 结果打印 排序前[-9, 1, -47*, 1246, 758, -123, 5, 638, -47, 5*]排序中...[-123, 1, -9, 1246, 758, -47*, 5, 638, -47, 5*][-123, -47*, 1, 1246, 758, -9, 5, 638, -47, 5*][-123, -47*, -47, 1246, 758, 1, 5, 638, -9, 5*][-123, -47*, -47, -9, 1246, 758, 5, 638, 1, 5*][-123, -47*, -47, -9, 1, 1246, 758, 638, 5, 5*][-123, -47*, -47, -9, 1, 5, 1246, 758, 638, 5*][-123, -47*, -47, -9, 1, 5, 5*, 1246, 758, 638][-123, -47*, -47, -9, 1, 5, 5*, 638, 1246, 758][-123, -47*, -47, -9, 1, 5, 5*, 638, 758, 1246]排序后[-123, -47*, -47, -9, 1, 5, 5*, 638, 758, 1246] 4. 算法效率分析 算法的时间效率无论初始状态如何在第i趟排序中选择最小关键码的元素需做n-i次比较因此总的比较次数为 算法的空间效率空间效率很高只需要一个附加程序单元用于交换其空间效率为O(1) 算法的稳定性不稳定转载于:https://www.cnblogs.com/fengze/p/6608138.html
