(一个帖子限制字数,不能发完,这个接上帖)
4、插入排序:
包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。 直接插入排序:无序插有序,将数组中每个数依次插入已经排列好顺序的数组中,需要用到嵌套循环,外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。 public static void inSort(int[] arr) { int num=arr.length; int i,j; for(i=0;i<num;i++){ int temp=arr; for(j=i; j>0 && temp<arr[j-1]; j--){ arr[j]=arr[j-1]; } arr[j]=temp; } } 5、希尔排序:
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。(下面希尔排序代码还需优化,只能表达思想,还不能正确运行) public class Test { public static int[] a = { 10,32, 1, 9, 5, 7, 12, 0, 4, 3 }; public static void main(String args[]) { int i; // 循环计数变量 int Index = a.length;// 数据索引变量 System.out.print("排序前: "); for (i = 0; i < Index - 1; i++) System.out.printf("%3s ", a); System.out.println(""); ShellSort(Index - 1); // 选择排序 // 排序后结果 System.out.print("排序后: "); for (i = 0; i < Index - 1; i++) System.out.printf("%3s ", a); System.out.println(""); } public static void ShellSort(int Index){ int i, j, k; // 循环计数变量 int Temp; // 暂存变量 boolean Change; // 数据是否改变 int DataLength; // 分割集合的间隔长度 int Pointer; // 进行处理的位置 DataLength = (int) Index / 2; // 初始集合间隔长度 while (DataLength != 0) // 数列仍可进行分割 { // 对各个集合进行处理 for (j = DataLength; j < Index; j++) { Change = false; Temp = a[j]; // 暂存Data[j]的值,待交换值时用 Pointer = j - DataLength; // 计算进行处理的位置 // 进行集合内数值的比较与交换值 while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) { a[Pointer + DataLength] = a[Pointer]; // 计算下一个欲进行处理的位置 Pointer = Pointer - DataLength; Change = true; if (Pointer < 0 || Pointer > Index) break; } // 与最后的数值交换 a[Pointer + DataLength] = Temp; if (Change) { // 打印目前排序结果 System.out.print("排序中: "); for (k = 0; k < Index; k++) System.out.printf("%3s ", a[k]); System.out.println(""); } } DataLength = (int)DataLength/2; // 计算下次分割的间隔长度 } } } 6、Java提供的排序方法
Java的util包中提供了一个数组排序方法,开发时使用该句代码 Arrays.sort(arr); |